Easy Proof Omitted

A sink for random thoughts & experiments

0%

Automated Planning and PDDL

Posted on

What is Planning?

Planning is the art and practice of thinking before acting. - Patrik Haslum

"Planning" is the name used in AI for computational problems that have to do with choosing a course of action. This may be for the purpose of creating a "plan", e.g., for a pair of robots to assemble a (simulated) IKEA table, for moving a sheet of paper through a printer, or exploiting IT security weaknesses. However, problems like model checking or computing genome edit distance are, in a computational sense, essentially the same.1

Planning Domain Description Language

PDDL was originally developed by Drew McDermott and the 1998 planning competition committee. It was inspired by the need to encourage the empirical comparison of planning systems and the exchange of planning benchmarks within the community. Its development improved the communication of research results and triggered an explosion in performance, expressivity and robustness of planning systems.

PDDL has become a de facto standard language for describing planning domains, not only for the competition but more widely, as it offers an opportunity to carry out empirical evaluation of planning systems on a growing collection of generally adopted standard benchmark domains. The emergence of a language standard will have an impact on the entire field, influencing what is seen as central and what peripheral in the development of planning systems.

  • Used by almost all implemented systems for deterministic planning
  • Supports a language comparable to what we have defined above (including schematic operators and quantification)
  • Syntax inspired by the Lisp programming language: e.g. prefix notation for formulae

Example: Rock Collecting Rover

There are several waypoints on the planet, some of which are connected. A rover can navigate between two waypoints A and B when A and B are connected. Interesting rocks can be found at any waypoint.

The rover can only analyze the rocks of a waypoint when it is at the waypoint. After the rover has analyzed a rock sample, it can transmit the results of this particular analysis to Earth. The transmission of the results of analysed rock samples can only be carried out at certain waypoints where the connection to Earth is good enough.

Each result is to be transferred via an individual action.

All actions have unit costs.

The goal is to analyze all rock samples and transfer the results to Earth.

Domain file

