Tools Collection

  • search-based problem-solving agent
  • logic-based planning agent
  • Planning definition domain language (PDDL)
  • state-space search
    • forward state-space search
    • backward state-space search
  • plan-space search
    • partial-order planning

Template

1
2
3
4
5
6
<!-- PDDL -->
Initial State: {state}
Goal State: {state}
Action({ActionName}(variable1,variable2,...)
    Precond:{a conjunction, all positive},
    Effect:{a conjunction, can extend to disjunction and conditional})

note: conditional effects are in the form: {when A: B}
note: conditional steps are in the form: {if A then B else C}
note: or in the form: {if A then B elseif C then D else E}

1
2
3
4
5
<!-- POP -->
Actions: {list of names of actions}
Orderings: {list of order constraints for actions, in form: A ≺ B}
Links: {available progression form one action to another, in form: A->^p B}
Open preconditions: {set of conditions not yet achieved}

note: $\prec$ is \prec by Tex, means: A must occur before B.
note: A ->^p B is actually $A \xrightarrow{p} B$

1
2
3
<!-- percept schema models -->
Percept({ActionName}(variable1,variable2,...)
    Precond: {a conjunction, all positive})

what is planning and why we need new method to find a plan

the first block of this course learnt about notation of agents, intelligent problem-solving, heuristic search, constraints, logic and logical reasoning, reasoning about actions and time, and in the future we will talk about planning and uncertainty, where change is the key topic in the second block of this course.

planning is the task of coming up with a sequence of actions what will achieve a goal, but we only considering classical planning, in which environments are fully observable, deterministic, finite, static, discrete, which is the simplest environment, and lifting some of these assumptions, raising a little more complex environment, will be the subject of the “uncertainty” part of the course.

search-based problem-solving agent and logical planning agents are not enough to achieve the goal in some or even most of planning problem, as the search-based problem solving agent has no goal-directness, has no problem decomposition into sub-goals that build on each other, which cause undo past achievements, has simple goal test doesn’t allow for the identification of milestones, besides, how to find a good heuristic function and how we model the way humans perceive complex goals and the quality of a plan are still mystery.

logical planning agents can solve some of questions we discussed with search-based problem-solving agent, its allow sub-goal and decompose big thing to smaller ones, but logic cannot give us a good proof or even a correct proof, and logically independent sub-goals may need to be undone to achieve other goals, this is a case that the solution stuck at local minimum, this is where non-linear planning being introduced, also I think laziness influence the solution, as there might be other solution if we switch two clauses joint by logic connector.

Both search and logic are important tools but need adapting to tackles: efficient search and inference and discriminating the variable quality of valid plans.

what is PDDL and what it consists of

Planning definition domain language (PDDL), which is a language expressive enough to cover interesting problems, restrictive enough to allow efficient algorithms, and allow us express states, actions (edge) and goals (also a state).

States are represented as conjunctions of propositional or function-free first order positive literals, and goal is a partial description of a state, in this case we get no restrictions which have applied to states, besides, a state should be a closed-world assumption.

action or action schemata, as they may contain variables, include the action name, a precondition description defines states in which action is executable, should be a conjunction of positive and negative literals, where all variables must occur in action name, and finally a effect description which defines how literals in the input state get changed and we assume that anything not mentioned remaining the same, it has same restriction as preconditions with an extra one, we need often to divide positive and negative effects into add list and delete list.

any action is applicable in any state that satisfies the precondition with an appropriate substitution for parameters.

result of executing action an state s in state s’ with any positive literal P in a’s effects added to the state and every negative literal not P removed from it, then solution is the action sequence that leads from the initial state to a state that satisfies the goal.

some free words

serious choice on how to describe a world, in term of vocabulary of predicate symbols that you use, that can either make you job easy or difficult.

state-space search, search the space of states using action schemata, bi-direction search is possible, so there are two type of search: forward state-space search (also called progression planning) and backward state-space search.

Any complete graph search algorithm (like A*) will be a complete graph panning algorithm.

Forward search does not solve problem of irrelevant actions (all actions considered from each state).

Heuristic for state-space search, divide and conquer (subgoal decomposition) and derive a relaxed problem (remove some constraints) are two possibilities to design a heuristic function.

let’s do partial-order planning

State-space search planning algorithms consider totally ordered sequences of actions.

partial-order planning (POP), Actions initial Start and Finish, Ordering constraints, causal links not allows conflict occur, Open preconditions.

“partial” means we only focus on clauses that we think we need. Partial-order solution will correspond to one or several linearisation of partial-order plan.

Consistent plan = plan without cycles in orderings and conflicts with links. Solution = consistent plan without open preconditions. Every linearisation of a partial-order solution is a total-order solution (implications for execution!).

This is an algorithm highly benefit with graph.

classical planning, the contingent planning

so far we only looked at classical planning, fully observable, static, deterministic. action descriptions are correct and compete. But unrealistic in many real-world applications. bounded, unbounded, conformant planning or sensorless, achieve goal in all possible circumstances. contingency planning, partially observable, non-deterministic environments, includes sensing actions and describes different paths for different circumstances. online planning and replanning, check whether plan requires revision during execution and replan accordingly.

percept schema models the agent’s sensors, Percept, precond, sensorless has no sensor and fully observable has no percept for a percept model.

PDDL conditional effect, when, if then else, “or”. acyclic, cyclic solutions, terminate with failure if circle occur, solved by add a branch back to the root. AND-OR graphs.