Planning with Resources
Philippe Laborie
[email protected]
ILOG
Foreword
Applications of AI Planning
Aerospace
Space
- Satellite, Launcher manufacturing
- Launch site operations
- Spacecraft operations
- Space users
- Autonomous space exploration
Aviation
- Manufacturers and suppliers
- Airlines, Airports
- Maintenance and repair organizations
- Air Traffic Control
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Foreword
Applications of AI Planning
Defense
Military logistic applications
Rescue and Military operations planning
Non-combatant Evacuation Operations
Emergency Assistance
Air Campaign Planning
Army Unit Operations
Coalition Operations
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Foreword
Applications of AI Planning
New information technology
Planning & Scheduling for the Web
Workflow, Business Process Management
Systems Management Aids
Help Desks and Assistants
Personal Assistants
Data analysis tasks, Database query
Virtual reality or other simulated environments
Computer games (bridge)
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Foreword
Applications of AI Planning
Industry
Process planning
Factory automation
- Production line scheduling
- Assembly planning
- Maintenance planning
Electronic design and manufacturing
Logistics
Project planning
Construction planning
Engineering Tasks
Management Tasks
5
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Foreword
Applications of AI Planning
Civil Security and Environment
Crisis Management
Evacuation Planning
Search & Rescue Coordination
Oil Spill Response
Medical Applications
Bioinformatics
Personal Active Medical Assistant
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Foreword
Applications of AI Planning
What most of these applications have in common ?
Manufacturing: A grinding operation requires a grinding machine. The grinding machine
can perform only one operation at a time. Only one grinding machine is available in the
shop.
Project Management: In a web site development project, the task of testing browsers
compatibility requires an effort of 6 person-months of a quality engineer. 5 quality
engineers are available.
Satellite: When the satellite is not within range of a receiving station, it can store images on
an onboard solid-state memory that provides a capacity of 90 Gbits (550 images).
Crisis Management: An aircraft B737-200 has a capacity to evacuate at most 120 people.
Maximum cargo loading is 3,400kg for a volume of 14.3 m3. Maximal range of the
aircraft is 2480km.
… they need the ability to reason about resources
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Overview
Planning with Resources
 Part I. State of the Art Overview

Definition of a Resource

Problem Modeling

Problem Solving
 Part II. Focus on Constraint-Based Approaches

Constraint-Programming

Problem Modeling

Problem Solving
 Constraint Propagation
 Search
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Planning with Resources
Part I: State of the Art Overview
State of the Art
Definition of a Resource
 A resource is any substance or (set of) object(s)
whose cost or available quantity induce some
constraint on the operations that use it
Manufacturing: A grinding operation requires a grinding machine. The grinding machine
can perform only one operation at a time. Only one grinding machine is available in the
shop.
 The1 grinding machine is a resource. It constrains the grinding
operations to execute sequentially on the machine.
0
Grinding-op1
10
Grinding-op3
Grinding-op2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
time
State of the Art
Definition of a Resource
 A resource is any substance or (set of) object(s)
whose cost or available quantity induce some
constraint on the operations that use it
Project Management: In a web site development project, the task of testing browsers
compatibility requires an effort of 6 person-months of a quality engineer. 5 quality
engineers are available.
5
 The team of quality engineers is a resource. It constrains the
number of tasks that can be executed in parallel and the
0
duration
of these tasks.
3 months
2 engineers
Web-site-dev1
Test-software1
11
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
time
State of the Art
Definition of a Resource
 A resource is any substance or (set of) object(s)
whose cost or available quantity induce some
constraint on the operations that use it
Satellite: When the satellite is not within range of a receiving station, it can store images on
an onboard solid-state memory that provides a capacity of 90 Gbits (550 images).
550
 The solid-state memory is a resource. It constrains the number
of images that can be taken between two periods of visibility of
the receiving station.
0
time
Pic1
12
Pic2
Pic5
Pic3
Pic4
Send-data
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Definition of a Resource
 A resource is any substance or (set of) object(s)
whose cost or available quantity induce some
constraint on the operations that use it
Crisis Management: An aircraft B737-200 has a capacity to evacuate at most 120 people.
Maximum cargo loading is 3,400kg for a volume of 14.3 m3. Maximal range of the
aircraft is 2480km.
3400
 The seat capacity of the B737-20 is a resource. It constrains the
number of people the plane can evacuate in a single flight. The
cargo capacity of the B737-20 is another resource. It constrains
the weight the aircraft can transport in a single flight. Etc...
0
time
Load-truck
13
Load-car
Unload-car
Unload-truck
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Definition of a Resource
 Resources Typology
14

Unary resource: Resource of capacity 1. Two activities
requiring the same unary resource cannot overlap

Discrete resource: Resource of capacity Q. Activities
requiring the same discrete resource can overlap
provided the resource capacity Q is not exceeded

Reservoir: Resource of capacity Q and initial level L;
Activities may consume or produce the reservoir. The
level of the reservoir over time must be kept in the
interval [0,Q]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Definition of a Resource
unary resource
availability
1
0
Op1
15
Op2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
time
State of the Art
Definition of a Resource
discrete resource
availability
Q
0
time
Op1
Op2
16
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Definition of a Resource
 In theory, a discrete resource of maximal capacity Q
can be represented as Q unary resources
Op1
{R1,…,Ri,…,Rj,…,RQ}
Opi
Opj
OpQ
OpQ+1
17
{R1,…,Ri,…,Rj,…,RQ}
{R1,…,Ri,…,Rj,…,RQ}
No solution after
trying Q! allocations
{R1,…,Ri,…,Rj,…,RQ}
{R1,…,Ri,…,Rj,…,RQ}
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Definition of a Resource
reservoir
level
Q
0
Op1
Op3
Op2
18
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
time
State of the Art
Definition of a Resource
 Resources are tightly linked with the notions of
time & concurrency

For unary and discrete resources, activities use the
resource over some time interval
 Handling parallel execution of activities is necessary to
take advantage of non-unitary capacities
 There may exist complex relations linking the duration
of an activity with the amount of resource it uses,
consumes and/or produces
19
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Definition of a Resource
 Resources may impose other constraints than just
capacity

State constraints : two activities requiring the resource
to be in incompatible states cannot overlap
 Minimal transition time between two consecutive
activities using the same unary resource
 Batching: two overlapping activities using the same
resource must start and end at the same time
 These additional constraints can generally be
expressed by classical planning predicates
20
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Definition of a Resource
 So … the hard point for planning with resources is
mainly the management of

Numerical time and
 Numerical capacity/availability
21
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling: STRIPS
 How hard is it to model time and capacities in
STRIPS ?

Exercise. Build a STRIPS model for the following
domain
A task to test a web-site lasts for 3 months and requires
2 quality engineers (out of 5 available). As a result of the
task, the web-site is tested. Other tasks also have
duration and compete for the same resource. The
model must correctly handle task parallelism.
22
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #1: Numerical quantities

No integer arithmetic is available in STRIPS. We need
to provide one.
 In domain description
(:predicates (plus ?i ?j ?k))
 In problem definition
(:objects _0 _1 _2 _3 _4 _5 _6 _7 _8 … )
(:init
(plus _0 _1 _1)(plus _1 _1 _2)(plus _2 _1 _3) …
(plus _0 _2 _2)(plus _1 _2 _3)(plus _2 _2 _4) … )
23
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #1: Numerical quantities

No integer arithmetic is available in STRIPS. We need
to provide one.
 Example of action that increase a quantity
(:action IncreaseQuantity
:parameters (?i ?d ?j)
:precondition (and (quantity ?i)
(plus ?i ?d ?j))
:effect (and (not (quantity ?i))
(quantity ?j)))
24
; ?j == ?i + ?d
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #2: Discrete Resource

The task is a time interval over which the resource is
used.
 Two actions to represent the task
(:action TestWebSite-Start
:parameters (?q2 ?q0)
:precondition (and (free-engineers ?q2)
(plus ?q0 _2 ?q2))
:effect (and (not (free-engineers ?q2))
(free-engineers ?q0)))
25
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #2: Discrete Resource

The task is a time interval over which the resource is
used.
 Two actions to represent the task
(:action TestWebSite-End
:parameters (?q0 ?q2)
:precondition (and (free-engineers ?q0)
(plus ?q0 _2 ?q2))
:effect (and (not (free-engineers ?q0))
(free-engineers ?q2)
(web-site-tested)))
26
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #2: Discrete Resource

The task is a time interval over which the resource is
used.
 Initially, the amount of resource is 5:
(:init (free-engineers _5) … )
27
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #3: Task Duration

Use a predicate startedAtTask to record when the
task was started and a global clock clock to measure
time
(:predicates
(clock ?t)
(testwebsite_started_at ?t) … )
(:action TestWebSite-Start
:parameters (?t0 … )
:precondition (and (clock ?t0) … )
:effect (and (testwebsite_started_at ?t0) … ))
28
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #3: Task Duration
(:action TestWebSite-End
:parameters (?t3 ?t0 … )
:precondition (and (testwebsite_started_at ?t0)
(clock ?t3)
(plus ?t0 _3 ?t3) … )
:effect (and (not (testwebsite_started_at ?t0) … )))
29
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Difficulty #3: Task Duration

Now we only need an action to increase time when
necessary:
(:action Tick
:parameters (?t0 ?t1)
:precondition (and (clock ?t0)
(plus ?t0 _1 t1))
:effect (and (not (clock ?t0))
(clock ?t1)))

We start at time 0:
(:init (clock I0) … )
30
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Conclusion

It is possible to represent time and resources in STRIPS

BUT … the model is not completely intuitive
 No built-in arithmetic
 A relative change on a resource (free-engineers -= 2) is
represented by two absolute changes:
(DEL (free-engineers ?x))
(ADD (free-engineers ?x+2))
 Representation of time is not natural (action TICK)
31
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Conclusion

A relative change on a resource is represented by two
absolute changes
(PRECOND (free-engineers ?x1)(plus ?x1 _1 ?x2))
(DEL (free-engineers ?x1))
(ADD (free-engineers ?x2))
MUTEX
(PRECOND (free-engineers ?y1)(plus ?y1 _1 ?y2))
(DEL (free-engineers ?y1))
(ADD (free-engineers ?y2))
32
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : STRIPS
 Conclusion

AND what about the performances ?
engineers
Test
Software
Training
TestWebSite
TestWebSite
Test
Software
Training
26s
150s
580s
33
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling
 Beyond STRIPS

Standalone languages
 PDDL2.1

 BTPL
Planning systems (language)
 parcPLAN
 O-Plan
 IXTET
 ASPEN
 RAX-PS
34
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : PDDL 2.1
 PDDL 2.1 was developed for the AIPS-2002
Planning Competition [Fox&Long 2002]
 Extension of PDDL [McDermott&al 1998] for
domains involving time and other numeric-valued
resources
 PDDL 2.1
35

Level 1: “Classical” propositional planning

Level 2: Numeric Variables

Level 3: Durative actions, No continuous effects

Level 4: Durative actions, continuous effects
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : PDDL 2.1
 Numeric variables
(:functions
(free-engineers) )
(:action Hire
:parameters ( ?n )
:precondition ( … )
:effect (and (increase (free-engineers) ?n) … ))
36
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : PDDL 2.1
 Numeric variables
Conditions:
(= (f ?x) ?q)
(< (f ?x) ?q) (> (f ?x) ?q)
(<= (f ?x) ?q) (>= (f ?x) ?q)
Effects:
(increase
(decrease
(scale-up
(scale-down
(assign
37
(f
(f
(f
(f
(f
?x)
?x)
?x)
?x)
?x)
?q)
?q)
?q)
?q)
?q)
; f(?x) += ?q
; f(?x) -= ?q
; f(?x) *= ?q
; f(?x) /= ?q
; f(?x) = ?q
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : PDDL 2.1
 Durative actions
Action
duration
Start
Conditions
at start
End
Effects
at start
Conditions
at end
Invariant
38
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Effects
at end
State of the Art
Problem Modeling : PDDL 2.1
 Durative actions
(:functions (free-engineers) )
(:action TestWebSite
:parameters ( )
:duration (= ?duration 3)
:condition (and (at start (>= (free-engineers) 2)))
:effect (and (at start (decrease (free-engineers) 2))
(at end (increase (free-engineers) 2))
(at end (website_tested))))
39
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : BTPL
 Basic Temporal Planning Language [Brenner 2001]
40

Extension of PDDL. Focus on time and concurrency.

Whereas PDDL2.1 represents an action with two events
(start and end), BTPL allows for more complex actions
involving several events

No relative changes on numerical attributes
(increase/decrease) as in PDDL2.1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : BTPL
 A BTPL ground action is a tuple a=(pre, eff) where

pre are preconditions (set of literals)

eff = {ue1,..,uen} is a set of unit events of the form
ue=(c,e,d) describing the (conditional) effects of A
 d: delay (rational number)
 c: condition of ue: set of literals to be satisfied at t+d
 e: effect of ue: add/delete list occurring at t+d
pre
A
c1
d1
d2
41
ue1 e1
c2
ue2 e2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : BTPL
 Example: ATM cash dispenser
(card_in ?y)
DialCode(?x)
(code_ok ?x ?y)
5
(cash-out)
(ticket)
7
not (cash-out)
not(card_in ?y)
10
(cash-out)
InsertCard(?y)
TakeCash()
(card_in ?y)
1
42
1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
not(cash-out)
(have_cash)
State of the Art
Problem Modeling : BTPL
 BTPL extension

Allow expressing action preconditions (pre) and event
conditions (c) that hold over time intervals [t1,t2) before
the action or event time-point.
pre: (p,d1,d2)
t-d1
t-d2
t
A
c: (q,d3,d4)
t’-d3
t’-d4
ue e
d
43
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
t’=t+d
State of the Art
Problem Modeling : parcPLAN
 parcPLAN

[Lever&Richards 1994, ElKholy&Richards 1996]

Rich temporal expressivity based on time-intervals
whose extremities are time-point variables
E.g.: position(robot,r1)@(t1,t2)

Expression of minimal/maximal delays between time
points
E.g.: t1+5  t2

44
Handle unary and discrete resources, no reservoir
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : parcPLAN
 Web-site project example
action develop(?website)@(start,end) {
conditions:
designed(?website)@(t1,t2),
implemented(?website)@(t3,t4),
tested(?website)@(end,t);
effects:
developped(?website)@(end,t);
constraints:
designates(?website, WEBSITE),
start <= t1 <= t2 <= t3 <= t4 <= end <= t,
end <= start + 18;
}
45
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : parcPLAN
 Web-site project example
action test_in_company(?website)@(start,end){
effects:
tested(?website)@(end,t);
resources:
requires(engineers(),2)@(start,end);
constraints: designates(?website, WEBSITE),
end <= t, end = start + 3;
}
action test_outsource(?website)@(start,end){
effects:
tested(?website)@(end,t);
constraints: designates(?website, WEBSITE),
end <= t, end = start + 4;
}
46
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : IXTET
 IXTET [Ghallab&Laruelle 1994, Laborie&Ghallab 1995]
is a temporal and resource planner
47

From IndeXed TimE Table

State of the world is represented by a set of valued
attributes (state variables)

Relies on time-points as elementary temporal primitives

Allow representation of unary, discrete and reservoir
resources
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : IXTET

State of the world is represented by a set of valued
attributes (state variables)
E.g.: color(car):red
position(robot):r1

Conditions are expressed over time intervals
E.g.: hold(position(robot):r1,(t1,t2))

Change is represented via the notion of event
associated with a time-point
E.g.: event(position(robot):(r1,r2), t)
48
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : IXTET

Minimal/Maximal delays can be expressed between
time-points
E.g.: t in [0, 12]
t2-t1 in [3, 5]

Unary and discrete resources can be used over timeintervals
E.g.: use(engineers():2, (t1,t2))

Reservoir can be produced/consumed at time-points
E.g.: consumes(money():100,t)
49
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : IXTET
 Web-site project example
 IXTET
operators are called task
task develop(?website)(t) {
?website in WEBSITES;
timepoint t1, t2;
hold(status(?website):designed, (t1,t2));
hold(status(?website):implemented, (t2,t));
hold(status(?website):tested, (t,end));
start <= t1 <= t2 <= t <= end;
(end - start) in [0,18];
}
50
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : IXTET
 Web-site project example
task test_in_company(?website)(start, end){
?website in WEBSITES;
event(status(?website):(?, tested), end);
uses (engineers():2, (start,end));
(end - start) in [3,3];
}
task test_outsource(?website)(start, end){
?website in WEBSITES;
event(status(?website):(?, tested), end);
consumes (money():100, start);
(end - start) in [4,4];
}
51
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : IXTET
 Web-site project example

The problem is modeled in the same way as a task
resource money() { capacity = 200; }
resource engineers { capacity = 5; }
task init()() {
timepoint t;
explained event(status(website1):(?, init), start);
explained event(status(website2):(?, init), start);
explained event(status(website3):(?, init), start);
develop(website1)(t);
develop(website2)(t);
develop(website3)(t);
start <= t <= end;
t - start in [0,16];
}
52
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : IXTET
 Web-site project example
resource money() { capacity = 200; }
resource engineers { capacity = 5; }
task init()() {
timepoint t, u;
explained event(status(website1):(?, init), start);
explained event(status(website2):(?, init), start);
explained event(status(website3):(?, init), start);
develop(website1)(t);
develop(website2)(t);
develop(website3)(t);
start <= t <= end;
t - start in [0,16];
uses(engineers():1, (u,end)); // One quality engineer only
u-start in [7,7];
// available first week
}
53
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : O-Plan
 O-Plan
54

[Currie&Tate 1991, Drabble&Tate 1994]

Open PLANning architecture

Hierarchical planning system

The language (Task Formalism) allows a rich
representation of time and resources
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : O-Plan
 Web-site project example

