Picat The Planner Module Questions and Answers

Question 1

A developer is using Picat's planner module to find a path in a maze. There are multiple paths from the start to the goal, with costs of 12, 15, and 18. The developer uses the call `plan(StartState, 20, Plan, Cost)`. Which of the following outcomes is guaranteed?

Accepted Answer

The planner will find one of the valid paths, but not necessarily the one with the cost of 12.

Answer

The `plan/4` predicate performs a resource-bounded search. It finds a plan that can transform the initial state to a final state with a cost that does not exceed the given limit. However, it does not guarantee optimality. It will succeed with the first valid plan it discovers that meets the cost constraint, which may or may not be the shortest path.

Question 2

When defining a planning problem, what is the primary purpose of the optional `heuristic(State) = H` function?

Accepted Answer

To guide the search by providing an estimated cost from the current `State` to a final state, which is used to prune search paths.

Answer

The `heuristic(State) = H` function is used by the planner's resource-bounded search algorithms. It provides an admissible estimate `H` of the cost to reach a goal from the given `State`. This estimate is compared with the current available resources; if the estimated cost is greater than the available resources, the search down that path is pruned, making the search more efficient.

Question 3

A developer is implementing the `action/4` predicate for a planning problem where the state is represented by a list of numbers. Which of the following rules inside the `action/4` predicate is invalid and will cause an error?

Accepted Answer

action(S, NextS, move, 1) => S[1] := S[1] + 1, NextS = S.

Answer

The Picat planner module tables all states encountered during the search to avoid re-computation and loops. Because of this, states must be treated as immutable. The use of the destructive assignment operator `:=` within an `action/4` predicate to modify a state is explicitly banned and will result in an error. New states must be constructed from old ones without modifying the original.

Question 4

What is the core mechanism within Picat's planner module that prevents infinite loops when searching a state space that contains cycles?

Accepted Answer

The automatic tabling of every state encountered during the search.

Answer

The planner module is built on Picat's tabling feature. It automatically tables every state that is generated during the search. If the planner encounters a state that is already in the table, it will not expand that state again, thus avoiding redundant computations and preventing infinite loops in graphs with cycles. This effectively converts the state-space search from a tree search to a graph search.

Question 5

In addition to the common `final(State)` predicate, the planner module also supports `final(State, Plan, Cost)`. What is the purpose of this alternative predicate?

Accepted Answer

It allows defining a condition where a final state can be reached from the current `State` by a known sequence of actions (`Plan`) with a given `Cost`.

Answer

The `final(State, Plan, Cost)` predicate provides a way to specify a condition where a final state is reachable from the current `State` via a pre-determined `Plan` with a specific `Cost`. If the system is not provided with this predicate, it assumes a default definition: `final(S,Plan,Cost) => Plan=[], Cost=0, final(S)`. This is useful for defining sub-goals or macro-actions within a larger planning problem.

Picat Practice Test

Picat Practice Test

Picat The Planner Module Questions and Answers