561 – Introduction to Symbolic Artificial Intelligence (CW1)
(Submission by groups of two students allowed/welcome) Due date: February 7, 2020
Electronic submission (code on LabTS + report on CATe)
In this exercise, you have two tasks to complete for the problem described below:
1. Model the problem using PDDL (Planning Domain Definition Language) and run an off-the-shelf planner to solve it (details for this task are given in Part 1 below).
2. Implement a number of search algorithms and heuristic functions (see Part 2 for a full descrip- tion).
Problem Description
The problem consists of an n×m grid whose tiles can contain one of the following: an empty space (.), a red sweet (r), a green sweet (g), or a blue sweet (b). The grid is indexed left-right and top-bottom, where (i,j) stands for the tile in row i and column j. Figure 1a shows an example grid.
012 0rgb 1.r. 2.gb
(a)
1: switch[(0,1),(1,1)]
2: remove[(0,0),(0,1)]
3: switch[(0,2),(1,2)]
4: remove[(1,2),(2,2)]
5: remove[(1,1),(2,1)]
(b)
Figure 1: An example 3 × 3 grid (a) and an optimal plan that solves it (b).
The state space is given by the set of all possible grids (i.e., any combination of sweets in an n × m
grid). The goal state represents a grid where all tiles are empty. The actions are the following:
• switch[(i,j),(k,l)]: switches the content of positions (i,j) and (k,l) if they are contiguous (i.e., in the same row or column) and their content is different.
• remove[(i,j),(k,l)]: removes the sweets at positions (i,j) and (k,l) if they are contiguous (i.e., in the same row or column) and they contain the same type of sweet. When removed, all the positions become empty (.).
All actions have a step cost 1. Given an initial state, the objective is to find a plan (i.e., a sequence of actions) that leads to the goal state. Figure 1b shows a possible optimal plan for the grid in Figure 1a. Figure 2 shows an excerpt of a search tree (no particular algorithm has been used to generate the tree—it is just an example).
1
rgb .r. .gb
switch[(0,1),(1,1)]
switch[(2,0),(2,1)]
rrb . . . . . . . rgb .g. ……. .r.
.gb g.b
remove[(0,0),(0,1)]
. . . ..b . . . .g.
.gb
switch[(0,2),(1,2)]
… .gb .gb
remove[(1,2),(2,2)]
… .g. .g.
remove[(1,1),(2,1)]
… … …
. . . .
Figure 2: An excerpt of search tree for the example in Figure 1.
Part 1 – PDDL Model of the Problem (40%)
In this part, you will model the problem described above using PDDL. Therefore, you will create two types of files:
• A single domain file (called domain.pddl) that specifies the types, predicates and the actions schemas (parameters, preconditions and effects). There should be two action schemas: one for switch and one for remove. Besides, there should be predicates for expressing (1) whether two locations are adjacent, (2) which colour has a given location, (3) whether two colours are different and (4) whether a given colour represents an empty tile.
• Three problem files (named problem1.pddl, problem2.pddl and problem3.pddl respectively) each of which specifies a different initial grid configuration shown in Figure 3. All three problem files must have the same the goal condition, i.e., all the tiles must be empty.
You are free to define your own predicates and actions as long as these describe the problem adequately. You must however include comments that describe the predicates and action parameters you have used, and any assumptions you have made when modelling the problem.
You are provided with a minimal skeleton of both kinds of files. You have to fill the types, predicates
2
.b.r
r..g
….
brgr
and actions for the domain file, and the objects, initial state and goal condition for each problem file To solve the planning tasks, you need a planner. For this exercise, you can use the PDDL editor in
http://planning.domains.
Part 2 – Implementation of Search Algorithms and Heuristics (60%)
In this part you will implement three search algorithms introduced in the lectures: Breadth First Search (BFS), Depth First Search (DFS) and A*.
2.1 Description
The skeleton is formed by the files below. You should only modify the files marked with an asterisk (*). Section 2.3 provides some hints regarding the order in which they should be implemented.
Action.h Defines an action, which consists of a name and a vector of Position parameters. The default constructor creates an action whose name is none and has no parameters.
AStartAlgorithm.(h/cpp)* Implementation of the A* algorithm. You must override the abstract methods in SearchAlgorithm using the appropriate data structure.
BFSAlgorithm.(h/cpp)* Implementation of the BFS algorithm. You must override the abstract meth- ods in SearchAlgorithm using the appropriate data structure.
DFSAlgorithm.(h/cpp)* Implementation of the DFS algorithm. You must override the abstract meth- ods in SearchAlgorithm using the appropriate data structure.
HeuristicFunction.(h/cpp)* It defines an abstract class HeuristicFunction that has an abstract method evaluate that takes a State as input and returns an estimation of the cost to reach the goal. You will implement the different heuristics here by subclassing the abstract class.
Grid.(h/cpp)* This class builds a grid from a given state and allows easy manipulation of its content. You have to fill three methods: isEmpty, getApplicableActions and applyAction. Feel free to add more methods to the file if needed (e.g., to compute heuristics).
main.cpp Main program used to start the search.
SearchAlgorithm.(h/cpp)* You have to fill the search method, which implements the general graph search algorithm (see slide 67 of the lecture notes). The abstract methods addToFrontier, selectFromFrontier, isFrontierEmpty and visitState must be implemented in the DFSAlgorithm, BFSAlgorithm and AStarAlgorithm subclasses. In each of these you will have to use the appro- priate data structure for the frontier.
3
rgb .r. .gb
(a) problem1.pddl
Figure 3: Grids to be used as the PDDL problem files in Part 1.
bg.br rbg.b
(b) problem2.pddl
(c) problem3.pddl
SearchProblem.(h/cpp)* Itstorestheinitialstateandprovidesmethodsforgettingit,askingwhether a state is the goal and getting a list of the possible successors of a given state. You have to fill two methods: isGoalState and getSuccessors.
utils.h It contains (1) the definition of the State type (a string), (2) the definition of the Position type (a pair of int), (3) helper functions to check whether a char is a sweet or an empty space and (4) a helper function for loading a state from a file.
The code contains some lines starting with TODO:… to indicate where you should write the code. 2.2 Compiling and Running the Code
To compile the code, you have to use the following commands:
cmake CMakeLists.txt
make
After successfully compiling the code, you can run it using the following command
./search
where:
• grid-file is the path to a file encoding the grid (details below),
• algorithm is the search algorithm to be used (bfs, dfs or astar), and
• heuristic is the heuristic to be used with A* (zero, num-sweets or custom).
The grids are formatted similarly to the example above. Each grid is encoded in a single file whose first line contains the number of rows and the number of columns of the grid. Then, the following lines represent the grid using the same symbols introduced before. For example, the previous example grid is represented by a file containing the following:
33 rgb .r. .gb
You can find some example grids in the grids folder. You can use them to test your search algorithms. 2.3 Tasks
The following enumerates the tasks you have to complete. They are shown in the order you will need to implement them:
1. Implement the isEmpty, getApplicableActions and applyAction methods from the Grid class. For the actions, use the naming shown above (switch and remove).
2. Implement the isGoalState and getSuccessors methods from the SearchProblem class.
3. Implement the search method from the SearchAlgorithm class.
4. Implement the inherited methods for BFSAlgorithm, DFSAlgorithm and AStarAlgorithm.
5. Implement the evaluate method for the NumSweetsHeuristicFunction class. It has to return the number of sweets that the given state contains.
4
6. (Bonus) Implement your own heuristic function in the evaluate method of CustomHeuristicFunction.
Submitting Your Work
You are required to make TWO submissions.
On LabTS
You are required to submit your code electronically via LabTS (as usual).
DO NOT include any additional print statements in your submitted code. Use them by all means for tracing/debugging but do not include them in your submitted program.
On CATe
You have to submit a short report (in .pdf formal, 2 pages max) answering the following questions about Part 2.
1. Compare the implemented algorithms using the provided information: time, number of expan- sions, number of visits and plan length. You must fill tables similar to the ones in Table 1 for each of the previous statistics. Note that the first column corresponds to the testing grids we have provided you with.
2. How does A* with the heuristic always returning zero (ZeroHeuristicFunction) perform com- pared to other algorithms? Is there any similarity? If so, explain why.
3. Is the heuristic based on computing the number of sweets (NumSweetsHeuristicFunction) ad- missible? Justify your answer.
4. (Bonus) Describe the heuristic you have implemented in the CustomHeuristicFunction class. Is it admissible? Justify your answer. What are the differences in terms of performance with respect to the other implemented heuristics and algorithms? What do you think causes such differences (if any)? Remember to add an extra column in the tables.
Time (seconds) Plan length
Problem DFS BFS A* (Zero) A* (NumSweets) Problem DFS BFS A* (Zero) A* (NumSweets)
1—-1—- 2—-2—- 3—-3—- 4—-4—- 5—-5—- 6—-6—- 7—-7—- 8—-8—-
Table 1: Reference tables for the report. There must be similar tables for the number of expansions and the number of visits.
5
Marking
Ensure that your submission COMPILES AND EXECUTES without errors on the lab machines. 25% of marks will be deducted for programs that do not compile or that generate run-time errors.
Marks will be deducted for overcomplicated or obscure solutions.
A proportion of marks is awarded to the style of your solutions. This includes layout as well as appropriate use of comments. Marks will be deducted for unreadable code.
6