Introduction

This coursework is about designing and evaluating symbolic planning domains and problems using Planning Domain Definition Language (PDDL). It is marked out of 100 and worth 15% of the overall course grade. It consists of four tasks:

• Modelling: formalization of the domain, given a specification (25 marks)

• Implementation:  writing your formalisation in PDDL and testing it on problem instances within an existing PDDL planner (10 marks)

• Experiments: designing an experiment to evaluate a PDDL planner (15 marks)

• Extensions: extending the domain to deal with real world challenges (50 marks)

The files you need are on the course LEARN website: click on “Assessment”(on the LHS menu) and go down to“Coursework 2: Symbolic Planning”. Alternatively, you can access the files here. You will download a file Inf2d-coursework2 .tar .gz which can be unpacked using the command:

tar   - xf   Inf2d - coursework2 . tar . gz

This will create a directory Inf2d-coursework2 which contains: example blocks world domain and problem files (EXAMPLE-blocks-world-domain .pddl,EXAMPLE-blocks-world-problem .pddl), the metric FF planner (ff), and a report template (report .tex).1

Submision

Create a directory Inf2d-cw2-s where  is your matriculation number (e.g 1234567). This directory should include the following files for the submission (if you do not attempt some tasks, do not include associated files):

Please note you need to compile report .tex into report .pdf and submit that.

Before submitting, you should compress the directory into Inf2d-cw2-s .tar .gz. You can do this using the following command:

tar   - cvzf   Inf2d - cw2 - s<matric > . tar . gz   Inf2d - cw2 - s<matric >

You can check that this file stores the intended data with the following command, which lists all the files one will get when one extracts the original directory (and its files) from this file:

tar   - t   Inf2d - cw2 - s<matric > . tar . gz

Also, you can check the size of the above file using the following command, to check that the file stores the intended data:

ls   - l   inf2d - cw2 - s<matric > . tar . gz

Submit this file via LEARN by uploading the file using the interface on the LEARN website for the course. If you have trouble please refer to the blogpost here.

Failure to comply with this specification will result in reduction of 5 marks awarded for your submission.

You can submit more than once up until the submission deadline. All submissions are timestamped automatically. Identically named files will overwrite earlier submitted versions, so we will mark the latest submission that comes in before the deadline.

If you submit anything before the deadline, you may not resubmit afterward. (This policy allows us to begin marking submissions immediately after the deadline, without having to worry that some may need to be re-marked).

If you do not submit anything before the deadline, you may submit exactly once after the deadline, and a late penalty will be applied to this submission, unless you have received an approved extension. Please be aware that late submissions may receive lower priority for marking, and marks may not be returned within the same time frame as for on-time submissions.

For information about late penalties and extension requests, see the School web page here.

Do not email any course staff directly about extension requests; you must follow the instructions on the web page.

Task 1: Modelling (25 marks)

Problem Specification

Consider a post office in which MailBot helps a teller to serve customers. When a customer requests a package, the teller sends the request to MailBot to deliver it (or them).  To do this, MailBot has to bring the desired packages from the warehouse to the delivery belt and turn it on, so as to transport the package to the teller. Before putting the package on the delivery belt, MailBot has to scan it using portable scanner. In this coursework, you will model the warehouse and the MailBot actions using Planning Domain Definition Language (PDDL). In later tasks, you will implement your specification to be executable by the planner ff. To successfully execute teller’s requests, MailBot must have the capability to move through the warehouse, be able to carry and use the scanner, pick up and put packages onto the delivery belt and use the belt to deliver the packages to the teller.

Task 1.1: Describing The World State (5 marks)

Your first subtask is to define the predicates which will describe the world state in your domain. Your world model should be able to describe the following:

• Warehouse, i.e. layout of the warehouse and which cells are connected.

• The location of MailBot and other objects such as the portable scanner, packages, and delivery belt.

• Whether or not the delivery belt is turned on.

• Whether or not a particular package has been scanned by MailBot.

• Whether or not MailBot is holding an object.

In report .tex, name all predicates and constants that you will use to describe the world, and give a brief description in English of what they represent. If you need additional predicates to model the actions in task 1.2 please also describe them here as well. Additionally, in the report write down an initial state as visualized in Figure 1.  Ensure the initial state is a valid PDDL initial state which could be used to create a plan for completing the problem given Task 1.2.  actions:  in particular, make sure that it complies with the syntactic constraints on representing states in PDDL.

Task 1.2: Actions (10 marks)

In this subtask, define the actions MailBot can perform.  Define the arguments, preconditions and effects of each of the actions and include them in report .tex:

• MailBot can move between two tiles if they are connected. MailBot cannot move diagonally or through the wall.

• MailBot can pick up objects, such as the scanner, if it is in the same tile as the object and it is not holding anything else. That is, it can only hold one object at any one time.

Figure 1:  Initial world state of the domain.  The warehouse includes 5x5 grid of tiles (dark/light gray), a portable scanner (red), delivery belt (orange) with a switch (brown outline) which is green when delivery belt is turned off and red when it is turned on, walls (blue), packages (yellow boxes) which have green labels when they are not scanned, and red labels when the packages is scanned., and MailBot located at the center of the warehouse.

