These exercises implement deductive planning rules for a simple version of the Shakey robot system, using the Simple Deductive Data Retriever.
Shakey was one of the first intelligent robots in AI. Many people worked on many aspects of the system, from computer vision to motion, but the part that is relevant here is Cordell Green's "Application of Theorem Proving to Problem Solving." That paper does the Monkey and Bananas problem, Towers of Hanoi, and robot planning like the exercises below.
A common problem in early robotic planning was moving boxes from one room to another, given information about box locations (current and desired), room locations, doors being open or closed, etc. Most of this information is represented in a state structure, as with the Monkey and Bananas example, and solved using the same planning framework.
To do these exercises:
(ql:quickload "sddr")
(in-package :sddr-tests)
Create a file for your rules. Start the file with (in-package :sddr-tests).
The test cases can be found in the file sddr-exs-tests.lisp. Each test set defines a utility function that queries your rules using the SDDR ask function. The utility function has the same name as the test set. The utility function assumes the rules are stored in a global variable with the same name as the test set.
The utility function automatically includes *plan-kb*, which
includes the rule (<- (same ?x ?x)).
Do not include these rules in your Shakey rules.
Shakey 1.0
Test set name: shakey-1
For Shakey 1.0, create a set of rules to allow the Retriever to solve simple Shakey problems. Follow the model of the Monkey and Bananas example in sddr-plan.lisp.
Define your rules in the global variable shakey-1. The test file defines a utility function (shakey-1 query) that calls (ask query (append *plan-kb* shakey-1)). You may find shakey-1 handy for debugging your rules.
Shakey only has to move one box from one room
to another, and there are no locked doors. The term for
representing a state in Shakey 1.0 is (v1-state robot-location
box-location). The v1- indicates
this is for version 1.0.
There are just two actions that change state:
(MOVE-TO location): the robot moves to a location, where a location can either be the hall or a room(PUSH-BOX location): the robot pushes a box from one location to another.
To keep things simple, ignore the subproblem of finding paths from rooms to rooms. Instead, assume that all rooms are connected to the hall, so the rules for moving and pushing boxes from one room to another are simply:
- First move or push the box from the first room to the hall
- Then move or push the box to the second room
Use the same PLAN framework used in
the
Monkey and Bananas code.
You should only need to define:
- rules for
RESULTSfor what happens to states when you move and push boxes - rules for
STEPfor choosing an action, given a current state and a goal state
The STEP rules are where you make the robot
smart enough to avoid getting into endless loops.
Shakey 2.0
Test set name: shakey-2
This is the hardest of the three Shakey exercises. When Shakey 1.0 is working, extend it to handle locked rooms. The robot should be able to unlock a room from the hallway, but not from inside the room. A robot can only enter or leave a room, when moving or pushing a box, if it's unlocked.
Define your rules in the global variable shakey-2. The test file defines a utility function (shakey-2 query) that calls (ask query (append *plan-kb* shakey-2)). You may find shakey-2 handy for debugging your rules.
The easiest way to do this is by extending the state to include a list of the unlocked rooms. Make a new version of Shakey 1.0, where:
- the rules use the state form
(v2-state robot-location box-location unlocked-room-list) - the rules for selecting
MOVE-TOandPUSH-BOXrequire the rooms involved to be unlocked - rules are added for the action
UNLOCKwhich lets a robot in the hall unlock any room, i.e., add it the list of unlocked rooms
The test cases start with easy cases, where the room the robot needs to enter, is in the unlocked list. The later cases start with an empy list of unlocked rooms.
Tip: use member to determine if a room is unlocked, i.e., in the list of unlocked rooms.
Shakey 3.0
Test set name: shakey-2
When Shakey 2.0 is working, extend it to handle multiple boxes. There is at most one box in a room, so we can represent the initial state as a list of rooms with boxes. Shakey's goal is to move all such boxes into a destination room.
This can be done with just ONE rule added to Shakey 2.0, if we assume that the plan for moving multiple boxes is to combine the plans for move each indvidual box.
Define your rules in the global variable shakey-3. That variable should contain the shakey-2 rules plus whatever you need to add. The test file defines a utility function (shakey-3 query) that calls (ask query (append *plan-kb* shakey-3)). You may find the function shakey-3 handy to call when debugging your rules.
The state representation for Shakey 3.0 is
(v3-state robot-location box-room-list goal-room unlocked-room-list)
This state specifies
- the robot's initial location
- a list of the rooms with boxes to move
- a goal room, into which boxes need to be moved
- a list of the locked rooms, as with Shakey 2.0
The robot is done when box-room-list is empty. If the list isn't empty, the robot should
- find a plan for getting the first box in the list to the goal room, using your Shakey 2.0 rules,
- find a plan for the remaining rooms
- return the combined plan.
Hint: use the deductive rules for APPEND to do some of this work for you.
Only submit the new Shakey 3.0.