-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex-OLD-where-3-and-Pi-are-not-distinguished.html
141 lines (96 loc) · 18.6 KB
/
index-OLD-where-3-and-Pi-are-not-distinguished.html
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
---
layout: default
---
<body>
<h1>The PANDA Planning Framework</h1>
<p>
PANDA is a framework that combines different techniques related to Hierarchical Task Network (HTN) planning. PANDA is an acronym for <span style="text-decoration: underline;">P</span>lanning and <span style="text-decoration: underline;">A</span>cting in a <span style="text-decoration: underline;">N</span>etwork <span style="text-decoration: underline;">D</span>ecomposition <span style="text-decoration: underline;">A</span>rchitecture. PANDA has been developed at the <a href="https://www.uni-ulm.de/en/in/ki/">Institute of Artificial Intelligence at Ulm University</a> headed by <a href="https://www.uni-ulm.de/in/ki/biundo">Susanne Biundo</a>.
</p>
<p>
We are currently in the process of making all components of PANDA available <a href="https://github.com/panda-planner-dev">here on GitHub</a> under an open source license. When the one you are interested in is not available (yet), please contact the respective authors for an executable or the code, if required.
</p>
<h2>A (Short) History</h2>
<p>
The PANDA framework has a long development history, and the first systems worth mentioning are <i>PANDA<sub>1</sub></i> (a plan space-based planning system based on POCL planning) developed by <a href="https://www.uni-ulm.de/in/ki/inst/alumni/bernd-schattenberg/">Bernd Schattenberg</a> and colleagues, and a domain editor tool called <i>PANDA Editor</i> that was a graphical editor for the XML-based input language of <i>PANDA<sub>1</sub></i>, based on the Eclipse framework (also developed by <a href="https://www.uni-ulm.de/in/ki/inst/alumni/bernd-schattenberg/">Bernd Schattenberg</a>). The development of both programs has been terminated; the software is not available anymore. Loosely based on some of the ideas implemented in <i>PANDA<sub>1</sub></i>, but with significant differences already at the level of pseudo code, <a href="https://www.uni-ulm.de/in/ki/inst/alumni/bastian-seegebarth/">Bastian Seegebarth</a> and <a href="https://www.uni-ulm.de/in/ki/inst/alumni/pascal-bercher/">Pascal Bercher</a> developed <i>PANDA<sub>2</sub></i>.
Finally, <i>PANDA<sub>3</sub></i> includes an exact re-implementation of <i>PANDA<sub>2</sub></i>, which differs mainly in the programming paradigm and design choices, but not on the level of pseudo code. It was mainly implemented by <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">Gregor Behnke</a>, with some help of <a href="https://www.uni-ulm.de/in/ki/inst/alumni/pascal-bercher/">Pascal Bercher</a> and <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">Daniel Höller</a>.
</p>
<p>
On top of this "traditional" POCL-based search, <i>PANDA<sub>3</sub></i> also includes two new HTN planning systems, which work completely differently. We will denote the POCL-based solver as <i>PANDA<sub>pocl</sub></i>. The two other solvers are the following: <i>PANDA<sub>pro</sub></i>, mainly developed by <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">Daniel Höller</a>, performs progression search in the space of states (plus partial plans) similar to the SHOP family. <i>PANDA<sub>sat</sub></i>, mainly developed by <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">Gregor Behnke</a>, solves HTN problems by compiling them into propositional logic.
</p>
<h2>Overview</h2>
<p>
The purpose of this page is to give an overview of the <strong>current</strong> PANDA framework, i.e., these three planners plus additional systems for plan repair, plan recognition, plan verification, and other related planning tasks – which are all based somehow on one or several of these systems.
</p>
<p>We now describe the following components:
<ul>
<li><a href="#sec_hddl">Problem Definition</a></li>
<li><a href="#sec_grounding">Preprocessing and Grounding</a></li>
<li><a href="#sec_solvers">Solvers</a></li>
<li><a href="#sec_verify">Plan Verification</a></li>
<li><a href="#sec_pgr">Plan and Goal Recognition</a></li>
<li><a href="#sec_repair">Plan Repair</a></li>
</ul>
<h3 id="sec_hddl">Problem Definition</h3>
<p>For a long time, there was no widely-used input language for hierarchical planning problems. In preparation of the <a href="http://gki.informatik.uni-freiburg.de/competition/">International Planning Competition (IPC) 2020</a>, we surveyed the input languages of recent systems and proposed the Hierarchical Domain Definition Language (HDDL) as standard input language for the competition. The following paper gives a discussion of the related languages and a definition of HDDL.</p>
<ul>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>, <a href="http://magma.imag.fr/content/humbert-fiorino">H. Fiorino</a>, <a href="http://lig-membres.imag.fr/pellier/">D. Pellier</a>, and <a href="http://www.volus.net/">R. Alford</a>. <strong>HDDL: An Extension to PDDL for Expressing Hierarchical Planning Problems</strong>. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9883–9891. (<a href="https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2020/Hoeller2020HDDL.pdf">PDF</a>)</li>
</ul>
<p>After the results of the IPC have been published the IPC benchmark set (all in HDDL) will be made publicly available.</p>
<h3 id="sec_grounding">Preprocessing and Grounding</h3>
<p>Like other input languages for planning problems (e.g., like PDDL for classical planning), HDDL is based on a first order input language allowing for variables in the model to enable a(n exponentially more) compact model definition.</p>
<p>Though the plan space search of the current system comes with some support for solving HTN planning problems in a lifted manner, the most recent developments, (especially <i>PANDA<sub>pro</sub></i> and <i>PANDA<sub>sat</sub></i>) rely on a fully grounded (i.e. propositional) input model. To make the grounded model as small as possible, these systems come with a hierarchical and a state-based reachability analysis to prune parts of the model that cannot be part of any solution. However, creating the whole model and pruning it afterwards is not feasible. Instead, it is created in a way that avoids the creation of unreachable parts in the first place. The process is described in the following paper.</p>
<ul>
<li><a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, A. Schmid, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>On Succinct Groundings of HTN Planning Problems</strong>. In: Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2020, pp. 9775–9784. (<a href="https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2020/AAAI-BehnkeG.1770.pdf">PDF</a>)</li>
</ul>
<h3 id="sec_solvers">Solvers</h3>
<p>
PANDA comes with three distinct approaches to solve HTN planning problems. Two are based on search, the third one on a translation to propositional logic. The most recent heuristics are only implemented for progression search. Therefore, when using PANDA in your project, either <i>PANDA<sub>pro</sub></i> or <i>PANDA<sub>sat</sub></i> might be a good choice.
</p>
<h4>Plan Space Search</h4>
<p>The (historically) first PANDA solvers are based on search in plan space (using Partial Order Causal Link (POCL) techniques), i.e., search nodes are partial plans that are refined until a solution to the planning problem is found. In the following, we will call it <i>PANDA<sub>pocl</sub></i>. Its pseudo code is described in the SoCS-14 paper. This search can be guided by heuristics. The most recent heuristics available in the current system are admissible estimates of the number of missing actions or modifications, based on a data structure called Task Decomposition Graph (TDG), all described in the IJCAI-17 paper.</p>
<ul>
<li><a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>An Admissible HTN Planning Heuristic</strong>. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2017, pp. 480–488. (<a href="http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Bercher17AdmissibleHTNHeuristic.pdf">PDF</a>)</li>
<li><a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, S. Keen,
and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>.
<strong>Hybrid Planning Heuristics Based on Task Decomposition Graphs</strong>.
In: Proceedings of the Seventh Annual Symposium on Combinatorial Search (SoCS). AAAI Press, 2014.</li>
</ul>
<h4>State Space Search</h4>
<p>The second search-based solver uses Progression Search (see JAIR-20 for the algorithm). This search builds solutions in a forward manner, which enables a used heuristic to base its calculation on a fully specified and continuously updated state. We have integrated three main lines of progression heuristics. The Relaxed Composition (RC) heuristics relax the HTN model to a classical planning model and uses classical heuristics calculated on this translation to guide the HTN search (see JAIR-20, IJCAI-19, and ICAPS-18). Recently, we integrated a heuristic based on a relaxed problem class called Delete- and Ordering-free HTN planning (see IJCAI-20) computed via (I)LPs; and a heuristic based on a novel landmark generation method (see HPlan-20). When applying the system, the RC heuristics might be a good choice.</p>
<ul>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a> and <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>.
<strong>Landmark Extraction in HTN Planning</strong>. In: Proceedings of the 3rd ICAPS Workshop on Hierarchical Planning (HPlan). 2020.</li>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, and <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>. <strong>Delete- and Ordering-Relaxation Heuristics for HTN Planning</strong>. In: Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2020, pp. 4076–4083. (<a href="https://www.ijcai.org/proceedings/2020/0564.pdf">PDF</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/papers/2020-Hoeller-IJCAI.bib">BibTeX</a>)</li>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>HTN Planning as Heuristic Progression Search</strong>. Journal of Artificial Intelligence Research 67: pp. 835–880 (2020). (<a href="https://jair.org/index.php/jair/article/view/11282/26578">PDF</a>)</li>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>On Guiding Search in HTN Planning with Classical Planning Heuristics</strong>. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2019, pp. 6171–6175. (<a href="http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2019/Hoeller2019ProgressionHeuristics.pdf">PDF</a>)</li>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>A Generic Method to Guide HTN Progression Search with Classical Heuristics</strong>. In: Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS), <span style="color: #ff0000;"><strong>Best Student Paper Award</strong></span>. AAAI Press, 2018, pp. 114–122. (<a href="https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Hoeller18Progression.pdf">PDF</a>)</li>
</ul>
<h4>SAT-based Solvers</h4>
<p>We have developed a translation from HTN planning problems to propositional logic that allows the usage of SAT solvers to find a solution for the planning problem. We thereby first bound the decomposition depth of the problem to enable the translation (of the potentially undecidable HTN problem) to the decidable SAT problem. Then we encode the problem into a propositional formula that has a solution if and only if the (bounded) planning problem has one.</p>
<p>There have mainly been two distinct encodings, one for totally ordered HTN planning problems (see AAAI-18), and one for partially ordered HTN planning problems (see AAAI-19 and IJCAI-19). This planner might be the currently strongest solver in the PANDA framework.</p>
<ul>
<li><a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>Bringing Order to Chaos – A Compact Representation of Partial Order in SAT-based HTN Planning</strong>. In: Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2019, pp. 7520–7529. (<a href="https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2019/Behnke2019orderchaos.pdf">PDF</a>)</li>
<li><a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>Finding Optimal Solutions in HTN Planning – A SAT-based Approach</strong>. Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). IJCAI organization, 2019, pp. 5500–5508.</li>
<li><a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>totSAT – Totally-Ordered Hierarchical Planning through SAT</strong>. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI). AAAI Press, 2018, pp. 6110–6118. (<a href="https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Behnke2018totSAT.pdf">PDF</a>)</li>
</ul>
<h3 id="sec_verify">Plan Verification</h3>
<p>There has been some recent work on deciding whether a given sequence of actions is a solution for an HTN planning problem. This problem becomes a computationally hard problem when the decomposition leading from the initial tasks given in the problem to the potential plan is not given.</p>
<p>We have two distinct components in PANDA:</p>
<ul>
<li> For the <a href="http://gki.informatik.uni-freiburg.de/competition/">IPC 2020</a> we developed a verifier that gets the produced plan and the applied sequence of decomposition methods, represented as a tree (<a href="https://maumagnaguagno.github.io/HTN_Plan_Viewer/">see an example in code and graphically</a>), as input and decides based on it.
<li> For cases where the decomposition sequence/tree is not available (e.g., when post-processing or guessing solutions) we developed a SAT-based verifier (see ICAPS-17).
</ul>
<ul>
<li><a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>This is a solution! (... but is it though?) – Verifying solutions of hierarchical planning problems</strong>. In: Proceedings of the 27th International Conference on Automated Planning and Scheduling (ICAPS). 2017, pp. 20–28. (<a href="http://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2017/Behnke17Verify.pdf">PDF</a>)</li>
</ul>
<h3 id="sec_pgr">Plan and Goal Recognition</h3>
<p>In classical planning, there has been some work on using techniques from planning to solve the task of Plan and Goal Recognition (PGR). In that spirit, we developed a translation from PGR to HTN planning problems. The transformation is based on the lifted model and the resulting problem can be solved by any planning system (see ICTAI-18).</p>
<ul>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>Plan and Goal Recognition as HTN Planning</strong>. In: Proceedings of the 30th IEEE International Conference on Tools with Artificial Intelligence (ICTAI), <span style="color: #ff0000;"><strong>Best Paper Award</strong></span>. IEEE Computer Society, 2018, pp. 466–473. (<a href="https://www.uni-ulm.de/fileadmin/website_uni_ulm/iui.inst.090/Publikationen/2018/Hoeller2018PlanRec.pdf">PDF</a>)</li>
</ul>
<h3 id="sec_repair">Plan Repair</h3>
<p>A translation similar to the one used for PGR can also be used to repair plans when the execution of a plan fails. It is described in KI-20.</p>
<ul>
<li><a href="http://fai.cs.uni-saarland.de/hoeller/index.html">D. Höller</a>, <a href="https://cecs.anu.edu.au/people/pascal-bercher">P. Bercher</a>, <a href="http://www2.informatik.uni-freiburg.de/~behnkeg/index_de.html">G. Behnke</a>, and <a href="https://www.uni-ulm.de/in/ki/biundo">S. Biundo</a>. <strong>HTN Plan Repair via Model Transformation</strong>. In: Proceedings of the 43rd German Conference on Artificial Intelligence (KI), <span style="color: #ff0000;"><strong>Shortlisted for Best Paper Award</strong></span>. Springer, 2020, pp. 88–101. (<a href="http://fai.cs.uni-saarland.de/hoeller/papers/2020-Hoeller-KI.pdf">PDF</a>, <a href="http://fai.cs.uni-saarland.de/hoeller/papers/2020-Hoeller-KI.bib">BibTeX</a>)</li>
</ul>
</body>