Assignment 1 - PDDL Modeling

Your task is to model a planning domain and several of its instances in PDDL. Check the first tutorial for a PDDL modeling example. You should create a domain PDDL file with several problem files. Further, you will write a short report explaining how you model the given domain and instances. The report should contain optimal plans for the instances together with their costs. Submit a zip file containing all your PDDL files and the report to BRUTE. The deadline is March 17.

Bridge and Torch Problem

The planning domain to be modeled generalizes the Bridge and Torch Problem. The problem deals with the following situation. Four guys (let us call them $a,b,c,d$) in the night need to cross a narrow bridge. $a$ can cross the bridge in $1$ minute, $b$ in $2$ minutes, $c$ in $5$ minutes, and $d$ in $8$ minutes. One of the guys has a torch. They can pass the torch among themselves. At most, two guys can cross the bridge at the same time, and one of them must have the torch. If two guys are crossing the bridge simultaneously, they must move according to the slower guy. For example, if $a$ and $c$ cross together, it will take $5$ minutes. The question is, what is the minimum possible time they need to cross the bridge?

Task Definition

We generalize the above problem a bit. We consider a set of islands $I$ that might be connected by bridges. Each bridge is of the same length for simplicity. Further, we have a set of guys $G$. Each of them has a crossing speed, i.e., a time he/she needs to cross a bridge. In the initial state, the guys are located on given islands. Our goal is to get all the guys to the final locations as quickly as possible. Further, there are several torches, each held by a guy. As before, a torch might be passed from one guy to another, but each guy can hold at most one torch. The rules for the crossing are the same as above, i.e., at most, two guys can cross a bridge at the same time, moving according to the slower one, and one holds a torch. We must introduce one more rule. In general, the guys could cross the bridges in parallel to optimize the time needed to get the guys to their final destinations. However, that would not be easy to model in PDDL. Thus, assume that the guys cannot cross bridges in parallel. If one or two guys cross a bridge, the remaining guys wait until they finish the crossing.

Your task is to model this domain in PDDL. Further, create three problem files capturing the following problem instances:

  1. The original Bridge and Torch Problem: We have two islands $I=\{l,r\}$ connected by a single bridge, four guys $G=\{a,b,c,d\}$ of respective crossing speeds $1,2,5,8$ minutes located at $l$, and one torch held by $a$. We aim to move all the guys to $r$ as quickly as possible.
  2. 6 Guys, 2 Islands, and 2 Torches: We have two islands $I=\{l,r\}$ connected by a single bridge, six guys $G=\{a,b,c,d,e,f\}$ of respective crossing speeds $1,2,3,4,5,6$ minutes located at $l$, and two torches $t_1,t_2$. $a$ holds $t_1$ and $b$ holds $t_2$. Again, we aim to move all the guys to $r$ as quickly as possible.
  3. 6 Guys, 4 Islands, and 2 Torches: We have four islands $I=\{i_1,i_2,i_3,i_4\}$ connected by bridges as shown below. Further, we have six guys $G=\{a,b,c,d,e,f\}$ of respective crossing speeds $1,2,3,4,5,6$ minutes located at $i_1$, and two torches $t1,t2$. $a$ holds $t_1$ and $f$ holds $t_2$. In this instance, we aim to get $a,b,c$ to $i_3$ and $d,e,f$ to $i_4$ as quickly as possible.

i3     i4
 \    /
  \  /
   i2
   |
   |
   i1

Find an optimal plan for each of the problem instances together with their costs using a planner and report your results. The cost of the optimal plan should correspond to the crossing time needed to get the guys to their final destinations. For the first problem instance, the cost should be 15, as you can read on the wiki page Bridge and Torch Problem. The second problem has the optimal solution of cost 16. The optimal cost of the last problem is 33.

courses/pui/assignments/assignment1-1.txt · Last modified: 2024/02/29 11:08 by xhorcik