Actions have conditions and effects and can be refined
into sub-actions thanks to schemas
schema develop_website;
vars ?website = ?{type websites};
expands {develop ?website};
nodes 1 action {design ?website},
2 action {implement ?website},
3 action {test ?website};
orderings 1 -> 2, 2 -> 3;
time_windows duration self = 0 .. 18 months;
end_schema;
55
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : O-Plan
 Web-site project example
schema test_website_in_company;
vars ?website = ?{type websites};
expands {test ?website};
conditions only_use_if {free_engineers} = true;
effects {free_engineers} = false at begin_of self,
{free_engineers} = true at end_of self;
time_windows duration self = 3 months;
end_schema;
schema test_website_outsource;
vars ?website = ?{type websites};
expands {test ?website};
resources consumes {resource money} = 100 kE;
time_windows duration self = 4 months;
end_schema;
56
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : O-Plan
 Web-site project example

The problem is modeled in the same way as a goal
schema
task todo;
nodes 1 start,
3 action {develop site1},
4 action {develop site2},
5 action {develop site3},
2 finish;
orderings 1 -> 3, 1 -> 4, 1 -> 5, 3 -> 2, 4 -> 2, 5 -> 2;
resources consumes {resource money} = 0 .. 200 kE overall;
time_windows 0 at begin_of 1,
16 at end_of 2;
end_task;
57
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : O-Plan
 Time




Precedence between actions
Minimal/maximal action duration
Time windows for events
Minimal/maximal delays between events
Action
dmin
dmax
Schema
58
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : O-Plan
 O-Plan Resource Typology
Unary
Resource
Consumable
59
Strictly
Producible
By-Agent
By and
Outwith
Agent
Discrete
Reusable
Non-Sharable
Outwith
Agent
Reservoir
Sharable
Independently
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Synchronously
State of the Art
Problem Modeling : O-Plan
 Resource usage

Consumable/Producible resource
schema <SCHEMA>;
resources consumes {resource <R>}= <q..Q> [at<EVT>];
resources produces {resource <R>}= <q..Q> [at<EVT>];

Reusable resources
schema <SCHEMA>;
resources allocates {resource <R>}= <q..Q> [at<EVT>];
resources desallocates {resource <R>}= <q..Q> [at<EVT>];
60
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 ASPEN
61

[Chien&al 2000]

Automated Scheduling and Planning ENvironment

The main ingredient of the model is the notion of
(hierarchical) activity types.

Numerical time

State variables

Numerical resources (unary, discrete, reservoir).
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 ASPEN

Example inspired from [McCarthy&Pollack 2002]

State variables: described as a set of possible
transitions
State_variable Position {
states = (“patio”,”dining”,…);
transitions = ( “patio”<->”dining”,
“dining”<->”kit”,
“dining”->”living”,
…);
default_state = “living”;
}
62
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 ASPEN

3 reasons for an activity to be inserted in the plan
Activity
Eat(breakfast)
Reservations:
State Variable: Position must_be kitchen

63
An activity requires a given state for a state variable
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 ASPEN

3 reasons for an activity to be inserted in the plan
Activity
Eat(breakfast)
[0,60]
Constraints:
ends_before start
of Take(medicine) by [0,60]
Activity: Take(medicine)

64
An activity express temporal constraint with another
activity of a given type
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 ASPEN

3 reasons for an activity to be inserted in the plan
Activity
DailyExercise()
Decompositions:
Exercise1()

65
Exercise2()
Exercise3()
An activity can be decomposed into sub-activities
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 Web-site project example
State_variable status {
states = { “init”, “designed”, “implemented”, “tested” };
transitions = {
“init” -> “designed”,
“designed” -> “implemented”,
“implemented” -> “tested” };
default_state = “init”;
}
Activity develop {
Website w;
duration = [0,18];
decomposition = { design with (w -> w) a1,
implement with (w -> w) a2,
test with (w -> w) a3,
where a1 ends_before start of a2,
a2 ends_before start of a3 };
}
66
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 Web-site project example
Activity test {
Website w;
decomposition = { test_in_company with (w -> w) or
test_outsource with (w -> w) };
reservations = { status(w) must_be “implemented”,
status(w) change_to “tested” at end; }
}
Activity test_in_company {
Website w;
duration = 3;
reservations = { engineers use 2; }
}
67
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : ASPEN
 Web-site project example
Activity test {
Website w;
decomposition = { test_in_company with (w -> w) or
test_outsource with (w -> w) };
constraints = { starts_after end of
implement with (w -> w) }
}
Activity test_in_company {
Website w;
duration = 3;
reservations = { engineers use 2; }
}
68
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : RAX-PS
 RAX-PS
69

[Jonsson&al 2000]

Interval based planner

No distinction between propositions holding over
intervals and actions taking place over intervals

Valued state-variables (same as IXTET or ASPEN)

Main ingredient is the notion of token: a given value for
a state variable holding over some time-interval
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : RAX-PS
 RAX-PS

Notion of time-line for a state variable v
Engine
Attitude
Idle
Turn(A,B)
Thrust(B)
Point(B)
Idle
Turn(B,C)
time

Token
tuple < v,
P(xP),
s,
< Attitude, Turn(A,B), 10,
70
e >
20 >
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : RAX-PS
 Each token T is associated a configuration constraint
GT called compatibility. This constraint determines
which other tokens must be present in a valid plan if
the plan contains T and how these tokens are
constrained with respect to T.
 Usually, GT is a disjunction of basic configurations
71
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Modeling : RAX-PS
 Example
