[SOLVED] AAAI 2008.

PowerPoint Presentation

Planning with Deadlines

Copyright By Assignmentchef assignmentchef

Public Transport Example
Drivers have working hours;
Bus routes have fixed durations and start and end locations.
Goals are that each bus route is done.
The routes have timetables that they must follow.

Temporal Planning: Public Transport
Planning with Problems Requiring Temporal Coordination. A. I. Coles, M. Fox, D. Long, and A. J. Smith.AAAI 2008.
Managing concurrency in temporal planning using planner-scheduler interaction. A. I. Coles, M. Fox, K. Halsey, D. Long, and A. J. Smith. Artificial Intelligence. 173 (1) (2009).
Route1 D1 B1
Working D1
Working D1
Route3 D1 B2
Actions have:
Working D1
Done Route1
Done Route3
Working D1
Available D1
Available D1
Conditions and Effects at the start and at the end;
Invariant/overall conditions;
duration >= 2 , duration <= 4duration = 2duration = 3 Durations constraints:(= ?duration 4)(and (>= ?duration 2) (<= ?duration 4))Planning with Snap Actions: Crikey/Crikey3 “Planning with Problems Requiring Temporal Coordination.” A. I. Coles, M. Fox, D. Long, and A. J. Smith.AAAI 2008. “Managing concurrency in temporal planning using planner-scheduler interaction.” A. I. Coles, M. Fox, K. Halsey, D. Long, and A. J. Smith. Artificial Intelligence. 173 (1) (2009).Working D1Working D1Route1 D1 B1Working D1Route3 D1 B2duration = 2duration = 3Three Challenges:Make sure ends cant be applied unless starts have.Overall Conditions.Duration constraints.Done Route1Done Route3Working D1Available D1Available D1duration >= 2 , duration <= 4Planning with Snap Actions: Crikey/Crikey3 “Planning with Problems Requiring Temporal Coordination.” A. I. Coles, M. Fox, D. Long, and A. J. Smith.AAAI 2008. “Managing concurrency in temporal planning using planner-scheduler interaction.” A. I. Coles, M. Fox, K. Halsey, D. Long, and A. J. Smith. Artificial Intelligence. 173 (1) 2009.Constraints:W- W>= 2
W W<= 4R1 >=W +
R1 R1= 2
R3 >=R1 +
R3 R3= 3
W >=R3 +

Timed Initial Literals
Introduced in PDDL 2.2 (IPC 2004);
Allow us to model facts that become true, or false, at a specific time.
Can use them to model deadlines or time windows.
Cannot be done directly, but we can achieve this by adding more facts to the domain.

Modelling Deadlines using TILs
(:durative-action unload-truck
:parameters (?p obj ?t- truck ?l- location)
:duration (= ?duration 2)
:condition(and (over all (at ?t ?l))
(at start (in ?p?t)))
(at end (can-deliver ?p)))
:effect (and (at start (not (in ?p ?t)))
(at end (at ?p ?l))))
(can-deliver package1)
(at 9 (not (can-deliver package1)))
(can-deliver package2)
(at 11 (not (can-deliver package2)))

Make sure the action achieving the desired fact has a condition that ensures it takes place before the deadline (over all or at start/end).
Make that fact true in the initial state.
And a TIL to delete it at the deadline.
Note that we could have multiple deadlines for different objects.

Modelling Time Windows Using TILs
(:durative-action bus-route
:parameters (?d driver ?r route ?b bus
?from ?to loc)
:duration (= ?duration (route-duration ?r))
:condition (and (at start (route ?r ?from ?to))
(at start (at ?d ?from))
(at start (at ?b ?from))
(over all (working ?d))
(at end (due ?r)))
:effect (and (at start (not (at ?d ?from)))
(at start (not (at ?b ?from)))
(at end (at ?d ?to))
(at end (at ?b ?to))
(at end (done ?r))
(at 3.75 (due route3))
(at 4 (not (due route3)))

Make sure the action achieving the desired fact has a condition that ensures it takes place during the window (over all or at start/end).POPF/OPTIC will generally work better if you use over all where possible.
Have a TIL to add that fact at the starting point for the window.
And one to delete it when the window ends.
Note that we could have multiple windows for the same fact by adding further TILs to the initial state.

Reasoning with TILs in Forward Search
Order the TILs chronologically;
At each state we have a choice:
Apply an action that is applicable in that state;
Apply the next Available TIL.
This allows us to leave the choice to search about whether the TIL will appear before or after a given action.
POPF has some advantages in this situation:
Only necessary orderings are enforced.

Temporal Planning: Public Transport
Planning with Problems Requiring Temporal Coordination. A. I. Coles, M. Fox, D. Long, and A. J. Smith.AAAI 2008.
Managing concurrency in temporal planning using planner-scheduler interaction. A. I. Coles, M. Fox, K. Halsey, D. Long, and A. J. Smith. Artificial Intelligence. 173 (1) (2009).
Route1 D1 B1
Working D1
Working D1
Route3 D1 B2
Actions have:
Working D1
Done Route1
Done Route3
Working D1
Available D1
Available D1
Conditions and Effects at the start and at the end;
Invariant/overall conditions;
duration >= 2 , duration <= 6duration = 2duration = 3 Durations constraints:(= ?duration 4)(and (>= ?duration 2) (<= ?duration 6)) We can also have windows of opportunity: (at 3.75 (due Route3)) (at 4 (not (due Route3)))(due Route3)Planning with Time Windows: Crikey/Crikey3 “Planning with Problems Requiring Temporal Coordination.” A. I. Coles, M. Fox, D. Long, and A. J. Smith.AAAI 2008. “Managing concurrency in temporal planning using planner-scheduler interaction.” A. I. Coles, M. Fox, K. Halsey, D. Long, and A. J. Smith. Artificial Intelligence. 173 (1) 2009.Constraints:W- W>= 2
W W<= 6R1 >=W +
R1 R1= 2
R3 >=R1 +
R3 R3= 3
W >=R3 +

Due Route3
Due Route3
W>= T0+
TW1= T0 + 3.75
TW11 >= R3 +
R3>=TW1 +

Planning with Time Windows: Crikey/Crikey3
Planning with Problems Requiring Temporal Coordination. A. I. Coles, M. Fox, D. Long, and A. J. Smith.AAAI 2008.
Managing concurrency in temporal planning using planner-scheduler interaction. A. I. Coles, M. Fox, K. Halsey, D. Long, and A. J. Smith. Artificial Intelligence. 173 (1) 2009.
Constraints:
W W>= 2
W W<= 6R1 >=W +
R1 R1= 2
R3 >=R1 +
R3 R3= 3

Due Route3
W>= T0+
TW1= T0 + 3.75
TW1 >= R1 +
R3 >=TW1 +

Due Route3

TW2= T0 + 4
TW2 >= R3 +
W>=TW1 +

/docProps/thumbnail.jpeg

CS: assignmentchef QQ: 1823890830 Email: [email protected]