CPS721: Assignment 5

PROLOG Instructions: When you write your rules in PROLOG, you are NOT allowed to use “;” (disjunction), “!” (cut), “->” (if-then), and the different variants of equality and inequality (“\=”, “==”, “=\=”, “=:=”, etc.). You are only allowed to use “;” to get additional responses when interacting with PROLOG from the command line. Note that this is equivalent to using the “More” button in the ECLiPSe GUI. You are also not allowed to use built-in predicates that we did not cover in class, such as “findall”, “setof”, “bagof”, etc. You may use “member” and “append”.

We use ECLiPSE Prolog release 6 to mark the assignments. It is your responsibility to check that your code runs in ECLiPSE Prolog release 6. If you write your code on a Windows machine, make sure the files are saved as plain text and are readable on Linux machines. Ensure your PROLOG code does not contain any extra binary symbols. You can test this by ssh-ing onto the department servers (ie. moon) and running ECLiPSE remotely from the command-line.

Submission Instructions: You should submit ONE zip file called assignment5.zip. It should contain 4 files:

robocup.pl dishwashing.pl robocup_report.txt dishwashing_report.txt

All these files have been given to you and you should fill them out using the format described. Ensure your names appear in all files, and your answers appear in the file sections as requested. Do NOT edit or delete any lines that begin with the “%%%%% SECTION:”. These are used by the auto-grader to locate the relevant code. You will lose marks if you edit such lines.

Your submission should not include any other files than those above. Do not submit .rar, .tar,

.7zip, other compression format aside from .zip, or submit multiple .zip files. If you do so, you will lose marks. All submissions should be made on D2L. Submissions by email will not be accepted.

As long as you submit the file with name assignment5.zip, you may submit multiple times, as it will overwrite an earlier submission. You do not have to inform anyone if you do. The time stamp of the last submission will be used to determine the submission time.

READ THIS INFORMATION BEFORE BEGINNING THE ASSIGNMENT

In this assignment, you will be creating programs to solve several planning problems. For each, there are multiple provided files:

• A file containing the generic planner (this is shared between all problems). You should NOT edit this file.

• File(s) with initial state information. You should NOT edit these files, but we encourage you to create your own and use them for testing as detailed below.

• The main submission file in which you will be defining the axioms and declarative heuristics.

• A report file in which you will be documenting your results.

Below, we provide more information on each of these files. We also provide some information about how we will test your programs.

Main File

The main files for questions 1 and 2 are robocup.pl and dishwashing.pl, respectively. To run your programs you should load these files. They have been set up so that they will also load the additional files as needed.

You will notice these files have several Prolog features that you haven’t seen before. First, in the setup section, you will see rules of the form :- dynamic robotLoc/2. This line tells Prolog to allow the predicate robotLoc to be defined in different non-consecutive lines in your program. This is necessary to allow the initial state of the planning problem to be stored in a different file than your axioms. You should NOT edit these sections of the files.

The setup section also contains the rule :- [planner]. This line tells Prolog to load in the file planner.pl, which contains the generic planner used for all problems. You should NOT edit the planner section. You will also notice that a similar rule is used to load in the initial state from a file in the init section. We will describe this file in further detail below.

Next, you will see the goal_states section. Here, multiple different goals have been defined for you. Notice that the predicate is defined as goal_state(ID, S), where S is the situation, and ID is the number of the corresponding goal. This is slightly different than the goal_state predicate introduced in class. This newer version will allow you to easily jump between goals when testing your program, by calling solve_problem with a different goal ID. We will describe this in detail below. You may find it useful to add additional goals for testing, especially when starting out. You can do so in this section. Please include this section in the submission, but its contents will be ignored.

The remaining sections then provide space to define your action precondition axioms, your suc- cessor state axioms, and your declarative heuristics.

Planner File

The planner can be found in the file planner.pl. You should NOT edit this file, but you should look at it to understand how to run the planner. In it, you will see mostly familiar predicates, though with slight changes in some cases. The main predicate you will call to run the planner is

solve_problem(Mode, GoalID, Bound, Plan)

Just as in class, the Bound variable is a maximum on the length of the plan to find, and Plan is the found plan. The other two arguments are input arguments that are intended to simplify the process of testing your program. GoalID defines which goal to use. This will allow you to easily test with the different goal conditions defined in the main files. The Mode argument allows you to specify which “mode” to run the planner in. If it is set to heuristic, then the planner will use declarative heuristics in the form of the useless predicate to cut off search to avoid unnecessary work. If it is set to regular, then the declarative heuristics are ignored, and the standard reachable definition is

used (ie. without pruning). Notice that the reachable predicate has been modified accordingly to allow for these different usages.