A domain file consists of:2

  • (define (domain DOMAINNAME)
  • a :requirements definition (use :strips :typing by default)
  • definitions of types (each parameter has a type)
  • definitions of predicates
  • definitions of operators (actions)
domain.pddl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
(define (domain roverdomain)
    (:requirements :strips :typing :adl)
    (:types rover dish rock position)
    (:predicates
        (connected ?a ?b - position)
        (has-dish ?a - position)
        (has-rock ?a - position)
        (has-rover ?a - position)
        (occupied)
    )
    
    (:action navigate
        :parameters (?a ?b - position)
        :precondition (and
            (has-rover ?a)
            (connected ?a ?b)
        )
        :effect (and
            (not (has-rover ?a))
            (has-rover ?b)
        )
    )
    
    
    (:action collect
        :parameters (?a - position)
        :precondition (and
            (has-rover ?a)
            (has-rock ?a)
            (not (occupied))
        )
        :effect (and
            (not (has-rock ?a))
            (occupied)
        )
    
    )
    
    (:action transmit
        :parameters (?a - position)
        :precondition (and
            (occupied)
            (has-rover ?a)
            (has-dish ?a)
        )
        
        :effect (and
            (not (occupied))
        )
    )
    
)

Problem file

A problem file consists of:3

  • (define (problem PROBLEMNAME)
  • declaration of which domain is needed for this problem
  • definitions of objects belonging to each type
  • definition of the initial state (list of state variables initially true)
  • definition of goal states (a formula like operator precondition)
problem.pddl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
(define (problem roverproblem)
    (:domain roverdomain)
    (:objects
        ; dh - dish
        ; rv - rover
        ; rk - rock
        a b c d e f g - position
    )
    
    (:init 
        (has-dish a)
        (has-rock b)
        (has-rock e)
        (has-rock c)
        (has-rock d)
        (has-rover g)
        
        (connected g f)
        (connected f a)
        (connected a b)
        (connected b g)
        (connected g b)
        (connected b c)
        (connected c b)
        (connected e g)
        (connected g e)
        (connected d e)
        (connected c d)
        (connected d c)

    )
    
    
    (:goal
        ( and
            (not (has-rock a))
            (not (has-rock b))
            (not (has-rock e))
            (not (has-rock c))
            (not (has-rock d))
            (not (occupied))
        )
    )
    
    
)

Popular Planners

Fast Downward Planner

Fast Downward4 is a domain-independent classical planning system.

1
2
3
4
5
wget https://github.com/aibasel/downward/archive/release-20.06.0.tar.gz
tar -xvzf release-20.06.0.tar.gz
cd downward-release-20.06.0
./build.py # only once
./fast-downward.py --alias lama-first /path/to/domain.pddl /path/to/problem.pddl
[stdout]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
INFO     Running translator.
INFO     translator stdin: None
INFO     translator time limit: None
INFO     translator memory limit: None
INFO     translator command line string: /usr/bin/python3 builds/release/bin/translate/translate.py ../domain.pddl ../problem.pddl --sas-file output.sas
Parsing...
Parsing: [0.000s CPU, 0.001s wall-clock]
Normalizing task... [0.000s CPU, 0.000s wall-clock]
Instantiating...
Generating Datalog program... [0.000s CPU, 0.000s wall-clock]
Normalizing Datalog program...
Trivial rules: Converted to facts.
Normalizing Datalog program: [0.000s CPU, 0.002s wall-clock]
Preparing model... [0.000s CPU, 0.000s wall-clock]
Generated 10 rules.
Computing model... [0.000s CPU, 0.001s wall-clock]
64 relevant atoms
28 auxiliary atoms
92 final queue length
101 total queue pushes
Completing instantiation... [0.000s CPU, 0.001s wall-clock]
Instantiating: [0.000s CPU, 0.005s wall-clock]
Computing fact groups...
Finding invariants...
5 initial candidates
Finding invariants: [0.010s CPU, 0.001s wall-clock]
Checking invariant weight... [0.000s CPU, 0.000s wall-clock]
Instantiating groups... [0.000s CPU, 0.000s wall-clock]
Collecting mutex groups... [0.000s CPU, 0.000s wall-clock]
Choosing groups...
5 uncovered facts
Choosing groups: [0.000s CPU, 0.000s wall-clock]
Building translation key... [0.000s CPU, 0.000s wall-clock]
Computing fact groups: [0.010s CPU, 0.001s wall-clock]
Building STRIPS to SAS dictionary... [0.000s CPU, 0.000s wall-clock]
Building dictionary for full mutex groups... [0.000s CPU, 0.000s wall-clock]
Building mutex information...
Building mutex information: [0.000s CPU, 0.000s wall-clock]
Translating task...
Processing axioms...
Simplifying axioms... [0.000s CPU, 0.000s wall-clock]
Translator axioms removed by simplifying: 0
Computing negative axioms... [0.000s CPU, 0.000s wall-clock]
Processing axioms: [0.000s CPU, 0.000s wall-clock]
Translating task: [0.000s CPU, 0.001s wall-clock]
5 effect conditions simplified
0 implied preconditions added
Detecting unreachable propositions...
0 operators removed
0 axioms removed
1 propositions removed
Detecting unreachable propositions: [0.000s CPU, 0.000s wall-clock]
Reordering and filtering variables...
6 of 6 variables necessary.
0 of 1 mutex groups necessary.
17 of 17 operators necessary.
0 of 0 axiom rules necessary.
Reordering and filtering variables: [0.000s CPU, 0.000s wall-clock]
Translator variables: 6
Translator derived variables: 0
Translator facts: 17
Translator goal facts: 5
Translator mutex groups: 0
Translator total mutex groups size: 0
Translator operators: 17
Translator axioms: 0
Translator task size: 92
Translator peak memory: 26812 KB
Writing output... [0.000s CPU, 0.000s wall-clock]
Done! [0.010s CPU, 0.010s wall-clock]
translate exit code: 0

INFO     Running search (release).
INFO     search stdin: output.sas
INFO     search time limit: None
INFO     search memory limit: None
INFO     search command line string: builds/release/bin/downward --evaluator 'hlm=lmcount(lm_factory=lm_rhw(reasonable_orders=true),transform=adapt_costs(one),pref=false)' --evaluator 'hff=ff(transform=adapt_costs(one))' --search 'lazy_greedy([hff,hlm],preferred=[hff,hlm],cost_type=one,reopen_closed=false)' --internal-plan-file sas_plan < output.sas
[t=4.9308e-05s, 9744 KB] reading input...
[t=0.000295154s, 9744 KB] done reading input!
[t=0.0019288s, 10000 KB] Initializing landmarks count heuristic...
[t=0.00200992s, 10000 KB] Initializing Exploration...
[t=0.00207028s, 10000 KB] Generating landmarks using the RPG/SAS+ approach
approx. reasonable orders
[t=0.00226699s, 10000 KB] approx. obedient reasonable orders
[t=0.00232234s, 10000 KB] Removed 0 reasonable or obedient reasonable orders
[t=0.0024036s, 10000 KB] Landmarks generation time: 0.000434502s
[t=0.00244563s, 10000 KB] Discovered 14 landmarks, of which 0 are disjunctive and 0 are conjunctive.
[t=0.00247662s, 10000 KB] 22 edges
[t=0.0025644s, 10000 KB] Simplifying 21 unary operators... done! [21 unary operators]
[t=0.00263706s, 10000 KB] time to simplify: 0.000104331s
[t=0.00269396s, 10000 KB] Initializing additive heuristic...
[t=0.00272805s, 10000 KB] Initializing FF heuristic...
[t=0.00285032s, 10000 KB] Building successor generator...done!
[t=0.00297551s, 10000 KB] peak memory difference for successor generator creation: 0 KB
[t=0.00300687s, 10000 KB] time for successor generation creation: 1.9058e-05s
[t=0.0030427s, 10000 KB] Variables: 6
[t=0.00307538s, 10000 KB] FactPairs: 17
[t=0.00310553s, 10000 KB] Bytes per state: 4
[t=0.00322581s, 10000 KB] Conducting lazy best first search, (real) bound = 2147483647
[t=0.00330731s, 10000 KB] 6 initial landmarks, 5 goal landmarks
[t=0.00336785s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 8
[t=0.00340958s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 8
[t=0.00344425s, 10000 KB] g=0, 1 evaluated, 0 expanded
[t=0.00348597s, 10000 KB] Initial heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 8
[t=0.00352082s, 10000 KB] Initial heuristic value for ff(transform = adapt_costs(one)): 8
[t=0.00356578s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 7
[t=0.00360315s, 10000 KB] g=1, 2 evaluated, 1 expanded
[t=0.00365184s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 7
[t=0.00369002s, 10000 KB] g=2, 3 evaluated, 2 expanded
[t=0.00378585s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 6
[t=0.00382462s, 10000 KB] g=3, 9 evaluated, 8 expanded
[t=0.00398096s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 5
[t=0.00402012s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 6
[t=0.0040531s, 10000 KB] g=10, 25 evaluated, 24 expanded
[t=0.00413626s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 4
[t=0.00417406s, 10000 KB] g=12, 31 evaluated, 30 expanded
[t=0.00430784s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 5
[t=0.00435535s, 10000 KB] g=17, 43 evaluated, 42 expanded
[t=0.00439819s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 3
[t=0.0044344s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 4
[t=0.00446531s, 10000 KB] g=18, 44 evaluated, 43 expanded
[t=0.00453552s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 2
[t=0.00457285s, 10000 KB] g=21, 49 evaluated, 48 expanded
[t=0.00465162s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 3
[t=0.00468935s, 10000 KB] g=24, 56 evaluated, 55 expanded
[t=0.00473399s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 2
[t=0.00477107s, 10000 KB] g=25, 57 evaluated, 56 expanded
[t=0.00481367s, 10000 KB] New best heuristic value for lmcount(lm_factory = lm_rhw(reasonable_orders = true), transform = adapt_costs(one), pref = false): 1
[t=0.00485071s, 10000 KB] New best heuristic value for ff(transform = adapt_costs(one)): 1
[t=0.00488327s, 10000 KB] g=26, 58 evaluated, 57 expanded
[t=0.00495006s, 10000 KB] Solution found!
[t=0.00498952s, 10000 KB] Actual search time: 0.00167119s
navigate g b (1)
navigate b c (1)
navigate c d (1)
collect d (1)
navigate d e (1)
navigate e g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
navigate a b (1)
navigate b c (1)
collect c (1)
navigate c b (1)
navigate b g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
navigate a b (1)
navigate b g (1)
navigate g e (1)
collect e (1)
navigate e g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
navigate a b (1)
collect b (1)
navigate b g (1)
navigate g f (1)
navigate f a (1)
transmit a (1)
[t=0.00502718s, 10000 KB] Plan length: 31 step(s).
[t=0.00502718s, 10000 KB] Plan cost: 31
[t=0.00502718s, 10000 KB] Expanded 62 state(s).
[t=0.00502718s, 10000 KB] Reopened 0 state(s).
[t=0.00502718s, 10000 KB] Evaluated 63 state(s).
[t=0.00502718s, 10000 KB] Evaluations: 126
[t=0.00502718s, 10000 KB] Generated 125 state(s).
[t=0.00502718s, 10000 KB] Dead ends: 0 state(s).
[t=0.00502718s, 10000 KB] Number of registered states: 63
[t=0.00502718s, 10000 KB] Int hash set load factor: 63/64 = 0.984375
[t=0.00502718s, 10000 KB] Int hash set resizes: 6
[t=0.00502718s, 10000 KB] Search time: 0.00180231s
[t=0.00502718s, 10000 KB] Total time: 0.00502718s
Solution found.
Peak memory: 10000 KB
Remove intermediate file output.sas
search exit code: 0

PDDL4J

The purpose of PDDL4J5 is to facilitate the development of JAVA tools for Automated Planning based on PDDL language (Planning Domain Description Language). Automated planning and scheduling, in the relevant literature often denoted as simply planning, is a branch of artificial intelligence that concerns the realization of strategies or action sequences, typically for execution by intelligent agents, autonomous robots and unmanned vehicles.[^1]

1
2
3
wget https://github.com/pellierd/pddl4j/releases/download/v3.8.3/PDDL4J-v3.8.3.zip
unzip PDDL4J-v3.8.3.zip
java -jar pddl4j-3.8.3.jar -p 0 -o domain.pddl -f problem.pddl
  • -p 0 for HSP (default planner)
  • -p 1 for FF
[stdout]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
parsing domain file "domain.pddl" done successfully
parsing problem file "problem.pddl" done successfully

encoding problem done successfully (17 ops, 12 facts)
* starting A*
* A* succeeded

found plan as follows:

00: (navigate g e) [1]
01: (   collect e) [1]
02: (navigate e g) [1]
03: (navigate g f) [1]
04: (navigate f a) [1]
05: (  transmit a) [1]
06: (navigate a b) [1]
07: (navigate b c) [1]
08: (   collect c) [1]
09: (navigate c b) [1]
10: (navigate b g) [1]
11: (navigate g f) [1]
12: (navigate f a) [1]
13: (  transmit a) [1]
14: (navigate a b) [1]
15: (   collect b) [1]
16: (navigate b g) [1]
17: (navigate g f) [1]
18: (navigate f a) [1]
19: (  transmit a) [1]
20: (navigate a b) [1]
21: (navigate b c) [1]
22: (navigate c d) [1]
23: (   collect d) [1]
24: (navigate d e) [1]
25: (navigate e g) [1]
26: (navigate g f) [1]
27: (navigate f a) [1]
28: (  transmit a) [1]

plan total cost: 29.00


time spent:       0.11 seconds parsing 
                  0.05 seconds encoding 
                  0.05 seconds searching
                  0.20 seconds total time

memory used:     -0.00 MBytes for problem representation
                 -0.00 MBytes for searching
                 -0.00 MBytes total

Online Planner

PDDL Editor

editor.planning.domains is a fully featured PDDL editor. The functionality is continually changing, but currently it boasts features such as syntax highlighting, code folding, PDDL-specific auto-completion, multi-tab support, etc.

You can switch the default satisfactory solver with an optimal solver by simply replacing the Custom Planner URL with http://fd-solver.herokuapp.com.

If everything goes fine, you can find the plan in a new file on the left panel.

GUI Planner

PDDL4GUI

PDDL4GUI6 is a small application written in Java that provides a graphical interface to the PDDL4J library. PDDL4GUI offers:

  • A graphical interface for solving planning problems with the PDDL4J library.
  • A graphical interface for solving planning problems through PDDL4J webservice and RESTFull API.
  • Anytime behavior for compatible planners.
  • The integration of VAL (The plan validation system) which offers the possibility to test the validity of the plans provided by PDDL4J.

After cloning the git repository, simply run java -javaagent:pddl4gui-1.0.jar -server -Xms2048m -Xmx2048m -jar pddl4gui-1.0.jar -LOCAL or run the provided shell script ./pddl4gui_loc.sh.

Resources

  1. Patrik Haslum @ ANU↩︎

  2. Principles of AI Planning - domain files↩︎

  3. Principles of AI Planning - problem files↩︎

  4. Downward Planner Git Repository↩︎

  5. PDDL4J Git Repository↩︎

  6. PDDL4GUI Git Repository↩︎