val

VAL's Progress:The Automatic Validation Tool for PDDL2.1 used in the International Planning Competition: 

VAL's Progress: The Automatic Validation Tool for PDDL2.1 used in the International Planning Competition Richard Howey and Derek Long University of Durham

Introduction: 

Introduction VAL was the validation tool used in the 3rd IPC. VAL is evolving along side PDDL to validate plans written in PDDL. The latest development is to extend VAL to validate plans with continuous effects. Validating plans with continuous effects is an important first step to developing planners capable of handling continuous effects.

Validation Example: Generator and Tanks : 

Validation Example: Generator and Tanks Initial State and Problem: A generator must run continuously for 100 time units. The generator has a capacity of 60 fuel units, using 1 fuel unit for every 1 time unit to generate. Two fuel tanks with 25 fuel units each can refuel the generator while it is generating. The generator starts with a full tank of fuel.

Durative Actions: 

Durative Actions Generate: Duration: must be 100 time units. Invariant condition: fuel-level of generator must be greater than zero. Continuous Effect: Refuel: Duration: less or equal to time to empty tank. Invariant condition: fuel-level of generator must be less than the capacity of the generator. Continuous Effects: dr/dt = 1 df/dt = 2 k(f) ( k(f) r – f(0) ) dg/dt = 2 k(f) ( f(0) – k(f) r ) dg/dt = – 1 t = time since durative action began g = fuel-level of generator f = fuel-level of a tank k(f) = flow constant of tank f

Possible Plan: 

Possible Plan 1: (generate generator) [100] 20: (refuel generator tank1) [25] 80: (refuel generator tank2) [12.5] generate refuel 1 refuel 2

Plan to Validate: 

Plan to Validate 1: (generate generator) - start 20: Invariant for (generate generator) 20: Update of Continuously Changing Primitive Numerical Expressions 20: (refuel generator tank1) - start 45: Invariant for (generate generator) Invariant for (refuel generator tank1) 45: Update of Continuously Changing Primitive Numerical Expressions 45: (refuel generator tank1) - end 101: Invariant for (generate generator) 101: Update of Continuously Changing Primitive Numerical Expressions 101: (generate generator) - end

Time 1 upto 20: 

Time 1 upto 20 1: (generate generator) - start 20: Invariant for (generate generator) 20: Update of Continuously Changing Primitive Numerical Expressions t = time since last simple action g = fuel-level of generator  g(t) = – t + 60 for t in [0,19) Invariant g(t) > 0 for t in (0,19) Update Generator fuel-level: g(19) = –19 + 60 = 41 dg/dt = – 1  – t + 60 > 0 for t in (0,19)

Time 20 upto 45: 

Time 20 upto 45 20: (refuel generator tank1) - start 45: Invariant for (generate generator) Invariant for (refuel generator tank1) 45: Update of Continuously Changing Primitive Numerical Expressions 45: (refuel generator tank1) - end t = time since last simple action g = fuel-level of generator a = fuel-level of tank 1 dg/dt = – 1 dr/dt = 1 da/dt = 0.08r – 2 dg/dt = – 0.08r + 2  dg/dt = – 0.08t + 1  g(t) = – 0.04t2 + t + 41 for t in [0,25)  r(t) = t for t in [0,25)  a(t) = 0.04t2 – 2t + 25 for t in [0,25)

Time 20upto 45: 

Time 20 upto 45 Invariants Update g(25) = – 0.04252 + 25 + 41 = 41, a(25) = 0 g(t) > 0 for t in [0,25)  – 0.04t2 + t + 41 > 0 for t in [0,25) g(t)  60 for t in (0,25)  – 0.04t2 + t + 41  60 for t in (0,25)  0.04t2 – t + 19  0 for t in (0,25) t = time since last simple action g = fuel-level of generator

Time 45 upto 80: 

Time 45 upto 80 80: Invariant for (generate generator) 80: Update of Continuously Changing Primitive Numerical Expressions t = time since last simple action g = fuel-level of generator  g(t) = – t + 41 for t in [0,35) Invariant g(t) > 0 for t in [0,35) Update Generator fuel-level: g(35) = – 35 + 41= 6 dg/dt = – 1  – t + 41 > 0 for t in [0,35)

Time 80 upto 92.5: 

Time 80 upto 92.5 80: (refuel generator tank2) - start 92.5: Invariant for (generate generator) Invariant for (refuel generator tank2) 92.5: Update of Continuously Changing Primitive Numerical Expressions 92.5: (refuel generator tank2) - end t = time since last simple action g = fuel-level of generator b = fuel-level of tank 2 dg/dt = – 1 dr/dt = 1 db/dt = 0.32r – 4 dg/dt = – 0.32r + 4  dg/dt = – 0.32t + 3  g(t) = – 0.16t2 + 3t + 6 for t in [0,12.5)  r(t) = t for t in [0,12.5)  b(t) = 0.16t2 – 4t + 25 for t in [0,12.5)

Time 80upto 92.5: 

Time 80 upto 92.5 Invariants Update Generator and Tank fuel-levels: g(12.5) = 18.5, b(12.5) = 0 g(t) > 0 for t in [0,12.5)  – 0.16t2 + 3t + 6 > 0 for t in [0,12.5) g(t)  60 for t in (0,12.5)  – 0.16t2 + 3t + 6  60 for t in (0,12.5)  0.16t2 – 3t – 54  0 for t in (0,12.5) t = time since last simple action g = fuel-level of generator

Slide13: 

Time 92.5 upto 101 101: Invariant for (generate generator) 101: Update of Continuously Changing Primitive Numerical Expressions 101: (generate generator) - end  g(t) = – t + 18.5 for t in [0,8.5) Invariant g(t) > 0 for t in [0,8.5) Update Generator fuel-level: g(8.5) = – 8.5 + 18.5 = 10 dg/dt = – 1  – t + 18.5 > 0 for t in [0,8.5)

Slide14: 

Goal

LaTeX Report: 

LaTeX Report Plan Plan to validate Plan validation Diagrams See handouts for generator validation report

Gantt Chart: 

Gantt Chart Actions of different executives can be displayed on different rows

Graphs: 

Graphs Graphs of the primitive numerical expressions are plotted for the duration of the plan.

Conclusions: 

Conclusions Restrictions on types of continuous effects are required to guarantee validation of plans: all continuous effects must be polynomial Validating plans with continuous effects is an important first step to developing planners capable of handling continuous effects.