For example, if you call solve_problem(regular, 2, 5, Plan), you are asking the planner to find a plan of no more than 5 actions, such that the goal with ID 2 is satisfied, and it should do so without using declarative heuristics for pruning.

You should NOT submit the planner file as part of your submission as we will automatically include it when testing. We will ignore your submitted file if you do.

Initial State File

For each problem, we have provided multiple initial state files which identify the fluents and auxiliary predicates which hold in different initial situations. These are loaded in the init sections of the main files using a line like :- [dishwashingInit1]. To change between initial states, simply comment out the unused initial states and uncomment the one you want to use. Please include this section in the submission, but its contents will be ignored. Note that it is a good idea to restart eclipse when switching initial states to avoid having fluents for multiple initial states open at the same time.

Changing the initial state is a good way to test your program in a variety of situations. You can add your own by creating new files that use this format. You then merely need to modify the init section in the main files to load in your desired initial state. This is an especially good idea when testing out your preconditions and axioms or debugging your program. However, you should complete your final tests with the given initial states. You should NOT submit any initial state files as part of your submission.

Self-Testing Your Axioms

Debugging axioms can be challenging. Don’t forget you can always directly check if an action is possible by using poss as a query. For example, to check that an action act is applicable in some situation given by [c, b, a], you can always query for poss(act, [c, b, a]). Similarly, if you want to check whether a fluent f(5, S) is true in a particular situation [c, b, a], you can always query for f(5, [c, b, a]). Doing so is a much more effective approach for debugging than just testing your axioms by calling solve_problem, as the latter gives very little feedback for why failure is occurring. It is also one of the primary ways we will test your submissions.

The initial states and goals given are of varying difficulty. Some are not feasible to solve without declarative heuristics. Thus, it is useful for you to first confirm your program is working on the easier ones, before even attempting the harder ones. To that end, you may find it useful to create your own initial states and goal states that will help you better understand if your program is working.

Marking Your Program

We will be testing your programs in two ways. First, we will try your axioms on different initial states to ensure that they correctly compute preconditions and effects. Second, we will also run your complete planner to ensure the whole system works together. Importantly, we will run your program on DIFFERENT initial and goal states than those given. Thus, your declarative heuristics should not be specific to those provided. In other words, make sure your declarative heuristics are general enough so that they can be applicable to solving any planning instance of the planning problem with arbitrary constant names, and different combinations of initial/goal states. We have tried to give different combinations of initial and goal states so you better understand the set of possible planning problems you will be tested on. More details is given on this topic in each of the questions.

When grading your programs using solve_problem, we will not require you to get all solutions by calling “More” or “;”. You should try to get additional solutions when testing your own program, but we will not consider it for marking. Instead, we will take plans outputted by your system, and verify it using our solution to ensure it is a valid plan, and is the shortest of all possible plans.

For your declarative heuristics, you don’t need to get the absolute fastest performance possible. Full marks will be awarded if a reasonable speedup is seen, and the returned plans are still valid (and optimal). Different parts of the assignment may also be marked manually.

