Given:

• an initial state
• a set of actions you can perform
• a state to achieve (goal)

Find:

• a plan: a partially or totally ordered set of actions needed to achieve
• the goal from the initial state

An automated planner is an intelligent agent that operates in a certain domain described by:

• a representation of the initial state
• a representation of a goal
• a formal description of the executable actions (also called operators)

ACTION REPRESENTATION

• A planner relies on a formal description of the executable actions. It is called Domain Theory.
• Each action is identified by a name and declaratively modeled through preconditions is postconditions.
• Preconditions are the conditions which must hold to ensure that the action can be executed;
• Postconditions represent the effects of the action on the world.
• Often the Domain Theory consists of operators containing variables that define classes of actions. A different instantiation of the variables corresponds to a different action.

Planning

• A planner is complete if it always finds a plan when it exists.
• A planner is correct when the solution found leads from the initial state to the goal.

PLANNING TECHNIQUES

• Deductive planning
• Planning as search
• Linear planning
• Nonlinear planning - Partial Order Planning (POP)
• Hierarchical planning
• Conditional planning
• Graph-based planning

Linear planning

A linear planner formulates the planning problem as a search in the state space and uses classical search strategies.（Planning as search）

Planning as forward search
Planning as backward search

Detuctive planning

Deductive planning uses logics for representing states, goals and actions and generates a plan as a theorem proof.

Green uses situation calculus to build a planning based on logic resolution.

Green法的缺陷是要描述的东西太多了，也就是frame problem

KOWALSKY FORMULATION

• holds(rel, s/a)： to describe all the relations rel that are true in a given state s or made true by the execution of an action.
• poss(s) that indicates if a state s is possible (namely reachable).
• pact(a,s) to indicate that it is possible to execute an action A in a state s, namely the preconditions of a are true in s.

Formulation需要这几部分

• Initial State
  • holds一些初始为真的状态
• Action Modeling
  • Preconditions，用pact描述各个action的前提条件
  • Effects，描述do()之后受影响的部分
• Frame Axioms/Conditions，描述do()前后不变（不受影响）的部分
• Clause
  • for precondition of action，
  • for State Reachability, 定义递归的规则
• Goal 描述目标的状态

Example

• Initial State
• action
• Effects & frame condition
• Frame condition 描述在执行某个动作后，明确规定哪些事实（fluents）是保持不变的。上式中 Frame condition 的含义，如果一个属性 V 在旧状态 S 下成立（holds(V, S)），并且 V 不是由于动作 move 而被改变的那几个属性（V \= ...），那么在执行动作后的新状态中，V 依然成立,。
• Clause
• Clause 的作用是 用逻辑公式定义一个状态在什么条件下才是“可能到达”的。
  • 基础事实（Base Case）：poss(s0).
    • 含义：初始状态 s0​ 总是可达的（可能的）。
  • 递归规则（Recursive Rule）：poss(do(A,S)) :- poss(S), pact(A,S).
    • 含义：如果在状态 S 下执行动作 A 产生了一个新状态 do(A,S)，那么这个新状态是可达的，前提必须满足：
    1. 原来的状态 S 本身就是可达的（poss(S)）。
    2. 在状态 S 下执行动作 A 是合法的，即满足了该动作的所有先决条件（pact(A,S)）
  • poss(s)：表示状态 s 是“可能的”（reachable），即存在一条动作路径可以到达这里。
  • pact(a,s)：表示动作 a 在状态 s 下是“可执行的”，即状态 s 满足了动作 a 所需的所有先决条件（Preconditions）。
  • do(A,S)：这是一个函数，表示在状态 S 中应用算子 A 后产生的结果状态。
• Goal：:- poss(S), holds(on(a,b),S),holds(on(b,g),S).

STRIPS

Stanford Research Institute Problem Solver

Action representation (3 lists)：

• PRECONDITIONS: fluents that should be true for applying the move
• DELETE List: fluents that become false after the move
• ADD List: fluents that become true after the move
  Example Move(X, Y, Z)
  Preconditions_: on(X,Y), clear(X), clear(Z)_
  Delete List_: clear(Z), on(X,Y)_
  Add list_: clear(Y), on(X,Z)_

Sometimes ADD e DELETE list are glued in an EFFECT list with positive and negative axioms
Esempio Move(X, Y, Z)
Precondizioni_: on(X,Y), clear(X), clear(Z)_
Effect List_:_ ¬clear(Z), ¬on(X,Y), clear(Y), on(X,Z)

Non Linear Planning

• Linear planners are search algorithms that explore the state space.
  • The plan is a linear sequence of actions to achieve the goals.
• Non-linear planners are search algorithms that generate a plan as a search problem in the space of plans.
  • In the search tree each node is a partial plan and operators are plan refinement operations.
• A non-linear generative planner assumes that the initial state is fully known Closed World Assumption: Everything that is not explicitly stated in the initial state is considered as false.

A non-linear plan is represented as

• a set of actions (instances of operators)
• a (not exhaustive) set of orderings between actions
  • 在图中，箭头就是先后顺序的表达。
  • 在文字上，Start<S<Stop,表示先Start，再S，再Stop
• a set of "causal links"

Causal links and threats

• A causal link is a triple that consists of two operators Si, Sj and a subgoal c . C should be precondition of Sj and effect of Si. Represent as $<S_i,S_j,C>$$$$$$$$$
• 
• 把threat放到$S_i$前面叫做demotion, 把threat放到$S_j$后面叫做promotion。

Partial Order Planning Algorithm (POP)

Modal Truth Criterion (MTC)

1. Establishment, open goal achievement by means of: (1) a new action to be inserted in the plan, (2) an ordering constraint with Action already in the plan or simply (3) of a variable assignment.
2. Promotion, ordering constraint that imposes the threatening action before the first of the causal link;
3. Demotion, ordering constraint that imposes the threatening action after the second of the causal link;
4. White knight, insert a new operator or use one already in the plan between to S1 and S3 such that it establishes the precondition of S3 threatened by S1.
5. Separation, insert non codesignation constraints between the variables of the negative effect and the threatened precondition so to avoid unification. This is useful when variables have not yet been instantiated.

CONDITIONAL PLANNING

A conditional planner is a search algorithm that generates various alternative plans for each source of uncertainty of the plan.

A conditional plan it is therefore constituted by:

• causal actions
• Sensing actions for retrieving unknown information
• Several alternative partial plans of which only one will be executed depending on the results of the observations.

HIERARCHICAL PLANNING

Hierarchical planners are search algorithms that manage the creation of complex plans at different levels of abstraction, by considering the simplest details only after finding a solution for the most difficult ones.

Detective Planning exercise

Kovalsky formulation

modeling某个action要写四部分：

1. effect，用holds(影响后状态，action)表达
2. frame condiftion，
   hold(V, do(action), S):-
   V\=前提条件，（都列出来）
3. clause for pre-condition of the action,
   pact(action, S):-
   holds(前提条件，S) （都列出来）
4. clause for the reachability of a state，
   poss(s0),
   poss(do(A,S)):-
   poss(S),
   poss(A,S).

STRIPS

对于一个action，列出他的PRECOND，ADD，DELETE list

对于 STRIPS 找到解的过程，通过执行可执行的action向goal stack添加新的状态，如果在current state中存在了，就可以从goal stack消掉；重复这个过程，直到goal stack中的状态全部被消除。

Causal links and threats

从结果倒着往回画可以执行的action，直到从goal连起来initial state。然后找出来threat 以及对应的casual links，改变顺序或者添加 white knight 使得没有threats，叉掉原本有threat的地方。整理图，去掉不必要的部分。