These three exercises implement a simple version of the Shakey robot system, using the 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 relevant here is Cordell Green's application of logic programming to the planning problem, details of which can be found in "Application of Theorem Proving to Problem Solving." That paper does the Monkey and Bananas problem, Towers of Hanoi, and robot planning.
These exercises require the following files from the C25 library:
- ddr.lisp -- the code for the Deductive Data Retriever
- shakey-tests.lisp -- the test cases for these exercises
shakey-tests.lisp defines all the tests in the package named shakey-tests. The easiest way to work on these exercises is to write all your code in the shakey-tests package, that is, create a file and start the file with (in-package #:shakey-tests).
Feel free to create new test cases!.
Global variable name:
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. Several kinds of information need to be represented:
- Unchanging facts, such as how rooms are connected: these can be represented as static facts in the knowledge base
- Facts the robot can change, such as where it is: these can be represented in a state structure, as with Monkey and Bananas
- The problem to be solved: this can be represented by describing an initial state and a desired goal state
For Shakey 1.0, create a set of facts and rules to allow the Retriever to solve simple Shakey problems. Follow the model of the Monkey and Bananas example in monkey-general.lisp. This is similar to the version in ddr-tests, but using a more general set of rules. The rules are described in comments at the start of monkey-general.lisp.
Assume that Shakey only has to move 1 box from 1 room
to another, and there are no locked doors. The term for
representing a state is simply
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 location1 location2): 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-FOR framework used in the
Monkey and Bananas code in ddr-tests.lisp.
You should only need to define:
- rules for
RESULTfor what happens to states when you move and push boxes
- rules for
ACTION-FORfor choosing an action, given a current state and a goal state
ACTION-FOR rules are where you make the robot
smart enough to avoid getting into endless loops.
Tip: use all-different to quickly say that room1, room2 and room3 are all different.
Global variable name:
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.
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
PUSH-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.
Global variable name:
When Shakey 2.0 is working, extend it to handle multiple boxes. We will assume that there's at most one box in a room, so all we need to do is give a list of the rooms that have a box in them. Shakey's goal is to move all such boxes into a destination room.
There's not a lot of additional rules needed to do this. Most of the work will still be done by the Shakey 2.0 rules. The trick is to create a new state that contains:
- the robot's initial location
- a list of the rooms with boxes to move,
- a goal room, into which boxes need to be moved, and
- a list of the locked rooms, as with Shakey 2.0
Capture this with the state form
(v3-state robot-location box-room-list goal-room unlocked-room-list)
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.
To combine plans, use the deductive rules for
shown in ddr-tests.lisp.
Only submit the additional rules.
A Universal Planner
Implement simple universal planning rules. Test that they can solve the test cases for Blocks World Stacking and the Monkey and Bananas.
Hint: Don't reinvent
that exercise first and use those rules.