1. The Robocup Problem [45 marks]

   We have already looked at variants of the robocup problem on previous assignments, largely to determine who can score or who can pass to whom. In this assignment, we will consider using planning to identify how to satisfy given objectives that a team may have while playing a game. Here, we are assuming you are controlling all the robots, and so you are planning for all of them collectively.

   We are also making several simplifying assumptions, but they are different than those considered on previous assignments. In particular, we will represent the field as a grid, such that there can be only one robot at any location at one time. There will be opponent robots at certain locations in the grid, but to keep things simple, they will not move. Robots can move, pass, and shoot, but only one robot can do one of these actions at any time (ie. robots do not move concurrently).

    

   Figure 1: An example robocup scenario.

   An example initial state is shown in the figure above. In this example, the field consists of 5 rows and 5 columns, there are five robots (r1, r2, r3, r4, and r5), there are five opponents (shown as x’s), and robot r1 currently has the ball. Note, we have given this file to you as robocupInit2.pl.

   Let us begin by defining the predicates that will be used to define states of this environment. We begin with the fluents:

   • robotLoc(Robot, Row, Col, S): Robot is at row Row and column Col in situation S.

   • hasBall(Robot, S): Robot has the ball in situation S.

   • scored(S): the ball is in the net in situation S.

     We will also have the following auxiliary predicates that do not have a situational argument:

   • numCols(X) defines that the number of columns for the field is X.

   • numRows(X) defines that the number of rows for the field is X.

   • goalCol(X) defines that the net is in column X.

   • opponentAt(Row, Col) defines that there is an opponent at the location Row, Column.

   • robot(R) defines that R is a robot.

     Facts based on these auxiliary predicates are included in the initial state file. See robocupInit1.pl

     and robocupInit2.pl as examples.

     We can now define our actions as follows:

   • move(Robot, Row1, Col1, Row2, Col2): this action means Robot moves from the location of Row1, Col1 to Row2, Col2. Robots can only move one row or column at a time, and cannot move diagonally. They also cannot move into a location where there is another robot or an opponent. A robot does not need to have the ball to move. For example, in Figure 1, r5 can move to row 3, column 1 in a single step, but they cannot move to row 3, column 0 or row 4, column 1 in a single step. Note that a robot cannot move off the field. A robot can also not move to the same location they are already at (ie. move(R, 1, 2, 1, 2) is not a valid action).

   • pass(Robot1, Robot2): this action means Robot1 passes the ball to Robot2. In order to do so, Robot1 must have the ball. They can pass the ball any number of rows or columns in the vertical or horizontal directions, but they cannot pass diagonally. A robot may not pass the ball through a location where there is an opponent robot, but they MAY pass the ball through a grid location where there is a teammate robot (ie. the teammate just lets it pass by). After a pass, Robot1 no longer has the ball, and Robot2 has the ball. For example, in Figure 1, r1 can pass the ball to r2 or r3, but not r4 (no diagonal passes) or r5 (opponent in the way).

   • shoot(Robot): this action means Robot shoots the ball at the net (and scores). The robot must have the ball to shoot it. They can only shoot the ball if they are in the same column as the net (ie. no diagonal shots). They can shoot any number of locations as long as there are no opponents in the way. Like passes, teammates do not get in the way of a shot. The robot no longer has the ball after they shoot it. For example, in Figure 1, a robot could shoot (and score) from locations row 2, column 2, as well as row 3, column 2, and row 4, column 2. There are no other locations in the Figure from which a robot can shoot from. Whenever a robot shoots, they will score.

     For this problem, you will write the precondition and successor-state axioms for this problem, as well as declarative heuristics. Notice that we have given you 6 goals for the first initial state and two for the second. For all of these, you should manually solve the problem yourself so you know what the optimal solution is. In addition, the following will hold for a working solution:

   • Goals 11-14 should only take a few seconds to solve.

   • Goal 15 will take roughly 10-30 seconds in regular mode.

   • Goal 16 is only solvable in a reasonable time with declarative heuristics.

   • Goal 21 (for initial state 2) make take 1-3 minutes to solve in regular mode.

   • Goal 22 only solvable in a reasonable time with declarative heuristics. You should now complete the following tasks:

     1. [18 marks] Write precondition axioms for all actions. You should put your precondition ax- ioms and any helpers for them in the precondition_axioms_robocup section. Recall that to avoid potential problems with negation in Prolog, you should not start bodies of your rules with negated predicates. In addition, make sure that all variables in a predicate are instantiated by constants before you apply negation to the predicate that mentions these variables. Finally, remember that your precondition axioms should only capture if you can apply an action, not if you should apply the action. Just let the planner decide if it should apply the action or add such information as declarative heuristics as required for part (c).

        HINT: You may want to introduce helper predicates to more easily check some of the action pre- conditions.

     2. [12 marks] Write successor-state axioms that characterize how the truth value of all fluents change from the current situation S to the next situation [A | S]. These should be added to the section successor_state_axioms_robocup. Recall that you will need two types of rules for each fluent:

        1. rules that characterize when a fluent becomes true in the next situation as a result of the last action.

        2. rules that characterize when a fluent remains true in the next situation, unless the most recent action changes it to false.

           Note that when you write successor state axioms, you may sometimes start bodies of rules with nega- tion of a predicate, e.g., with negation of equality. This can help your program work a more efficiently.

     3. [10 marks] You will now write declarative heuristics that the planner can use for pruning when run in “heuristic” mode. Recall that the predicate useless(A, ListOfActions) is true if an action A is useless given the list of previously performed actions. This predicate provides (domain dependent) declarative heuristic information about the planning problems that your program solves. The more inventive you are when you implement this predicate, the less search will be required to solve the planning problems. However, any implementation of rules that define this predicate should not use any information related to the specific initial or goal situations. Your rules should be general enough to work with any of the initial and goal states, as well as similar ones involving specifying where the robots should end up at or where the ball should end up at. When you write rules that define this predicate use common sense properties of the application domain.

        Write your rules for the predicate useless in the file robocup.pl in the section called declarative_heuristics_robocup. You should include at least 5 declarative heuristics. Put com- ments beside each declarative heuristic explaining what they are doing.

        We note that many of the declarative heuristics considered in class worked by avoiding sequences of actions that go back and forth between two states. For example, this was done when avoiding doing climbOnBox immediately after climbOffBox in the bananas problem from the lectures. There are some such heuristics possible for this domain (and you should implement them), but not many. Instead, you should consider other types of useless actions. This can include pruning actions that shouldn’t be done more than once, or eliminating some of the “symmetries” that arise in this problem due to the fact that certain sets of actions can be done in a different order, but still end up in the same state. For example, if we do pass(r1, r2) and then move(r3, 1, 1, 2, 1) in situation S, the resulting state is the same as first doing move(r3, 1, 1, 2, 1) and then doing pass(r1, r2). This is because these actions are independent in the sense that they have no effect on each others preconditions or effects.

        Using declarative heuristics to prune such cases may not allow the planner to find all possible plans when calling “More” or ”;”, but it can dramatically speed up the planning process when searching for a single solution. You are encouraged to use such declarative heuristics for this problem. However, you should ensure your heuristics do not make it impossible to find solutions (or prune optimal solutions) in the types of initial state/goal state pairs we have given you.

        TIPS: It is generally best to ensure your axioms work correctly in regular mode before testing your declarative heuristics. This will help you debug issues by helping you isolate which part of your program is causing issues. When working on your declarative heuristics, it is often best to first focus on problems of “medium difficulty” (ie. that take 10-30 seconds) in reqular mode. This is because such tasks take long enough that you can see appreciable gains using the declarative heuristics, while not taking so long that it is hard to try a test out different heuristics. Once you make gains there, you can test your heuristics (and possibly add more complex heuristics) on harder problems.

     4. [5 marks] Document the results of testing your planner (ie. calling solve_problem) on this problem and put them in the file robocup_tests.txt. Fill out the sections with the following details:

     • cpu_details : include information about the processor (mainly speed), amount of RAM, and operator system you ran your tests on.

     • summary : summarize your results in 5-10 sentences. In particular, describe which states you tested on, your timing results, and how much speedup you saw when using declarative heuristics. Report any other interesting behaviour you saw.

     • log : show the log of your tests (ie. copy the interaction) including the runtime and the output plan, when using both the regular and heuristic modes. You do not have to find more than one plan per problem (though you may want to do that yourself when testing).

     You tests should be performed on at least goals 11, 12, 13, 14, 15, and 21. You may wish to include tests on other goals as well, but this is not required.