• If MailBot is in the same location as a package and holds the portable scanner, it can scan the package (it should only scan the package once for delivery).

• MailBot can turn on the delivery belt switch if it is in the same tile as a switch.

Task 1.3: Backwards state-space search (10 marks)

In this question you must perform the backwards state space search algorithm as described in the lectures and include it in report .tex.  The starting state is given in Figure 2 and the goal is to deliver package 011.  Represent this goal in your PDDL formalisation of the domain.  Spell out the working of the algorithm by specifying at each step which are the relevant actions and what the current goal state is.  State why the relevant actions are selected as relevant.  State clearly which action the algorithm selected at each step. For the purpose of this task you may assume the search always picks the correct action when there is a choice, so you do not need to simulate dead ends and backtracking. Finally, state clearly why the algorithm terminates when it does, and state the valid plan that the algorithm generated for getting from the initial state to the goal.

Figure 2: Task 1.3. initial state. Package 011 is already scanned by Mailbot.

Task 2: Implementation (10 marks)

Implement your domain model in PDDL using the example files in Inf2d-coursework2 as a starting point.2 To test your plan correctness, use the metric FF planner ff.3 To run the planner execute the following command:4

. /ff   - o   <domain - file > . pddl   - f   <problem - file > . pddl

Task 2.1: Test Problem #1 (5 marks)

write problem-1 .pddl in which

• Initial state: as described in Figure 1

• Goal state: deliver package 001

Task 2.2: Test Problem #2 (5 marks)

write problem-2 .pddl in which

• Initial state: as described in Figure 1

• Goal state: deliver package 001 and package 011.

For both of these subtasks, report the plans found.

Task 3: Experiment (15 marks)

To find the plan, the PDDL planner ff uses best-first search in which the world state s is evaluated using a weighted evaluation function:

f(s) = wgg(s) + whh(s)

where g(s) is the cost so far to reach s, h(s) is the estimated cost to get from s to the goal state, and wg,wh  ∈ Z are weights. By default in ff, wg  = 1 and wh = 5.

In this task, you are asked to design and perform the experiment to evaluate the effect of wg  and wh  to the planner’s performance.

Task 3.1: Design (5 marks)

The current problem files are not challenging enough for the planner.  For this subtask, design a harder problem instance problem-3 .pddl, whilst keeping domain .pddl fixed. This problem instance will be used to benchmark the planner’s performance. Describe the design of the problem instance in report .tex.

Task 3.2: Evaluation (10 marks)

Given the problem-3 .pddl, design an experiment and evaluate the effect of different values of wg and wh to planner’s performance. To run the experiments with different values of wg  and wh use the following command 5:

. /ff   - E   - g   <w _g >   -h   <w _h >   - o   domain . pddl   - f  problem - 3 . pddl

Report your experiment results in report .tex. Your experiment analysis should be brief and have both quantitative and qualitative elements.

Task 4: Extensions (50 marks)

In this part you will extend the domain to support additional actions and considerations to make the domain model closer to the real world scenario.

Task 4.1: Energy Station (10 marks)

In a real word, MailBot movement between the tiles has a cost, which the current domain model does not taken into account.  MailBot energy is stored in its battery, which has a capacity of 15 units. Whenever MailBot moves from one cell to the next without holding anything, it loses 1 unit of energy. Whenever it moves from one cell to the next whilst holding something, it loses 2 units of energy. To help MailBot recharge its battery, the warehouse now has a power station (see Figure 3). Whenever MailBot is in the same tile as the power station, it recharges itself, instantly, to the battery’s full capacity of 15 units.

In this task, you are asked to create the extended domain domain-ext .pddl, which must include the additional actions and predicates to handle the energy considerations mentioned above (hint:  use numeric-fluents).  To test your implementation, create problem-ext-1 .pddl, for which the initial state is given in Figure 3.  The goal in this planning problem is that package 001 and package 010 are delivered to the teller. In report .tex, include the plan that ff found.

Figure 3: Initial state for Task 4.1. The power station is coloured in purple. The initial energy level of MailBot is 10 units.

Task 4.2: Limited Power (15 marks)

In a real world, even if MailBot has enough energy, it may be mechanically incapable of lifting objects that are too heavy on its own.  In other words,  MailBot can pick up the scanner and small packages by itself, but for large packages, it needs extra help.  Previously, the teller would help MailBot, but recently the post office got a DeliveryBot that has the same capabilities and constraints as MailBot, except it cannot use a portable scanner.  MailBot and DeliveryBot can together move large packages to different cells and move it onto the delivery belt.

In this task, you are asked to extend domain-ext .pddl to handle the lifting constraints mentioned above. To test your implementation, create problem-ext-2 .pddl for which the initial state is given in Figure 4.  The goal in this planning problem is that package 011 is delivered to the teller.  In report .tex, include the plan that ff found.