Artificial Inteligence (AI) is not only designing neural networks or/and processing images with computing vision. AI can be applied for resolving many problems such as the planning ones.
First of all I must say that this is not a tutorial to learn the full PDDL syntax but nevertheless you will be provided with explanations and links to the PDDL reference during this article.
To follow this tutorial we just need to understand two concepts: PDDL and Planner. The below definitions have been taken from the site Planning.Wiki - The AI Planning & PDDL Wiki
PDDL: Planning Domain Definition Language (PDDL) is a family of languages which allow us to define a planning problem. As planning has evolved, so to has the language used to describe it and as such there are now many versions of PDDL available with different levels of expressivity.
Planner: An AI Planner allows us to attempt to solve a plannig problem. An AI planner reads in PDDL and uses it in order to decompose and solve the problem. There are however a really wide array of planners and some are objectively better or worse than others either unilaterally or in solving specific instances.
It goes without saying that if you deep dive into the Planning field you will learn new concepts such as ADL, STRIPS among others.
Let’s image that we have a Vegan Restaurant and we want to improve our waiter service organization and make it more efficient. To achieve this, we need to identify what actions must be taken by our waiters at the time.
After years of attending people we can state the following assumptions:
- The waiter spends
1 minuteaccompanying the customers to the table.
- The spent time on deciding what to eat is always
5 minutes(it doesn’t depend on the number of people in the group).
- Each group will spend
30 secondsper person on ordering the food.
- The waiter spends
45 seconds(0.75 minutes) on serving the food for each person in the group.
- Each group will spend
20 minuteseating and we assume that the number of people in the group won’t affect the spent time.
- The spent time on paying the bill and leaving the table free will be always
- Cooking the food takes
4 minutesper person
Apart from the above assumptions, we also need to consider that:
- The tables are not shared between different groups.
- The waiters cannot take two different actions at time.
Our solution won’t be coupled to the number of waiters, groups nor to the table distributions
Let’s code it
A PDDL problem consists of two files:
domain: The domain file contains the object types, predicates and actions that can exist within the the model. The domain is used to resolve problems that make use of this domain.
problem: It defines which domain is used to resolve the problem and the definition of the problem: elements that participate in the problem, the initial state and the goal to be achieved.
The identified types for our domain are
Predicates are true or false and they are used to identify which actions can be performed. The value of the predicates is modified along the problem resolution. By default, all the predicates are false.
See below the list of identified predicates:
The functions are referred to as numeric fluents.
An action defines a transformation the state of the world. This transformation is typically an action which could be performed in the execution of the plan.
The standard action definition looks like this:
(:action BUILD-WALL :parameters (?s - site ?b - bricks) :precondition (and (on-site ?b ?s) (foundations-set ?s) (not (walls-built ?s)) (not (material-used ?b)) ) :effect (and (walls-built ?s) (material-used ?b) ) )
On the other hand, we will make use of an speciall action
durative-action because our actions impply temporal consequences. For example, a waiter will be busy while is serving the food.
The possible actions in our domain are:
The below diagram represents the problem to be resolved.
First of all we need to transform the real problem into a PDDL script.
To resolve our problem we use the planner
optic that supports
durative-actinos. You could resolve the problem with the below command.
docker run -v `pwd`:/var/data adamfgreen/aip2020:latest optic \ -E -c -S /var/data/domain.pddl /var/data/problem-basic.pddl
The planner will try to find the plan that would find the best solution for our problem. The best solution will guarantee that the waiter organization is the best possible.
; Plan found with metric 50.006 ; States evaluated so far: 833 ; States pruned based on pre-heuristic cost lower bound: 431 ; Time 0.30 0.000: (assign-table-to-group w1 t2 g2) [1.000] 1.001: (decide-what-to-eat g2) [5.000] 1.001: (assign-table-to-group w1 t1 g1) [1.000] 2.002: (decide-what-to-eat g1) [5.000] 6.002: (order-food g2 w2) [2.000] 7.003: (order-food g1 w1) [1.500] 8.003: (cooking-food g2) [16.000] 8.504: (cooking-food g1) [12.000] 20.505: (serve-the-food w1 g1) [2.250] 22.756: (eat g1) [20.000] 24.004: (serve-the-food w2 g2) [3.000] 27.005: (eat g2) [20.000] 42.757: (pay-bill-and-say-bye w1 g1 t1) [3.000] 47.006: (pay-bill-and-say-bye w1 g2 t2) [3.000] * All goal deadlines now no later than 50.006
Certainly to predict the best plan for the above problem could be easy, but could you do the same for the following problem?
docker run -v `pwd`:/var/data adamfgreen/aip2020:latest optic \ -E -c -S /var/data/domain.pddl /var/data/problem-complex.pddl
And we have a plan!
; Plan found with metric 351.797 ; States evaluated so far: 22478 ; States pruned based on pre-heuristic cost lower bound: 98 ; Time 21.25 0.000: (assign-table-to-group w1 t3 g1) [1.000] 1.001: (decide-what-to-eat g1) [5.000] 6.002: (order-food g1 w1) [1.500] 7.503: (cooking-food g1) [12.000] 19.504: (serve-the-food w1 g1) [2.250] 21.755: (eat g1) [20.000] 41.756: (pay-bill-and-say-bye w1 g1 t3) [3.000] 44.757: (assign-table-to-group w1 t5 g8) [1.000] 45.758: (decide-what-to-eat g8) [5.000] 50.759: (order-food g8 w1) [4.000] 54.760: (cooking-food g8) [32.000] 86.761: (serve-the-food w1 g8) [6.000] 92.762: (eat g8) [20.000] 112.763: (pay-bill-and-say-bye w1 g8 t5) [3.000] 115.764: (assign-table-to-group w1 t1 g7) [1.000] 116.765: (assign-table-to-group w1 t5 g6) [1.000] 116.765: (decide-what-to-eat g7) [5.000] 117.766: (decide-what-to-eat g6) [5.000] 122.767: (order-food g6 w1) [3.500] 126.268: (cooking-food g6) [28.000] 154.269: (serve-the-food w1 g6) [5.250] 159.520: (eat g6) [20.000] 179.521: (pay-bill-and-say-bye w1 g6 t5) [3.000] 182.522: (assign-table-to-group w1 t2 g4) [1.000] 183.523: (decide-what-to-eat g4) [5.000] 183.523: (assign-table-to-group w1 t3 g5) [1.000] 184.524: (assign-table-to-group w1 t4 g3) [1.000] 184.524: (decide-what-to-eat g5) [5.000] 185.525: (decide-what-to-eat g3) [5.000] 189.525: (order-food g5 w1) [1.000] 190.526: (cooking-food g5) [8.000] 198.527: (serve-the-food w1 g5) [1.500] 200.028: (eat g5) [20.000] 200.028: (order-food g3 w1) [1.000] 201.029: (cooking-food g3) [8.000] 209.030: (serve-the-food w1 g3) [1.500] 210.531: (eat g3) [20.000] 220.029: (pay-bill-and-say-bye w2 g5 t3) [3.000] 230.532: (pay-bill-and-say-bye w1 g3 t4) [3.000] 233.533: (assign-table-to-group w1 t5 g2) [1.000] 234.534: (order-food g4 w1) [2.500] 234.534: (decide-what-to-eat g2) [5.000] 237.035: (cooking-food g4) [20.000] 257.036: (serve-the-food w1 g4) [3.750] 260.787: (eat g4) [20.000] 280.788: (pay-bill-and-say-bye w1 g4 t2) [3.000] 283.789: (order-food g7 w1) [2.000] 285.790: (cooking-food g7) [16.000] 301.791: (serve-the-food w1 g7) [3.000] 304.792: (eat g7) [20.000] 304.792: (order-food g2 w1) [2.000] 306.793: (cooking-food g2) [16.000] 322.794: (serve-the-food w1 g2) [3.000] 325.795: (eat g2) [20.000] 345.796: (pay-bill-and-say-bye w1 g2 t5) [3.000] 348.797: (pay-bill-and-say-bye w1 g7 t1) [3.000] * All goal deadlines now no later than 351.797
It’s fair to point out that making use of a planner could be tricky. Hence some planners only work with a single operating system or distribution and that could make developers to drag their feet on it On the plus side, contributions to this world would be very appreciated.
Last but not least I must say that PDDL can be very interesting to get the children introduced to the computer science logic
The code can be found here: