====== Assignment 1 - PDDL Modeling ======

Your task is to model a planning domain and several of its instances in PDDL. Check the [[courses:pui:tutorials:tutorial01|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 [[https://en.wikipedia.org/wiki/Bridge_and_torch_problem|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?

{{ :courses:pui:assignments:crossing.jpg?nolink&600 |}}


===== 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:
  - **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.
  - **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.
  - **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.

<code>
i3     i4
 \    /
  \  /
   i2
   |
   |
   i1
</code>

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 [[https://en.wikipedia.org/wiki/Bridge_and_torch_problem|Bridge and Torch Problem]]. The second problem has the optimal solution of cost 16. The optimal cost of the last problem is 33.

/*
Your first task is to model a problem called **Grid-Mario** in PDDL. The modeled problem is supposed to be a representation of a game Grid-Mario that we want to solve in the means of classical planning. Detailed description of the game's mechanics is given below. 

Everyone has to model the world representation including the agent’s movement on the grid with all known obstacles. Additionally, everyone gets a random selection of 2 other features from the problem domain they have to model as well. For every combination of features you get 4 problem instances to model. One for each individual mechanic and then a complex one to test all modeled mechanics at once. 

We recommend using [[http://editor.planning.domains | online editor]] for modelling the PDDLs but the choice is yours.

To find your features, check out this {{ :courses:pui:assignments:pui_pddl_.pdf | table of assigned features}}.

Download images of the assigned problem instances

  * {{ :courses:pui:assignments:pui_board_-_hw1-pddl-box-keys.pdf |Boxes + keys}}
  * {{ :courses:pui:assignments:pui_board_-_hw1-pddl-box-spring.pdf |Boxes + springs}}
  * {{ :courses:pui:assignments:pui_board_-_hw1-teleports-keys.pdf |Teleports + keys}}
  * {{ :courses:pui:assignments:pui_board_-_hw1-teleports-springs.pdf |Teleports + springs}}
  * {{ :courses:pui:assignments:pui_board_-_hw1-levers-keys.pdf |Levers + keys}}
  * {{ :courses:pui:assignments:pui_board_-_hw1-levers-springs.pdf |Levers + springs}}

To better understand the image representation of the problem instances, check out {{ :courses:pui:assignments:pui_board_-_hw1-legend.pdf | legend}}.

===== Task Submission =====

This task is **mandatory** and you can recieve maximum of **5 points**.

Model the domain and 4 given problem instances in PDDL and submit all PDDL files in a .zip file to BRUTE. In total, you should submit one archive with 5 PDDL files. 

**Filenames** 
  * domain.pddl - modeled domain
  * p01.pddl - problem instance that tests movement
  * p02.pddl - second problem instance (lever / box / teleport) 
  * p03.pddl - third problem instance (keys / springs)
  * p04.pddl - last given problem instance testing all modeled mechanics 

There is no automatic evaluation for this task. 


===== Deadline =====
This task will be assigned during the 2. week of tutorials. You have one week to submit it. 

Deadline for Monday tutorials: **6.3.2023 - 23:59**

Deadline for Wednesday tutorials: **8.3.2023 - 23:59**
 
===== Rules of Grid-Mario =====

**Map**
  * Map is represented by a grid
  * Size of the map is arbitrary (n x m)

**Agent** 

  * Fits exactly one tile
  * Can move from one tile to another in 4 directions (up, down, left, right)
  * Cannot walk into boxes, walls, holes (he is very careful)
  * Can share a tile with levers or items
  * The inventory has capacity of one item

**Items** 

  * There are two types of items in the game - keys, springs
  * They both (surprisingly) fit into agent’s inventory
  * Only one item can be carried by the agent
  * Items cannot share a tile
  * Agent can swap item from their inventory for a different item located on the same tile

**Push box** 

  * Agent can push one box at a time
  * Agent cannot stand on the box or pull it
  * Box has to be pushed in one line (agent → box → clear spot) to a tile that is not hole / wall
  * Box can be pushed onto an item / lever but the item cannot be picked up / used as long as the box is on top of the item

**Teleport**

  * Teleport is located on a tile
  * In order to use the teleport, agent has to stand on the same tile
  * Teleports are linked in fixed pairs and work bidirectionally
  * They can be used as many times as needed
  * Using the teleport is optional 

**Levers** 

  * Lever is located on a grid tile, it can share a tile with the agent
  * Once lever is pulled it fills in a designated hole that turns into regular tile
  * One lever is linked to a one hole
  * Lever cannot be un-pulled and pulling it again doesn’t have any effects

**Keys** 

  * Keys are items that can be placed on a tile together with an agent
  * Key can be picked up, put down and used to unlock doors that block paths between tiles
  * To unlock a door, the agent has to stand next to the door 
  * Every key is universal (fits to any door) but once used it disappears
  * Doors are located between tiles (not placed on tiles), path between tiles gets restored once the door is open
  * Door cannot be locked or closed again

**Springs** 

  * Spring is an item that allows the agent to jump over holes and walls of width equal to one tile
  * Spring can be picked up, carried by agent and put down
  * Once spring is down agent can use it to jump over one hole/wall in front of them
  * The jump is performed in straight line (agent + spring → hole/wall → clear spot)


===== Tips for PDDL Modeling =====

  * Grid can be modelled both using coordinates or tiles as objects
  * Go one action at a time and always debug on the smallest possible problem instances
  * All predicates not stated in the initial state definition will be set to false automatically (if you put (at agent t1) to init, every other (at agent ?t) will be not true)
  * All types without a parent will have ‘object’ type as their parent
  * The editor can smell fear
  * You can save your session + get its ID so it can be restored in the online editor

==== Common Mistakes ====

  * incorrect pairing of parentheses
  * typos in types, predicates, arguments
  * missing predicate from a long list of repeating ones (tile x1 y1, tile x2 y2, …)
  * domain name doesn’t match in problem and domain definitions
  * some features of the world are not defined in :init (grid connections, clear tiles, item positions, …)

===== Restrictions =====

For the purpose of this homework, please use only PDDL requirements provided in the template, no extra ones are necessary to model grid-Mario. Using types is optional (predicates can be used instead). Please use only conjunctions of predicates for defining actions.

===== Templates =====

For simpler writing here are templates for both domain definition (also provided in the [[http://editor.planning.domains|online editor]] ) and problem definition. 

**Domain definition in PDDL**
<code>
(define (domain domainName)

    (:requirements
        :negative-preconditions
        :typing
    )

    (:types

    )

    (:predicates
    
    )

    (:action actionName
        :parameters (?x - foo)
        :precondition (and 
		(foo) 
		(fuu)
	)
        :effect (and 
		(fii)
		(not (fee))
	)
    )
)
</code>

**Problem definition in PDDL**
<code>
(define (problem problemName) (:domain domainName)

(:objects
    x - type
)

(:init
    (fee)
)   

(:goal
    (and
        (foo)
    )
)
)
</code>
*/