The Planner Module Flashcards

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?

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

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.

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

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.

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.

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?

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

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.

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

Answer: The automatic tabling of every state encountered during the search.

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.

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?

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`.

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.

A planner model has two `action/4` rules that can potentially match the same state: one for moving a block (`move`), and another for painting it (`paint`). The developer wants the planner to be able to try painting a block if a `move` action from that state ultimately fails to find a solution. How should the `action/4` rules be defined?

Answer: Both rules must be defined using the backtrackable operator `?=>`.

To allow the planner to explore alternative actions from a single state, the `action/4` predicate rules must be defined as backtrackable using the `?=>` operator. If the non-backtrackable `=>` operator is used, once a rule's head and condition match a call, the planner commits to that choice and will not backtrack to try other matching `action/4` rules for that state, even if the chosen path fails.