Planning In Game Playing (COMP3411)

A solution to a planning problem is an action sequence that, when applied to the initial state, results in a state that satisfies the goal.

So we are given, in GDL:

  • a description of the Initial State (facts)
    • e.g. off(rightSock) and off(leftSock).
  • a list of Actions
    • (e.g. rightShoe, precondition: righSockOn, effect: rightShoeOn)
  • a Goal
    • (e.g. rightShoeOn ^ leftShoeOn).

Planning by State-Based Search

  • Forward Search
  • Backwards Search
  • Bi-Directional Search

Partial-Order Planning

Partial Order Planning is breaking down the plan and leaving the order of actions open for as long as possible.


Partial-Order Planning as a Search Problem

The search nodes are partial-order plans, the initial plan contains only the start and the finish action.

Plans have 4 components:

  • A set of actions (steps of the plan)
  • A set of ordering constraints A<B (A before B)
  • A set of causal links A p→ B: A achieves p for B
  • A set of open preconditions

An action conflicts with a causal link A p→ B if it has the effect of ¬p, and it could come after A and before B.

A plan is consistent if there are no cycles in the ordering constraints, and no conflicts with causal links.

consistent plan with no open preconditions.

Solving Partial-Order Planning Problems

To solve these we apply the following algorithm:

start.precondition = none;
start.effect = none;
finish.precondition = goal;
finish.effect = none;
plan.actions = {start, finish};
plan.orderingConstraints = {start < finish};
plan.causalLinks = none;
plan.openPreconditions = finish.preconditions;
initialPlan = plan;
while (solution != found) {
   pick an open precondition p (of an action A);
   pick an action with that effect (of an action that isn't A);
   if (A not in plan.actions) {
      plan.actions += A;
      plan.orderingConstraints += {start < A, A < Finish};
   plan.causalLinks += A pB
   if (conflict(action C, causal Link A pB)) {
      plan.orderingConstraints += B<C or C<A;
   if (inconsistent(plan)) {
      plan = initialPlan;
      // repeat with different choices

Planning with Propositional Logic

Planning can be done by testing the satisfiability of a logical sentence (the ability for it to be true):

\begin{align} \text{ initial state ^ all possible actions ^ goal } \end{align}

This sentence contains the propositions for every action occurrence; A model will assign true to an action A iff A is part of the correct plan. (An assignment that corresponds to an incorrect plan will not be modelled because of inconsistency with the assertion that the goal is true).

Planners based on satisfiability can handle large planning problems.