Automated Planning

Search vs Planning

milk, bananas 그리고 cordless drill을 가져오는 임무가 있다고 하자.

Standard search algorithms은 아마 fail 할 것이다.

Planning systems do the following:

1. open up action and goal representation to allow selection
2. divide-and-conquer by subgoaling
3. relax requirement for sequential construction of solutions

---

Planning as state space search

Planning as a search problem : search from the initial state through the space of states, looking for a goal

 

Algorithms for planning:

• Progression : forward state-space search
• Regression : backward relevant-space search

Heuristics for planning : need to find good domain-specific heuristics for planning problems

---

Planning Domain Definition Language(PDDL)

State : a conjunction of fluents(현재 세상에서의 상태) that are ground, functionless atoms

Actions : a set of action schema that is a set of ground actions

Example

The precondition and effect are conjunctions of literals that may contain variables.

A planning domain is defined by a set of action schemas

• A planning problem within the domain : initial state and a goal (conjunctions of literals)

---

Example Domain : Air cargo transport

---

Example Domain : Spare tire problem

---

Example Domain : The blocks world

---

Classical Planning Algorithm

• Forward/Backward state-space search
• Can be solved by applying heruistic search algorithms

Planning as Boolean satisfiability : SAT-based planner with propositional form translated from a PPDL description

---

Heuristics for Planning

Planning search problem is graph : nodes(states), edges(actions)

 

Problem relaxation

• graph에 edge를 더 넣어서 더 쉽게 경로를 찾을 수 있도록 한다.( ex. ignore-preconditions heuristic, ignore-delete-lists heuristic)
• 다수의 node를 그룹으로 묶는다.

Domain-independent pruning : symmetry reduction, serializable subgoals

FastForward : A system with ignore-delete-list heuristic and nonstandard hill-climbing search (modified to keep track of the plan)