2. Dishwashing [55 marks]

   In the future, people may have household robots to help them with chores. For this question, you will build a planning system for dishwashing that could be used by such a robot.

   We consider a simple version of this problem described as follows. A robot with two arms is standing by the sink. There are plates and glasses on the counter. The robot should pick up the dirty dishes, wash them, and put them in the dish rack to dry. The robot has two utensils (called scrubbers) they can use for cleaning the dishes. These are a sponge and a brush. Plates can only be cleaned with a sponge and glasses can only be cleaned with a brush. To clean a dirty dish, it should be scrubbed with a soapy scrubber and then rinsed to get rid of the soap and dirt. Note that we are assuming that a scrubber can be used to scrub an arbitrary number of dishes without needing more soap or becoming dirty.

   To describe this planning problem, we will use the following auxiliary predicates:

   • place(X) states that X is a place that items can be located at. X will either be counter or

     dish_rack.

   • scrubber(X) states that X is a utensil for cleaning dishes. X will either be a sponge or a brush

   • glassware(X) states that X is glassware (ie. a glass cup or glass bottle).

   • plate(X) states that X is a plate.

   • dish(X) states that X is a plate or glassware.

   • item(X) states that X is an item the robot can hold. This includes glassware, plates, and scrubbers.

     The definition of place, scrubber, and item are given in the section aux_dishwashing in dishwashing.pl.

     Do not change this section. Notice that glassware and plate are used to assign the types to objects in the initial state files, while dish and item are useful predicates that can be used to refer to different groups of objects.

     The fluents in this problem are as follows:

   • holding(X, S) holds if the robot is holding item X in S.

   • numHolding(C, S) holds if the robot is holding C different items in S. Since the robot has 2 hands, this is at most 2 items.

   • faucetOn(S) holds if the faucet is on in S.

   • loc(X, P, S) holds if the location of item X in situation S is P. Here, P is a place. If the robot is holding X in S, then no such loc fluent will hold for X in S.

   • wet(X, S) holds if the item X is wet in S.

   • dirty(X, S) holds if the item X is dirty in S. Recall that scrubbers never get dirty.

   • soapy(X, S) holds if the scrubber X is soapy in S. We can now define our actions as follows:

   • pickUp(X, P): picks up item X from place P. After applying this action, X will no longer be at P and it will be held by the robot. Note that the robot must not already be holding two items to pickup another.

   • putDown(X, P): puts down item X to place P. Only applicable if X is being held by the robot. After applying this action, X is no longer held by the robot.

   • turnOnFaucet: turns on the faucet. This action is only applicable if the robot has a free hand (ie. it is holding at most one item) to turn on the faucet.

   • turnOffFaucet: turns off the faucet. This action is only applicable if the robot has a free hand to turn off the faucet.

   • addSoap(X): adds soap to X. This action is only applicable if X is a scrubber that is held by the robot. The robot must have a free hand to add soap to the scrubber. The scrubber will be soapy after adding soap.

   • scrub(X, Y): scrubs dish X using scrubber Y. Both X and Y must be held by the robot to apply this action. If X is glassware, it can only be scrubbed with a brush. If X is a plate, it can only be scrubbed with a sponge. If Y is soapy, then X will be soapy after it is scrubbed. If X is a dirty dish, it will remain dirty after it is scrubbed (ie. the food stays on it until the dirt and soap is rinsed off). Note that scrubbing a dish with a scrubber that has no soap on it will have no effect on the dish.

   • rinse(X): rinses item X. The faucet must be on and X must currently be held by the robot in order to rinse it. If X is a scrubber that is soapy, it will no longer be soapy after rinsing it. If X is a dish that is both soapy and dirty (ie. because it was scrubbed using a soapy scrubber), then it will be clean and not soapy after being rinsed. In all cases, an item will be wet after being rinsed.

     As in the first question, you will write the precondition and successor-state axioms for this problem, as well as declarative heuristics. We have provided 3 initial states and a variety of goal states for testing:

   • Goal states 11, 12, and 13 for initial state 1 have an optimal solution length of 2, 4, and 6 steps, respectively. These should all be solved in a matter of seconds.

   • Goal state 14 for initial state 1 has a solution length of 8. It will take 10-30 seconds in regular mode.

   • Goal state 15 for initial state 1 has a solution length of 10. It will take 30-120 seconds on heuristic mode, and quite a while on regular mode.

   • Goal state 21 for initial state 2 has a solution length of 6, and will take 10-40 seconds in regular mode to solve.

   • Goal state 22 for initial state 2 takes 11 steps, and will take 5-15 minutes when using declarative heuristics.

   • Goal state 31 for initial state 3 takes 10 steps and will take 2-10 minutes with declarative heuristics.

