1. Introduction to Planning

AI Planning

AI Planning finds a plan (sequence on actions to bring a system from $I$ to $G$) and ideally an optimal plan given: an initial state $I$, a goal state $G$, and a set of actions $A$.

Link to original

Closed World Assumption

The closed world assumption is the presumption that what can currently not be shown to be true is false.

This is a different kind of negation for which we use the symbol “not”. Remember that for $\neg A$ to be true, we need to explicitly prove $\neg A$; for this reason '$\neg$' is sometimes called strict negation.

For “not $A$” to be true, we need to show that $A$ is not known to be true; that is to say: every attempt to prove $A$ fails, there is no successful derivation tree for $A$.

Link to original

Defining a Domain

We define objects such as:

• cargo $(c_1,\dots ,c_n)$
• trucks $(t_1,\dots ,t_m)$
• locations $(l_1,\dots ,l_k)$

We define relations such as:

• pairs of locations can be connected; $connected(l_i,l_j)$
• each truck is in a given location; $at(t_i,l_j)$
• each cargo can be in a given location; $at(c_i,l_j)$
• each cargo can be on a truck; $on(c_i,t_j)$

We define actions such as:

Action	Parameters	Preconditions	Effects
Move	truck t location from location to	at(t, from)	+ at(t, to) - at(t,from)
Load	truck t cargo c location l	at(t, l) at(c, l)	+ on(c, t) - at(c, l)
Unload	truck t cargo c location l	at(t, l) on(c, t)	+ at(c, l) - on(c, t)

Preconditions are described through a set of relations that must be true. Effects are described by adding or deleting relations.

PDDL

The Planning Domain Definition Language is a standard language understood by planners.

It is described through two files:

• Domain file: general description of the world, which types of objects are involved, which actions can be applied, etc
• Problem file(s): specific situation to solve, list of objects, initial state, goal state

Different versions of PDDLs are able to handle different features:

• PDDL: propositional planning
• PDDL2.1: numbers + time
• PDDL3: preferences (not covered here)
• PDDL+: continuous change, processes, events (not covered here)

Gripper Domain in PDDL

Imagine a simple problem where a robot wants to move objects between two rooms, this is similar to the cargo domain we looked at earlier:

Action	Parameters	Preconditions	Effects
Move	room x room y	at-robot(x)	+ at-robot(y) - at-robot(x)
PickUp	room x ball b gripper g	at-robot(x) at(b, x) free(g)	+ carry(g,b) - at(b,x) - free(g)
Drop	room x ball b gripper g	at-robot(x) carry(g, b)	- carry(g,b) + at(b,x) + free(g)

We define the domain as such:

(define (domain gripper)
	# predicates
	(:predicates (ROOM ?x) (BALL ?x) (GRIPPER ?x)
		(at-robot ?x) (at ?x ?y)
		(free ?x) (carry ?x ?y))
	
	# move action
	(:action move
	 :parameters (?x ?y)
	 :precondition (and
	   (ROOM ?x)
	   (ROOM ?y)
	   (at-robot ?x)
	 )
	 :effect (and
	   (at-robot ?y)
	   (not (at-robot ?x))
	 )
	)
	
	# pick-up action
	(:action pick-up
	 :parameters (?x ?y ?z)
	 :precondition (and
	   (BALL ?x)
	   (ROOM ?y)
	   (GRIPPER ?z)
	   (at ?x ?y)
	   (at-robot ?y)
	   (free ?z)
	 )
	 :effect (and
	   (carry ?z ?x)
	   (not (at ?x ?y))
	   (not (free ?z))
	 )
	)
	
	# drop action
	(:action drop
	 :parameters (?x ?y ?z)
	 :precondition (and
	   (BALL ?x)
	   (ROOM ?y)
	   (GRIPPER ?z)
	   (carry ?z ?x)
	   (at-robot ?y)
	 )
	 :effect (and
	   (not (carry ?z ?x))
	   (at ?x ?y)
	   (free ?z)
	 )
	)
)

We define the problem as such:

(define (problem gripper-problem1)
	# select the domain
	(:domain gripper)
	
	# objects
	(:objects roomA roomB
		ball1 ball2 ball3 ball4
		left right)
	
	# initial state
	(:init (ROOM roomA) (ROOM roomB)
		(BALL ball1) (BALL ball2) (BALL ball3) (BALL ball4)
		(GRIPPER left) (GRIPPER right)
		
		(free left) (free right)
		(at-robot roomA)
		(at ball1 roomA) (at ball2 roomA) (at ball3 roomA) (at ball4 roomA))
	
	# goal state
	(:goal (and
		(at ball1 roomB)
		(at ball2 roomB)
		(at ball3 roomB)
		(at ball4 roomB)
	))
)