(Define_Compatibility (ProjectStatus(?w) tested)
:compatibility_spec
(OR (met-by (ProjectStatus(?w) test_incompany))
(met-by (ProjectStatus(?w) test_outsource)))
(Define_Compatibility (ProjectStatus(?w) test_incompany)
:constraints
(?duration <- 3)
:compatibility_spec
(AND (equals (Engineers (+2 Used)))))
(Define_Compatibility (ProjectStatus(?w) test_outsource)
:constraints
(?duration <- 4))
72
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
Planning
Languages
Planners
Planning Techniques:
- Planning Graph
- SAT Planners and other encodings
- Heuristic Planning
- Local Search & Repair
- Partial Order Causal Link (POCL)
- Hierarchical Task Networks (HTN)
Basic Tools:
- Linear Programming (LP)
- Mixed Integer Linear Programming (ILP or MIP)
- Satisfiability (SAT)
- Constraint Satisfaction Problems (CSP)
73
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Linear Programming (LP)

Input: a set of variables, a system of linear inequations
and a linear objective to minimize
ai, j , b j , ci , xi  R
maximize
c
i
 xi
i
subject to
a
i, j
xi  b j
i, j

74
Output: a value for each variable that maximizes the
objective function
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Linear Programming (LP)

Example
maximize ( x  y  50 ) subject to
50 x  24 y  2400 , 30 x  33 y  2100 ,
x  45 , y  5

75
Optimal solution: x=45, y=6.25 (objective = 1.25)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Linear Programming (LP)
76

Efficient algorithms available using the Simplex method

Except for some pathological cases, the method
exhibits a polynomial complexity

Practical problems involving several hundred thousands
of variables can be solved

Many software and libraries available (freeware or
commercial e.g. ILOG CPLEX)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Mixed Integer Linear Programming (ILP/MIP)

Input: same as LP but some variable are constrained to
be integer
ai, j , b j , ci , x k  R ,
maximize
c
i
xl  Z
 xi
i
subject to
a
i, j
xi  b j
i, j

77
Output: a value for each variable that maximizes the
objective function
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Mixed Integer Linear Programming (ILP/MIP)

Example
maximize ( x  y  50 ) subject to
50 x  24 y  2400 , 30 x  33 y  2100 ,
x  45 , y  5 , y is integer

78
Optimal solution: x=45.12, y=6 (objective = 1.12)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Mixed Integer Linear Programming (ILP/MIP)
79

Problem is NP-hard ...

But fairly efficient approaches exist based the
cooperation of LP and a tree search.

Basic idea: relax the problem as a LP, solve it, if some
integer variable xl has non integer value vl, branch on
xl=[vl]  xl=[vl]+1

Survey paper: [Bixby&al 2000]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Satisfiability (SAT)
Boolean variables
Literal
Clause
Theory

P,Q,R,…
P,Q,…
(PQ),…
C1C2,…
true,false
(un)negated variable
disjunction of literals
conjunction of clauses
Satisfiability problem: is a given theory valid ?
That is, does it exist an assignment of all the boolean
variables in {true, false} such that the theory is true.

80
MAX-SAT: what is the maximum number of clauses that
can be satisfied.
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Satisfiability (SAT)

Example: (P  Q) (Q  R) (R  P)

A solution: P=Q=true, R=false
(P  Q) (Q  R) (R  P)
81
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Satisfiability (SAT)

Satisfiability is NP-complete

… but efficient methods exist
 Complete methods (Davis-Putnam procedure and its
improvements)
 Approximation methods (randomization and local search)
82

Can solve problems with thousands of variables

Survey paper: [Gent&Walsh 1999]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Constraint Satisfaction Problems (CSP)
Problem. Given:

A set of variables X={x1,…,xn}

A finite domain Di for each variable xi

A set of constraints Ci(xi1,…,xik) on some subset of
variables described in extension (subset of the cartesian
product Di1 …Dik satisfying the constraint) or in
intension (e.g. xi=min(xj,xk) )
Find an assignment of all variables in X that satisfies all the
constraints
83
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Constraint Satisfaction Problems (CSP)

Example:
Variables:
c  {blue, red}
x  {1,2,3,4}, y  {1,2,3,4}
Constraints:
(xy)
(x.y 10)
(c=blue) (x>y)

84
A solution: (x=1),(y=2),(c=red)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Basic Tools
 Constraint Satisfaction Problems (CSP)
85

Problem is NP-complete (SAT can easily be reduced to
a CSP on boolean variables)

Efficient resolution techniques using constraint
propagation and tree search

Survey papers: [Kumar 1992, Smith 1995]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
Planning Graph
SAT Planners
Heuristic Planning
GraphPlan
IPP
STAN
R-IPP
SAT-PLAN
[Rintanen&Jungholt 1999]
LPSAT
[Kautz&Walser 1999]
HSP
GRT
FF
GRT-R
Metric-FF
Sapa
TP4
LPG
Excalibur
ASPEN
Local Search
& Repair
POCL
HTN
86
SNLP
UCPOP
parcPLAN
IxTeT
RAX
UMCP
SHOP
Sipe-2
O-PLAN
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Graph
 Planning Graph [Blum&Furst 1997]

Planning Graph expansion
0
i-1
i
propositions
i+1
propositions
actions
87
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Graph
 Planning Graph

Mutex relations
Inconsistent
Effects
88
Interference
Competing
Needs
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Inconsistent
Support
State of the Art
Problem Solving: Planning Graph
 Planning Graph

89
Solution extraction
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Graph
 Planning Graph

Solution extraction
 Ad-hoc algorithm (GraphPlan)
 SAT encoding
 CSP encoding
90
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Graph
 Planning Graph


Some Planning Graph Planners
 GraphPlan
[Blum&Furst 1997]
 IPP
[Koehler&al 1997]
 STAN
[Long&Fox 1999]
SAT encoding
 SatPlan

91
[Kautz&Selman 1999]
CSP encoding
 CPLAN
[vanBeek&Chen 1999]
 GP-CSP
[Do&Kambhampati 2000]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: R-IPP
 R-IPP
IPP extension to resource constrained plans
92

[Koehler 1998]

GraphPlan based algorithm

The planning graph is annotated with possible interval
boundaries for resource level
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: R-IPP
 Resource r with possible level in [Qmin(r),Qmax(r)]
0
i-1
i
L(i-1,r)[Lmin(i-1,r), Lmax(i-1,r)]
93
i+1
L(i+1,r) ?
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: R-IPP
 Resource r with possible level in [Qmin(r),Qmax(r)]
L max ( i  1, r )  max(
L max ( i  1, r ),
No action affecting r is applied
i-1
94
i
i+1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: R-IPP
 Resource r with possible level in [Qmin(r),Qmax(r)]
L max ( i  1, r )  max(
L max ( i  1, r ),
{ l ( a ) / a action at level i setting amount of r to be l ( a ) }
L(r):=l(a)
i-1
i
i+1
An action a can set the
amount of resource to l(a)
95
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: R-IPP
 Resource r with possible level in [Qmin(r),Qmax(r)]
L max ( i  1, r )  max(
L max ( i  1, r ),
{ l ( a ) / a action at level i setting amount of r to be l ( a ) }
{ L max ( i  1, r )   p ( a ) / S non  exclusive
set of producers of level i } )
a S
i-1
i
i+1
A non-exclusive set of
action produces r
L(r)+=p(a)
96
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: R-IPP
 Similar calculations for Lmin(i+1,r)
 The classical notion of mutex is extended. Two actions
are mutex also if:
97

They are of different type w.r.t. a resource (consumer,
provider, producer)

They are provider of the same resource

Their combined effect is impossible

They have contradictory resource requirements
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: R-IPP
 Resource boundaries are used to
98

Restrict the number of applicable actions in a given
level

Allow detection of additional mutexes

Prune the search when solving the planning graph
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
 Planning with Resources based on SAT and/or
LP/MIP encodings
99

[Rintanen&Jungholt 1999]

LPSAT [Wolfmann&Weld 1999]

[Kautz&Walser 1999]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
 [Rintanen&Jungholt 1999] propose an approach
similar to R-IPP based on a SAT-encoding
10
0

Producers and Consumers can be executed in parallel

The search is not restricted to backward-chaining as in
the GraphPlan framework.
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
 LPSAT

Based on a SAT-encoding of the planning graph
[Ernst&al 1997]
i-1
i
i+1
Explanatory Frame Axioms:
At(P1,B,i-1)  At(P1,B,i+1)  SlowFlight(A,B,i)  FastFlight(A,B,i)
Actions effects and conditions:
SlowFlight(A,B,i) 
10
1
At(Plane,A,i-1) 
At(Plane,B,i+1) 
At(P1,A,i-1)
At(P1,B,i+1)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
 LPSAT

SAT extended by LCNF representation and solver:
propositional variables may trigger some linear
constraints [Wolfmann&Weld 1999]
(P  Q) (Q  R) (R  P)
P  (50x+24y2400)
Q  (30x+33y2100)
R  (x45)
10
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
 LPSAT

LCNF allows expression of resource requirements
i-1
i
i+1
Resource requirements:
SlowFlight(A,B,i) 
Refuel(i)

10
3
(Level(i-1) - Level(i+1)= 15)
(Level(i+1)= 240)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
 [Kautz&Walser 1999] propose an ILP encoding
10
4

Actions a that consumes/produce a resource

One action that reset the resource to its maximal
capacity (refuel)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving
 [Kautz&Walser 1999] propose an ILP encoding
ri  1  ri  k i 
q
a
 ai 
a  Cons
q
a
 ai
ri  1  ri  k i 
a
 ai 
a  Cons
a  Prod
q
a
 ai
a  Prod
s i   a i  a  Prod  Cons
s i  a i  1  a  Prod  Cons
s i  ( ri  1  Q MAX )
ri  1  s i  Q MAX  0
 si  ( k i  0 )
s i  M  k i  0 , M such that k i  M
Q MIN  ri 
q
a
 ai
Q MIN  ri 
Q MAX  ri 
q
a  Prod
q
a
 ai
a  Cons
a  Cons
10
5
q
a
 ai
Q MAX  ri 
q
a  Prod
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
a
 ai
State of the Art
Problem Solving: Heuristic Planning
 Heuristic Planning

Forward or backward state planning

Use of an efficient heuristic h(s)
Heuristic cost: h(s’)
s’
Initial
state
Cost of
current plan:
g(s)
10
6
Goal
s
Candidate
actions
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Heuristic Planning
 Heuristic Planning

In HSP, the heuristics h(s) is computed by solving a
relaxed problem where all the delete lists of actions are
ignored.

s: state, p: proposition, cs(p) estimation of the cost for
achieving p from state s
cs ( p ) 
{
if ps
min op O ( p ) 1  c s ( Prec ( op ))  otherwise
0
HSP heuristics (non-admissible): h ( s ) 
c
p  Goal
10
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
s
( p)
State of the Art
Problem Solving: Heuristic Planning
 Some heuristics planners
10
8

HSP
[Bonet&Geffner 1999,2001]

GRT
[Refanidis&Vlahavas 1999]

FF
[Hoffman&Nebel 2001]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Heuristic Planning
 Heuristic Planning with Resources
10
9

GRT-R
[Refanidis&Vlahavas 2000]

Metric-FF
[Hoffman 2002]

Sapa
[Do&Kambhampati 2001]

TP4
[Haslum&Geffner 2001]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: GRT-R
 GRT-R: Heuristic planner handling consumable
resources in the heuristics
Heuristic cost: h(s’)
<N=2, R1=5, R2=1>,
<N=3, R1=2, R2=3>
Q1=10, Q2=10
s’
Initial
state
s
<N=1, R1=6, R2=2>
Cost of
current plan:
<N=2,R1=5,R2=4>
11
0
Candidate
actions
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Goal
State of the Art
Problem Solving: GRT-R
 The heuristic with resource allows guiding and pruning
the search
 The heuristics h(s) is computed by regression from the
goal state toward state s
 Issues: complexity in time and memory for computing
the sets of cost vectors
111
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Metric-FF
 Metric-FF. Extension to FF [Hoffmann&Nebel 2001]
 Reminder: FF is a forward search heuristic planner. At
a given state s, the heuristics h(s) is estimated by
solving a relaxed problem that ignores the delete lists
of operators. This is done in GraphPlan style.
Heuristic
cost: h(s’)
Initial
state
s
Cost of
current plan:
g(s)
11
2
Solve
relaxed
problem
s’
Candidate
actions
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Goal
State of the Art
Problem Solving: Metric-FF
 Metric-FF restricted formalism

Conditions: q>C, qC

Effects: q+=C (production), q-=C(consumption)
 Metric-FF idea: on a resource, something similar to
ignoring the delete list is to ignore consumption and
only consider production events (monotonicity).
 Monotonicity: each proposition true at level i in the
planning graph remains true at any level j  i
11
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Metric-FF
 As for FF

Finding a solution to the relaxed problem is polynomial
(because of the monotonicity)

Finding the shortest solution to the relaxed problem is
NP-complete.
 A (good) solution to the relaxed problem is computed
using similar techniques as in R-IPP
 The value of the heuristic is the number of operators in
this solution
11
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Metric-FF
 The notion of monotonicity is very generic
 Extended Metric-FF formalism

Conditions:
linear expressions {<.,=,,>} linear expression

Effects:
{:=, +=, -=} linear expression
 Transformed into a simpler Linear Normal Form
language where a monotonic relaxation is applied
11
5
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Sapa
 Sapa. Heuristic Metric Temporal Planner
 Focus on durative actions: action A, duration D(A)
 Notion of time stamped state
cj
Predicates
true at t
ti
tj
Persistent conditions
to be protected
pi
Scheduled events:
- Ends of persistent condition
Resource
levels at t
- Change truth value of a predicate
- Change a resource
Past t Future
11
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Sapa
 Notion of applicable action
 Result of applying an action to a state
A
cj
Predicates
true at t
ti
tj
Persistent conditions
to be protected
pi
Scheduled events:
- Ends of persistent condition
Resource
levels at t
- Change truth value of a predicate
- Change a resource
Past t Future
11
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Sapa
 Heuristic planning
Heuristic cost: h(s’)
s’
Initial
state
Goal
s
Cost of
current plan:
g(s)
Candidate
actions
 The heuristics relies on solving a relaxed problem
where delete lists and resources are ignored using
GraphPlan like techniques
11
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Sapa
 In the relaxed problem

Delete lists and Resource usage are ignored
Partial
Plan
Relaxed planning graph
Approximation of the
distance from the goal
FastFlight(A,B) Deplane(P1,B)
Deplane(P1,A)
Board(P2,B)
Deplane(P2,C)
Board(P1,A)
SlowFlight(A,B)
Deplane(P1,C)
FastFlight(B,C)
SlowFlight(B,C)
sinit
11
9
s
Lower bound on the date P1 can be at C
(useful to prune the search)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Sapa
 In the relaxed problem, resources are used to adjust
the heuristics

For a resource R, pre-computation of the action AR that
can increase maximally the level of R (of a level R)

Init(R): initial level of R at state s from which the relaxed
plan was computed. Con(R) and Pro(R) are the total
consumption and production of R in the solution of the
relaxed plan.

If Con(R)>Init(R)+Pro(R), we know that at least
Con ( R )  ( Init ( R )  Pro ( R ))
R
additional actions to produce R will be necessary
12
0
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: TP4
 Similar approach used in TP4
 But the planner is a regression planner, starting from
the goal
12
1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Planning with Resources
Part II: Focus on Constraint-Based
Approaches
Overview
Planning with Resources
 Part II. Focus on Constraint-Based Approaches

Reminder: POCL and HTN Planning

Constraint-Programming

Problem Modeling

Problem Solving
 Constraint Propagation
 Search
12
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Partial-Order Causal-Link Planning (POCL)

Search in a space of partially-ordered plans

Iteratively selects some flaw of the current partial plan
and attempt to fix them until there are no more flaw
(solution plan)

Flaws:
- unachieved preconditions
- threads on causal links
12
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Partial-Order Causal-Link Planning (POCL)

Unachieved preconditions
Insert a new action and a causal-link OR
w
p
p
Initial
q
state
q
s
s
q
q
r
v
r
12
5
u
u
Goal
v
p
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Partial-Order Causal-Link Planning (POCL)

Unachieved preconditions
Insert a causal-link with an existing action
p
Initial
q
state
q
s
s
q
q
r
v
r
12
6
u
p
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
u
Goal
v
State of the Art
Problem Solving: Planning Techniques
 Partial-Order Causal-Link Planning (POCL)

Threads on causal-links
p
p
Initial
q
state
q
s
s
u
p
p
r
v
r
u
Goal
v
p
Fixes: action promotion OR demotion
12
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Partial-Order Causal-Link Planning (POCL)

Threads on causal-links
p
p
Initial
q
state
q
s
s
u
p
p
r
v
r
u
Goal
v
p
Fixes: action promotion OR demotion
12
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Partial-Order Causal-Link Planning (POCL)

Threads on causal-links
p
p
Initial
q
state
q
s
s
u
p
p
r
v
r
u
Goal
v
p
Fixes: action promotion OR demotion
12
9
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Partial-Order Causal-Link Planning (POCL)

13
0
Some POCL planners
 SNLP
[McAllester&Rosenblitt 1991]
 UCPOP
[Penberthy&Weld 1992]
 IXTET
[Ghallab&Laruelle 1994]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Hierarchical Task Networks (HTN)

Hierarchical Operators (see O-PLAN)
Task T(x1,…xn)
Method 1
precondition: p
q
Method 2
precondition: v
q
s
r
13
1
s
r
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Hierarchical Task Networks (HTN)

HTN Planners work by iteratively
- expanding tasks (choose a method) and
- resolving conflicts
until a conflict-free plan can be found which consists
only of primitive tasks

Most of industrial applications of AI Planning use the
HTN approach
 Provides a strong structuration of the domain to
efficiently guide the search
13
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
State of the Art
Problem Solving: Planning Techniques
 Hierarchical Task Networks (HTN)

Some Partial-Order HTN Planners
 SIPE-2
[Wilkins 1988]
 O-Plan
[Currie&Tate 1991]
 UMCP
[Erol&al 1995]

Often based on constraint propagation [see later]

Some Forward-Chaining HTN Planners
 SHOP
13
3
[Nau&al 1999]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving: Planning Techniques
 Partial-order approaches to planning (POCL, HTN)
are recognized to be the most flexible for handling
time and resources [Smith&al 2000]
 Partial order planning is receiving more and more
attention [Nguyen&Kambhampati 2001,Geffner 2001]
13
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving: Planning Techniques
 In partial order planning, from the point of view of
resources, a partial plan is a temporal network of
activities that require/produce/consume some
resources.
 It’s essentially the same as in constraint-based
scheduling
13
5
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming
 Constraint-Based Scheduling =
Scheduling + Constraint Programming
 Scheduling problems arise in situations where
a set of activities has to be processed
by a limited number of resources
in a limited amount of time
13
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming
 Paradigm to solve combinatorial optimization
problems
 One states the problem in terms of variables and
constraints after which, a search procedure is used
to find a solution
13
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming
 Each variable has an initial domain of possible
values ( x  [0,…,4] )

Constraints propagate to reduce domains
“x < 3”  x  [0,…,2]
13
8

Each constraint has its own propagation algorithm
(reusable)

As propagation isn’t sufficient, a search tree is build
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming
decision making
new constraints
backtracking
Dec. vars: x in [1..3]
y in [1..3]
z inDefinition
[1..3]
Problem
Constraints: x - y = 1
y<z
Search
y=2
[1..3]
Dec.
Dec. vars:
vars: xx in
= 3[2..3]
[1..3]
yy in
= 2[1..2]
zz in
[1..3]
[2..3]
Variables,
= 3Domains,
Constraints:
=1
and Constraints
Constraints:
xx -- y
y=
1
y
<
z
y<z
y=2
initial variables, constraints,
and domains
reduce domains, deduce constraints,
contradictions
13
9
Constraint
x y- y<Propagation
=z 1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
problem
specification
partial
solution
Constraint-Based Approaches
Constraint-Based Scheduling
[Baptiste&al 2001]
Problem Definition
Modeling Objects:
Activities, Resources,
Temporal Constraints,
Resource Demands
14
0
Search
Scheduling
Strategies
Problem Specification
/ Partial solution
Constraint
Propagation Resource
Demands, Temporal
Constraints
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming : Properties
 Besides the separation of problem definition,
constraint propagation, and search, the Locality
Principle [Steele 1980] is important: each
constraint must propagate as locally as possible,
independent of the existence or non-existence of
other constraints.
 [Stallman&Sussman 1977] separation between
deductive methods (constraint propagation) and
search
 [Kowalski 1979] distinction between logical
representation of constraints and the control of
their use: Algorithm = Logic + Control
14
1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming
 Global Constraints

One of the strong points of CP tools are the so called
global constraints (Opposed to constraints like x < y.)

Example is the “all-different” constraint where you have
n variables which all should take a different value:
 i , j  [1,..., n ] / i  j , ( x i  x j )
14
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming
V11
V12
V10
V2
V9
V3
V8
V4
V7
14
3
O(n2) binary constraints
Weak constraint propagation
V1
V6
V5
One global constraint
(Easier modeling)
Strong constraint propagation
[Regin 1994]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming : Search
 Search Heuristics
 Variable and value selection heuristics.
 Choose variable to assign a value to and then choose a
value for this variable (instantiate the variable).
 Typical strategy
 Choose most constrained variable, i.e., a variable that is difficult
to instantiate; start with the difficult parts (this before they get
even more difficult).
 Choose least constraining value, i.e., a value that leaves as
many values as possible for the remaining uninstantiated
variables.
14
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming : Search
 Variable selection heuristics
 choose variable with smallest remaining domain
 choose variable with maximal degree in constraint
graph (most constraints defined on it)
14
5
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming : Search
 Value selection heuristics
 choose value that participates in highest estimated
number of solutions. Number of solutions are estimated
by counting the solutions to a tree-like relaxation or the
original constraint graph.
 choose minimal value
 Recall: In general decisions correspond to
additional constraints.
14
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming : Search
 Search Tree Exploration
 Depth First Search (DFS). The traditional search
strategy of CP.
 Best First Search (BFS). Choose the node with the best
minimum cost.
 Limited Discrepancy Search (LDS). Divides the search
tree into strips, trying to stick close to the heuristic.
 … and several others like Depth-Bounded Discrepancy
Search, Interleaved Depth-First Search.
14
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Constraint Programming : Search
 Optimization
 In case an objective function is present, one tries to find
the best solution. Such optimization can be done in
several ways
 When a solution with cost c is found, restart search to find
a solution with cost c-1.
 Do dichotomization. Besides upper bounds coming from
solutions, when being complete one can also calculate
lower bounds.
 When a solution with cost c is found, stay in this solution
node, add a “cut” that says the cost needs to be at most
c-1, and continue search.
14
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling
 Scheduling is the “problem of allocating scarce
resources to activities over time” [Baker 1974]
 Typology of
14
9

Activities

Temporal constraints

Resources
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Activities
 Non-preemptive activities
Activity A
t
Start time: s(A)
End time: e(A)
Processing time: p(A) == e(A)-s(A)
1 Activity  3 numerical Variables
15
0
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Activities
 Notations on current domain of activity time
window
Activity A
smax(A)
smin(A)
15
1
emax(A)
t
emin(A)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Activities
 Preemptive activities
p1
Start time: s(A)
Activity A
...
pi
t
End time: e(A)
Processing time: p(A) =  pi  e(A)-s(A)
15
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Activities
 Preemptive activities

Preemption at fixed dates (break calendar)
p1
Activity A
... pi
t
M T W T F S S M T W T F S S M T W T F S S M T W T F S S M T W T
Processing time: p(A) =  pi = e(A)-s(A) - breaks(A)
1 Activity  3 numerical Variables
15
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Activities
 Preemptive activities

Preemption by other activities
p1
Activity A
... pi
Activity B
t
Activity C
1 Activity  1 Variable Set of dates
15
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling: Temporal constraints
 Generally expressed as ti - tj [dmin, dmax] where
 ti, tj

: start or end time point of some activities
dmin, dmax: minimal and maximal delay
 Generic enough to model
15
5

release dates:
start(A)  [r,+)

deadlines:
end(A)  (-,d]

precedence:
start(B)-end(A)  [0,+)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling: Temporal constraints
 Simple Temporal Problem (STP)
[Dechter&al 1991]
 Distance Graph representation
dmax
tj
ti
-dmin
15
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling: Temporal constraints
 Arc consistency ( Single Source Shortest Paths)
ensures a backtrack-free search

n=#time-points, p=#temporal constraints

Memory: O(p)

Time: O(n.p) (with negative cycle detection)
 Path consistency ( All Pairs Shortest Paths)
15
7

Memory: O(n2)

Time: O(n2)

Provides all pairs distances (useful for heuristics)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Resource Usage
 Resource quantities q(U) are decision variables
 The same activity may use several resources
U1: A requires Machine1
A
U2: A requires(q2) Workers
U3: A consumes(q3) Memory
15
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Resource Usage
 Resource usage follow the “constraint protocol”
 In particular, they can be used in meta-constraints
[A requires Machine1] 
[A consumes(q2) Memory]  [B requires(q3) Workers]
15
9
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Decision Variables
 Start, end and processing time of activities:
s(A), e(A),p(A)
 Required quantities of resources:
q(U)
 From the standpoint of constraint-programming,
the limited capacity of resources imposes some
global constraint on the decision variables of the
problem
16
0
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Objective functions
 Often the objective is to minimize a function
f(e(A1),…,e(An))

Makespan: f = max(e(Ai))
 Total weighted flow time: f =  wi.e(Ai)
 Maximum tardiness: f = max(Ti); Ti=max(0,e(Ai)-di)
 Total weighted tardiness: f =  wi.Ti
 Total weighted number of late jobs: f =  wi.Ui
 Earliness/Tardiness costs
16
1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Objective functions
 Other common objective functions
16
2

Minimum transition costs

Minimum peak resource usage

Schedule maximum weighted # of activities

Schedule on a minimum weighted # of resources
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Modeling : Scheduling Problem
 Given:

A set of resources

A set of activities

A set of temporal constraints on/between activities

A set of resource usage
 An objective function f
 Find an instantiation of the decision variables that
16
3

satisfies all the constraints and

minimizes f
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving
 A.I. Planning and Scheduling techniques start to
converge into a “POPS” (Partial Order Planning
and Scheduling) concept
16
4

Partial Order Planning is “Reviving”

“Partial Order Scheduling” is most of what ConstraintBased Scheduling is about
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving
 POP and POS work on the same type of structure:
a temporal network of operators/activities

POP focus on operator/activity generation constraints

POS focus on time and resource constraints
 The fundamental idea is that in both case, a
solution plan or a solution schedule can be
characterized by a set of local properties
 These local properties can be enforced by
constraint propagation and/or by branching in the
search tree
16
5
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving
 Example of such a local property in POP: The
Necessary Truth Criterion [Chapman,87]
Clobberer:
-free(A)
Establisher:
+free(A)
White knight:
+free(A)
Pre: free(A) ?
16
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving
 In what follow, we identify the local properties that
are used in Constraint-Based Scheduling to
characterize solution schedules and describe
1. the propagation and
2. the branching schemes
based on these local properties
16
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving : Global Constraints
 What’s happening inside ?

Key principle is that a resource knows the set of
activities that requires it (start, end, processing time)

For instance a unary resource takes care of the
n ( n  1) 2 disjunctive constraints of the form
e ( A )  s ( A ' ), or
e( A' )  s( A)
16
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving : Global Constraints
 What’s happening inside ?
16
9

When adding an activity requiring a resource, the
resource automatically takes care of the relations with
all other activities requiring the same resource

Remark: One can add activities during search

Note however that sometimes you need to know that all
the activities that will require the resource are known to
do any propagation
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving : Global Constraints
 What’s happening inside ?

We have several types of constraints that all make sure
the capacity of the resource is not exceeded at any
point. These constraints differ in the strength of the
propagation they induce:
 timetables
 precedence energy
 disjunctive constraint
 balance constraint
 edge-finding
17
0

In general: more propagation = more effort

These constraints are global constraints, they “globally”
consider the set of activities on a resource
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving : Global Constraints
 Different algorithms available to propagate
resource capacity (timetable, disjunctive, edgefinder, balance, etc.)
 Several algorithms may be used in cooperation on
the same resource
 A resource knows the set of activities that uses it
 As soon as something changes on the resource
(change of activity start/end/processing time, change
of resource demand, new resource usage added),
propagation algorithms are triggered
17
1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving : Global Constraints
 A resource is said to be closed if no additional
resource usage will be inserted into the current
schedule lower in the search tree
 When a resource is closed, stronger propagation
can be inferred
LINIT=0
17
2
+q -q
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Problem Solving : Global Constraints
 In mixed A.I. Planning & Scheduling, a resource
can be considered closed if for example :

No operator use this resource; or
 In hierarchical planning, it corresponds to an already
processed abstraction level; or
 The decision has been taken to close the resource on
the current sub-tree :
close R
insert an operator using R
Forbid insertion of
any operator
using R. Stronger pruning.
17
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Time-tabling [LePape 1994]

Interesting activities A are those for which
emin(A) > smax(A).
s max
s min

17
4
e max
e min
Between smax(A) and emin(A) we know A will be
executed.
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
s max
s min
Q
e max
e min
q
Aggregated necessary demand
QMAX
t
17
5
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
e max
s max
s min
Q
s min
e min
e min
Aggregated necessary demand
QMAX
t
17
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Time-tabling
17
7
C()

E()
 Time Bounds

 Precedence
 Level

 Energy
 Time Bounds

 Precedence
 Not First/Last
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Time-tabling
17
8

Used for large problems

Worst case O(n) algorithm

Incremental

Smart about when to propagate and when not, group
propagation, etc.

In practice a very fast algorithm
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Disjunctive constraint

Considers pairs (A, B) of activities

If two activities can not overlap because of the capacity
they require, and one, say A, can not be scheduled
before the other, then
 New time bounds are deduced
 A new precedence constraint is deduced
17
9
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Disjunctive constraint on unary resource
[Erschler 1976]
A
s max
e max
s max
A

e min
s min
B
e max
s max
e min
s min
e max
e max
s max
B
s min
e min
s max ( A )  e min ( B )
s min
e max ( A )  s max ( B )
e min ( A )  s min ( B )
18
0
e min
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Disjunctive constraint
18
1
C()

E()
 Time Bounds

 Precedence
 Level

 Energy
 Time Bounds

 Precedence

 Not First/Last
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Disjunctive constraint
18
2

Works on unary, discrete, and state resources

More propagation than timetable constraint on unary
resources

Low memory cost

Needs fake activities to cope with resources not
available at certain times

Algorithm : O(n2)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Edge-Finding
 [Carlier&Pinson
 [Nuijten
1990]
1994]
 [Baptiste&LePape
1995]
 Detecting First Among n Activities on Unary
Resource
  ,  A , [ e max (   { A })  s min (  )  p (  )  p ( A )]  [ A   ]
18
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Edge-Finding
B p=4
B p=4
C p=5
18
4
7
A
A
4
p=2
C p=5

15
7
16
6
16
6
16
4
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
15
Constraint-Based Approaches
Algorithms based on time windows
 Similar reasoning for detecting Last, Not First, Not
Last with respect to a set 
 Edge-Finding can be extended to discrete
resources [Nuijten 1994, Baptiste&LePape 1996]
18
5
C()

E()
 Time Bounds

 Precedence
 Level
 Energy

 Time Bounds

 Precedence

 Not First/Last

PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 Energetic Reasoning [Erschler&al 1991]
 Discrete resource:  {A,B}  Acts,
[Q MAX .( s min ( B )  e max ( A ))  W ( A )  W ( B ) 
W
C  { A ,B }
 [ s ( A )  e ( B )]
18
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
[ s min( B ), e max( A ))
(C ) ]
Constraint-Based Approaches
Algorithms based on time windows
 Energetic Reasoning
6
C1 p=1
1
2 C2
6
16
C2
p=3
5
15
A

4
p=4
4
6
18
7
p=3
15
A
12
4
p=4
B
B
p=4
16
5
16
4
C1 p=1
16
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
p=4
16
Constraint-Based Approaches
Algorithms based on time windows
 Energetic Reasoning
18
8
C()

E()
 Time Bounds

 Precedence
 Level
 Energy

 Time Bounds

 Precedence

 Not First/Last

PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on time windows
 More Propagation based on time windows
18
9

Preemptive resource constraints: mixed edge-finding
[LePape&Baptiste 1998]

Activity cannot be nth [Nuijten&LePape 1998]

Energetic reasoning [Baptiste&al 1999]

Multi-machine propagation [Sourd&Nuijten 2000]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Algorithms based on analyzing time bounds of
activities propagate few (or even nothing) when
the problem is not tight
 Example: On discrete resources, for the time-table
constraint, if for all activity of the schedule:
emax - smin  2.pmin, the time-table constraint
propagates nothing
smax
smin
19
0
emin
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
emax
t
Constraint-Based Approaches
Algorithms based on relative positions
 These propagation algorithms do not directly take
into account precedence relations (but only
through their effect on time bounds)
 In PO Planning
 Time bounds of operators are loose
 Extensive usage of precedence relations between
operators in the partial plan
 Traditional resource propagation algorithms do
not prune the search space enough
19
1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Example: Blocks world. Limited number of hands (2)
modeled as a reservoir of capacity 2 and initial level 2
-1
+1
-1
-1
+1
19
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
+1
Constraint-Based Approaches
Algorithms based on relative positions
 Analyze precedence relations on the left side of
the propagation rule (C())
 Based on a Precedence Graph that collects and
maintains precedence relations between activities:
 Initial statement of the problem
 Precedence constraints inside a planning operator
 Search decisions (e.g.: causal link, threat, ordering
decision on resources)
 Discovered by propagation algorithms (disjunctive
constraint, edge-finding, energetic reasoning, emaxsmin).
19
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Precedence Graph
 Events x=(tx,qx) where the availability of a resource
changes
 Arcs : Two kind of arcs: tx<ty and tx ty
+2
+2
-2
+2
[-10,-5]
-1
Activity
{
Arc {
Event
Production
Consumption
<

 Transitive closure is incrementally maintained
19
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Partition for an event x in a precedence graph
U(x)
B(x)
BE(x)
BS(x)
19
5


x

E(x)
A(x)
AE(x)


AS(x)
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Energy Precedence Propagation [Laborie 2001]

Does not assume the resource to be closed

For any solution:
 X  U ,    B ( X ),
s ( X )  min ( s (Y ))   ( q (Y ). p (Y )) / Q MAX
Y 

19
6
Y 
In a partial schedule, we can decline this property to
perform constraint propagation
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Energy Precedence Propagation [Unary,Discrete]
Discrete resource:  X  U,
[  B ( X )]  [ s min ( X )  min ( s min (Y ))   ( q min (Y ). p min (Y )) / Q MAX ]
Y 
Y 
QMAX=2
B p=4, q=2
B p=4, q=2
9
X
C p=4, q=1

E
E
D
0
19
7
p=2
q=1
X
C p=4, q=1
D
p=2
q=2
0
p=2
q=1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
p=2
q=2
Constraint-Based Approaches
Algorithms based on relative positions
 Energy Precedence Propagation
C()

E()
 Time Bounds
 Precedence

 Level
 Energy

 Time Bounds

 Precedence
 Not First/Last
Worst-case complexity: O(n2)
19
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Balance Constraint [Cesta&Stella 1997,Laborie 2001]

Assumption: when applied to a reservoir, all producers of
the reservoir are known in the current schedule

Local property: for a given event x in a solution schedule,
we can compute the level of the reservoir just before x at
date t(x)-e as:
  ( x )  L INIT 
 q(y )
y  BS ( x )
A schedule is a solution on the reservoir iff
 x  U , 0    ( x )  Q MAX

19
9
In a partial schedule, we can decline this property to
perform constraint propagation
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation

Given an event x, using the graph, we can compute   ( x )
an upper bound on the reservoir level at date t(x)-e
assuming:
 All the production events y that may be executed strictly
before x are executed strictly before x and produce their
maximal quantity q(y);
 All the consumption events y that need to be executed
strictly before x are executed strictly before x and
consume their minimal quantity q(y);
 All the consumption events that may be executed
simultaneously or after x are executed simultaneously or
after x
20
0
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
U(x)
AE(x)
BE(x)



x

BS(x)

20
1


E(x)
(x)  L
INIT

 p max ( y ) 
y B ( x )  U ( x )
AS(x)
 c min ( y )
y  BS ( x )
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation

Similar bounds can be computed:
 Lower bound on the reservoir level at date t(x)-e
 Lower/Upper bound on the reservoir level at date t(x)+e

For symmetry reason, we focus on

Given
(x)
(x)
, the reservoir balance algorithm discovers:
 Failures
 New bounds for required quantities of resources q(x)
 New bounds for time variables t(x)
 New precedence relations
20
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation
20
3

Discovering failures: As soon as:  x ,   ( x )  0 , no
solution exist that satisfy the precedence relations

Property: the rule [  x ,   ( x )  0 ]  [ fail ] is sufficient to
ensure the soundness of the search on a reservoir w.r.t.
the reservoir underflow.

A symmetrical property exists for reservoir overflow
based on   ( x ) .
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
LINIT=0
U(x)
[+1,+2]
[-1,-1]
[-2,-1]
[+1,+1]
E(x)
[+0,+10]
[+1,+3]
[-5,-5]
[-5,-5]
[-5,-4]
BS(x)
[+1,+1]
BE(x)
-(x)= 0 + (2+1+10+1) - (1+5+5+4) = -1 < 0 !!!
20
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation

Safe event: An event x is said to be safe if and only if
  ( x )  Q MAX ,   ( x )  Q MAX
  ( x )  0,   ( x )  0

20
5
Property: If all the events are safe, then any
instantiation of the time variable that satisfies the
precedence constraints also satisfies the reservoir
constraint. In other words, the current partial order is
safe and the reservoir is “solved”.
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation

Reservoir balance equation:
  ( x )  L INIT 

y  BS ( x )
y  BE ( x )  U ( x )
 q max ( y )  0
y  BS ( x )
It means that some events in BE ( x )  U ( x ) will have to
be executed strictly before x in order to produce at least:
 ( x )   L INIT 
20
6
 p max ( y )
In case the first part of the equation is such that:
L INIT 

 q max ( y ) 
 q max ( y )
y  BS ( x )
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation
events z  BE ( x )  U ( x ) will have to be
executed strictly before x in order to produce at
least  ( x )
 Some

Let
( z1 ,..., z i ,..., z n )
BE ( x )  U ( x )

the set of production events in
sorted by increasing minimal time
k
Let k be the smallest index such that:  p max ( z i )   ( x )
i 1

20
7
Then:
t ( zk )  t ( x )
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
LINIT=0
U(x)
[-2,-1]
[+1,+2]
[-2,-2]
[+2,+2]
[+1,+2]
[+0,+10]
[-5,-5]
[+1,+3]
[-5,-5]
[-5,-4]
BS(x)
[+1,+2]
BE(x)
(x)= 0 - (2+10) + (2+5+5+4) = 4
20
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
E(x)
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation

In AI Planning applications, if some producers of the
reservoir may still be inserted in the partial plan:
transform the balance algorithm into a real truth
criterion:
 Some events z  BE ( x )  U ( x ) will have to be executed
strictly before x in order to produce at least  ( x )
OR
 Some operator containing a producing event z will have to
be inserted such that t(z) < t(x)

20
9
Such a “truth criterion” is described in [Laborie 2003]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Algorithms based on relative positions
 Reservoir Balance Propagation
C()

E()
 Time Bounds

 Precedence

 Level

 Energy
 Time Bounds

 Precedence

 Not First/Last
Worst-case complexity: O(n2) O(n3)
21
0
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Level-Based
O(n2)
O(n3)
Reservoir
Discrete
Timetabling
Unary
O(n)
Balance
O(n2)
EdgeFinding
Disjunctive
O(n log n)
O(n2)
O(n log n)
O(n2)
Time-Bounds analysis
21
1
Energy-Based
EnergePreced.
tic
Energy
Reason.
O(n3)
Precedence analysis
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
O(n2)
Constraint-Based Approaches
Search Techniques
 Branching Schemes
 Search Heuristics
 Beyond the Basic Search Scheme
21
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Branching Schemes
 Example of Branching Schemes :
21
3

Event Pair Ordering

Setting Times
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Branching Schemes
 Property : In a solution for a unary resource, all the
pairs of resource usage are ordered.
 Activity Pair Ordering (Unary Resource) :
Select a not-ordered pair of resource usages : (u,v)  U
 Branch on :
[e(u)  s(v)]  [e(v)  s(u)]
 Needs a precedence graph to maintain the sets of notordered pairs of resource usage

21
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Branching Schemes
 Property : On a capacity resource, a partial schedule
where all the events are safe is a solution.
 Event Pair Ordering (Discrete, Reservoir, etc.) :
21
5

Select a critical pair of events (x,y) on a resource R
(event = start or end time-point of an activity using R)

Critical Pair of events : not-ordered pair of event : (x,y)
such that neither x nor y is safe (in the sense of the
balance constraint)

Branch on :
[t(x) < t(y)]  [t(x)  t(y)]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Branching Schemes
 Property: in a solution on a discrete resource, there is
no Minimal Critical Sets.
 Minimal Critical Set Ordering

[Laborie&Ghallab 1995, Cesta&Oddi 2002]
 Select an MCS on a resource :
e1
s1
s2
s3

21
6
e2
e3
q1+q2+q3 > Q
q1+q2  Q
q1+q3  Q
q2+q3  Q
Branch on the resolvers of this MCS :
[t(e1) t(s3)]  [t(e3)  t(s1)]  [t(e3)  t(s2)]
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Branching Schemes
 All previous branching schemes are complete
 Setting Times (All resources) :

Select an activity a in the schedule
 Branch on : [s(a) = smin(a)]  [s(a) > smin(a)]
 Dominance rule relying on constraint propagation :
instead of posting [s(a) > smin(a)], activity a is marked as
non-selectable until its start time has been updated by
propagation.
21
7
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Search Heuristics
 Slack-Based Heuristics [Smith&Cheng 1993]

Choose a resource where the slack of any subset of
potentially conflicting activities on that resource is
minimal. Slack of a subset S is
 maxA  S (emax(A)) – minA  S (smin(A)) – sumA  S p(A)
 Sequence that resource / Take a sequencing decision on that
resource.

Choose pair of unsequenced activities with minimal
maximal slack. Maximal slack of A and B is
 max(emax(A) – smin(B), emax(B) – smin(A)) – p(A) – p(B).
 Choose sequencing that leaves maximal slack.
21
8
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Search Heuristics
 Texture-based Heuristics [Beck&al 1997]
21
9

Texture measurement: dynamic analysis of a search
state to reveal problem structure

Heuristic: based on the revealed structure, find “most
critical” part of the search state and take a decision to
reduce criticality

The texture measurement and the heuristic to take
decisions are separate.

Note: for efficiency reasons one might want to make
more than one decision before recomputing texture
measurements
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Search Heuristics
 Example of Texture-based Heuristics: SumHeight
Heuristic
22
0

Texture measurement: a probabilistic estimate of the
extent to which activities are competing for each
resource and time point (“contention”)

Find the most critical (highest contention) resource and
time point

Take a decision to reduce contention
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Search Heuristics
 The SumHeight Texture Measurement: Individual
Demand
time
smin
22
1
emin
smax
emax
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Search Heuristics
R2
R2
22
2
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
R2
time
Constraint-Based Approaches
Search Heuristics
 The SumHeight Decision

Find the resource, R*, and time point, t*, with highest
contention

Find the 2 activities not sequenced with each other with
the highest individual demand for R* at t*

Post a precedence constraint between them

Complexity:
 R = # resources, n = # activities per resource
 O(R.n.log(n)) for texture calculation
 O(n2) for finding decision after texture calculation
22
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Beyond the Basic Search Scheme
 Shaving [Torres&Lopez 2000]

Perform some kind or forward checking that exploit the
interactions between resources

Use some global propagation algorithms to determine if
there exist a schedule that verify a property p
 E.g. Try posting A  B on a unary resource ...

If no solution schedule verify p then p must be verified
in any solution. Thus it can be inferred.
 … if global propagation algorithms fail, then infer the opposite
constraint B  A
22
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Beyond the Basic Search Scheme
 Shaving. Example of application: Time-Bound
Shaving

Activity A, Select  such that emin(A)    emax(A)
 If propagating e(A) <  leads to a dead-end: infer   e(A)
 If propagating e(A) >  leads to a dead-end: infer   e(A)

Perform a dichotomic search on [emin(A), emax(A)] to
compute the best adjustments
 Other shavings: Precedence, Ranked First/Last
activities
22
5
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Beyond the Basic Search Scheme
 Shaving. Example (Tested on ILOG Scheduler):

Famous Job-Shop problem mt10 (1010)

Strong constraint propagation (disjunctive, edge-finder,
precedence energy)

Strong Shaving (time-bounds, precedence, rank
first/last). Shave until a fix point is reached.

Optimality proof requires:
 2 choice points !!!!
 About 2mn CPU time
22
6
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Beyond the Basic Search Scheme
 Probing

Main idea: At each node of the search, solve a relaxed
version of the current schedule and use this solution to
guide the search
 Relaxed problem: for example only keep temporal constraints
[ElSakkout&Wallace 2000] or cost relevant activities
[Beck&Refalo 2001]
 If the solution to the relaxed problem cannot be extended to a
solution, identify the discrepancies and branch on the different
alternatives to solve these discrepancies.

22
7
If the relaxed problem can be solved to optimality, it
provides a lower bound on the objective function
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Beyond the Basic Search Scheme
 Probing
22
8

[ElSakkout&Wallace 2000, Beck&Refalo 2001]

Example: Job-shop with Earliness/Tardiness Costs of
last activity
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Beyond the Basic Search Scheme
 Probing

During the search, maintain at each node the optimal
solution of a linear relaxation of the problem (no
resource constraints)
Minimize
 yi
subject to:
i
Cost:
Time windows:
Precedence:
22
9
y i  tc i   x i ,m  pt i ,m   dd i 
y i  ec i  dd i   x i ,m  pt i . m 
s min a i , j   x i , j  s max a i , j 
x i , j  pt i , j  x i , j  1
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Constraint-Based Approaches
Beyond the Basic Search Scheme

Using the relaxed optimal start time (from LP), build
textures

Identify a peak (where the texture > capacity)
 Select a pair of activities, A and B, at the peak
 Branch: (A  B)  (B  A)
 New precedence constraints (as well as precedence
discovered by constraint propagation) are used to
update the LP relaxation
23
0
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Conclusion
Constraint-Based Scheduling
 Properties that contributed to the industrial
success of Constraint-Based Scheduling
23
1

The paradigm clearly separates the constraints
(semantics, propagation algorithms) from the search
space exploration (branching schemes, heuristics)

Constraint propagation allows dramatically pruning the
search before everything gets instantiated

Each constraint is an autonomous algorithm, the
paradigm is extensible: new application-dependent
constraints can easily be implemented
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Conclusion
Constraint-Based Scheduling
 Properties that contributed to the industrial
success of Constraint-Based Scheduling
23
2

Constraint propagation algorithms often rely on some
bounds that can be seen as the optimal solution to a
relaxed (sub)problem

In optimization problems, the search tree is pruned by
computing some lower bound on the objective function,
usually it corresponds to the optimal objective function
of a relaxed problem

Powerful heuristics also often rely on analyzing a good
solution to a relaxed problem
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Conclusion
Constraint-Based Scheduling
Relaxed
(sub)problems
Optimal
solution
Good
solution
bounds
bounds
Propagation
heuristics
Search
Real problem
23
3
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Conclusion
Constraint-Based AI Planning
Relaxed
(sub)problems
Optimal
solution
Good
solution
bounds
bounds
Part I
heuristics
Part II
Propagation
Search
Real problem
23
4
PLANET International Summer School on AI Planning, Sept. 2002, Halkidiki, Greece
Descargar

Planning with Resources