It is a good idea to start by convincing yourself these are the actual plan lengths (at least for the easy problems), before starting to write your axioms. This will help ensure you fully understand the tasks given.

You should now complete the following tasks:

1. [15 marks] Write precondition axioms for all actions in your domain in the precondition_axioms_dishwashing section of dishwashing.pl. See the description of part (a) of Question 1 for useful suggestions when defining your preconditions.

2. [20 marks] Write successor-state axioms in section successor_state_axioms_dishwashing of dishwashing.pl. See the description of part (b) of Question 1 for useful suggestions when defining your successor-state axioms.

3. [15 marks] You will now write declarative heuristics for the planner to use when solving this problem in “heuristic” mode. You should write at least 10 rules.

   When creating your heuristics, you can assume that the initial and goal states they will be used on will be “reasonable”. That is, they should allow your planner to handle problems that involve getting all (or some subset) of a given set of dishes cleaned and into the dish rack. The initial states and goal states will never include states that would not be helpful to achieving this objective. For example, you can assume that the dishes on the counter always start dirty, you will never need to put dirty or soapy dishes in the dish rack, clean and wet dishes should always end up in the dish rack, and soapy and wet dishes should never be put on the counter. However, your declarative heuristics should never result in the planner finding suboptimal solutions.

   You may wish to consider heuristics of different types such as those discussed in part (c) of Question

   1. There are also other possible types of heuristics. Try to be creative about what you can do with the useless predicate. However, you are also not obligated to cover all different kinds of heuristics, just that you include at least 10 rules. It is also worth testing them individually (by removing and adding them), to see if they are actually helping at all. Please see part (c) of Question 1 for further tips on generating declarative heuristics.

   Remember to put a comment beside each declarative heuristic indicating what it is doing.

4. [5 marks] Document the results of testing your planner (ie. calling solve_problem) on this problem and put them in the file dishwashing_tests.txt. Please see part (d) of Question 1 for full details on the expected documentation.

You tests should be performed on at least goals 11, 12, 13, 14, and 21. You may wish to include tests on other goals as well, but this is not required.