3. Automated planning
The student chooses one task and one variant of the assignment (a) or (b) or (c) and solves it.
Option (a): Description of the task in the PDDL and generation of a plan from an existing planner.
Option (b): Create your own domain-dependent planner.
Option (c): Compile the task into PDDL language according to input parameters.
Entering variant (a) - Domain engineering
Choose one of the tasks below. Describe it in the PDDL language and generate a plan that leads to the solution of the task with the minimum number of steps (optimal plan). Alternatively, you can look for plans that lead to a solution but are not optimal, or plans that do not optimize, such as plans that find a solution in less than the specified time. Consider different ways of expressing a given task in a PDDL. Upload the codes in the PDDL and the generated plan (or plans) to gitlab.
Enter variant (b) - Creating a Planner
Create a domain dependent for a specific task from the tasks below. Focus on your own search algorithm and plan generation, you can choose from different types of uninformed and informed systematic search, it is also possible to use local search. The solution will not contain a PDDL language parser, instead the STRIPS representation of the task will be built directly into the program. It is important that the solution uses the principles of classical planning, ie the representation of states using logical atoms, actions with logical assumptions and effects, etc. Upload the solution to gitlab.
Specifying variant (c) - Problem Compilation
Create a compiler for the task into PDDL. Assume a task with certain input parameters, the goal is to create a program whose output will be code in the PDDL language, which will represent the specification in the form of a classical planning problem. The solution of the created PDDL will then be the solution of a specific instance of the original task. In the PDDL output code, the input parameters of the task will be taken into account, ie for example the input graph, the input numerical parameter, etc.
Tasks
Lloyd’s 15 Puzzle
Let’s have a classic sliding puzzle with the size of N x N blocks. One block is missing in the grid, and you can move an adjacent block in its place (top, bottom, left, or right). Each block has its own unique number from 1 to (N^2-1). Initially, the blocks are randomly distributed in the grid. The task is to arrange the blocks according to the number from left to right and from top to bottom with as few steps as possible (one step is to move one block).
Sokoban
There are boxes in the grid with walls, which the warehouseman must move by pushing to the prescribed place. The task of the warehouseman is to reach the boxes to the destination with as few steps as possible. The step is to move the storekeeper (not the box) by one place.
MAPF (Multi-agent Path Finding)
The problem is similar to Lloyd’s 15 in that instead of a grid we have a general continuous unoriented graph. Instead of tiles, we have numbered agents that are at the vertices, always at most one agent at the vertex. Some vertices are free and similarly to Lloyd’s 15 puzzle, it is possible to move the agent to the neighboring free peak. The goal is to find a sequence of moves so that each agent reaches its target vertex.
Warehouse logistics
We have a warehouse represented as a grid map, various objects are stored in various places in the warehouse. We also have a group of robots, with each robot carrying one item. The task is to use robots to transport objects to the specified destinations. As a rule, there are many times more objects than robots, the distribution of objects in the warehouse is even, but the target places for objects are relatively small (in practice, these are places where objects are packaged). Express the task as classical planning.
Traveling purchaser problem (TPP)
This is a problem for the business traveler, who also buys goods. We have a number of products and a number of markets. In each market, a limited quantity of each product is provided at a known price. The goal of a business traveler is to buy goods according to a given list while minimizing the cost of goods and travel costs between markets.
Factory Balls Forever
In each level of the game link: https://poki.cz/g/factory-balls-forever [Factory Balls Forever] it is necessary to color the ball according to the specified pattern. Patterns can be created by covering certain parts of the ball, while the whole uncovered part is always colored with the selected color. The surface of the ball represents a continuous surface and it is necessary to think about overcoming the discrepancy between the continuous nature of the task and its discrete expression as classical planning.
Minecraft
The Minecraft planning problem is similar to the Blocks World domain (see lecture), where we also have a robot that manipulates cubes. The robot moves freely along the spatial grid (it can fly), where each cell corresponds to a block (cube). The robot can take a block if it is on an adjacent square. If the robot is holding a block, it can place it on an adjacent square. The task is to use a robot to build a tower of a certain height from the cubes (for example 3).
Planners
"PDDL Editor" web interface with planner: http://editor.planning.domains
Can be used together with another planner (link), contains import of tasks from a number of IPC years.
Fast Downward planner http://www.fast-downward.org/HomePage
Fast Forward planner: https://fai.cs.uni-saarland.de/hoffmann/ff.html (download here: https://fai.cs.uni-saarland.de/hoffmann/ff/FF-v2. 3.tgz)
Planners from one of the International Planning Competition: https://ipc2018-classical.bitbucket.io/#planners
Solved planning tasks in PDDL - examples
Exercise presentation - tasks of the Tower of Hanoi, Logistics and Blocks https://gitlab.fit.cvut.cz/BI-ZUM/bi-zum/blob/master/media/sources/media_tutorials_04_sem4.pdf
The page https://fai.cs.uni-saarland.de/hoffmann/ff-domains.html contains a collection of the most well-known tasks in the field of planning (solutions in PDDL). For each task, a description of the domains in the PDDL and a generator are provided. You can use the generator to generate a PDDL containing a description of the problem.
International Planning Competition - overview of all years
Suitable other self-study resources available ONLINE (optional)
I. E-books available online through the CTU - Planning library
Automated Planning: Theory and Practice, Malik Ghallab,, Dana S. Nau,, and Paolo Traverso, Elsevier Science & Technology https://ebookcentral.proquest.com/lib/cvut/reader.action?docID=333985&ppg=46
II. Books and other resources freely available on the Internet
Steven M. LaValle, Planning algorithms, Cambridge University Press, 2006. http://planning.cs.uiuc.edu/
PDDL wiki https://planning.wiki/ref
PDDL https://www.researchgate.net/publication/2278933_PDDL_-_The_Planning_Domain_Definition_Language
Introduction to PDDL http://www.cs.toronto.edu/~sheila/2542/w09/A1/introtopddl2.pdf
Solved planning tasks in PDDL https://fai.cs.uni-saarland.de/hoffmann/ff-domains.html