|
CS 3243 - Foundations of Artificial Intelligence
NUS SoC, 2005/2006, Semester II |
|
|
CS 3243 - Foundations of Artificial Intelligence
NUS SoC, 2005/2006, Semester II |
[ IVLE ]
[ Overview ]
[ Syllabus ]
[ Grading ]
[ Homework ]
[ HW 1 ]
[ >HW 2T ]
[ HW 2I ]
[ Misc. ]
Please see the demo sign up sheet to sign up for a demo slot on 17 Apr
2006 (Monday of Reading Week).
Here are some pictures and a video from one
of the teams who did this assignment. Enjoy.
In this homework assignment, you will work (together or individually) to create a robotic agent that will solve a Sokoban problem on a known map. Sokoban (or 'warehouse man' in Japanese) is a type of puzzle problem. As input, you will be given a map of the space your robot will travel in. The maps you will be working in are 7' x 5'. The maps will show up to three boxes (which will be physically implemented as white, lightweight boxes 6" x 6" x 6" across) that need to be moved a set of destination squares. Any block can go to any destination square. Your agent has the capability to push but not pull a box. Also, your agent is not strong enough to push two boxes in a row or column together. Agents must move in 1' increments and 90 degree turns.
You should program your agent to solve the Sokoban problem, then execute the moves that it needs to do in order to finish the problem.
The following two 7x5 maps will make up two of the four test cases for the demo of your robot. All '+' indicate walls. An 'X' indicates a block position, an 'O' a destination for a block. In the input, a three by three character box makes up a 1'x1' square (the center is the 1'x1' and the other eight are the corners and edges surrounding the space). The final two test cases will be given to you at demo time. Your agent will always start in the upper left corner facing down (e.g., in both maps, in position 'a' facing 'b'). You'll have five minutes to add these map and goal state to your agent's software.
| Map 1 | Map 2 |
|---|---|
+++++++++++++++ +a X X O O+ +b +++++ + +++++ + +++++ +X +++++ + +++++++++++++ +O+++++++++++++ +++++++++++++++ +++++++++++++++ +++++++++++++++ |
+++++++++++++++ +a +++ + +b +++ + + X + +++ +++++ +++ +++ +++ + +++ +++ + +++ X+++ X + +++ +++ + + +++O O O+ +++++++++++++++ |
Note that boxes will be 6"x6"x6" (as above) and colored white. Walls of the area will be brown cardboard and at least 8" high. Boxes will be centered in the 1'x1' square that it is located in. Boxes and destinations will only be located in the 1'x1' squares, they will never be located on an edge (e.g., never on a space like the 'b' in the above examples). Also, your agent will not be given a problem that has no solution.
To do this assignment, you will be provided with a Mindstorms kit. You will need to build some type of mobile agent. You will first check out kit a Mindstorms kit from the Graphics Laboratory (from Mr. Chong Peng Kong) and build a robot that will implement (at least) a forward motion of 1 foot and turning motions of 90 degrees. I suggest that you build the driver base as instructed in the instruction booklet and refine it so that in can traverse distances of 1 foot and turn 90 degrees as accurately as possible. The driver base will need to be equipped with at least one touch sensor in order to detect when a wall has been encountered. You will find that as the robots move, they accumulate error in their position; you may want to think about how to handle this.
You may code this assignment in any programming language you want but we advise that you use Lejos (see links at the bottom) as we have had success with this programming language in the past. Although you will need to submit your code and README for the assignment (as per the following instructions), the grading will mostly be done by demonstration. In the week following the homework due date, I will set up 20 minute appointments for you to demo your robot agents. At least one of your team members must be present for the demo.
Your code will need to be submitted with a README.txt file in plain text. The code and README (as per homework #1) should not contain your names, but just your matric number(s). You should submit it as a single zip (not RAR, GZ or BZ) file (without an included directory, as per homework #1) named submission-XXXXXX-YYYYYY.zip, where XXXXXX and YYYYYY are your matric number(s) in CAPS. Upload the resulting zip file to the IVLE workbin by the due date: 6 Apr 05, 11:59:59 pm SGT. There absolutely will be no extensions to the deadline of this assignment. Read the late policy if you're not sure about grade penalties for lateness.
As you will find out, the above description is a nice abstraction of how robotic kits actually work in the real world. Sensor and actuators rarely work to move exactly one foot or turn 90 degrees. Memory on the RCX control module is limited to 32K (yes, you read correctly, that's kilobytes). There are interesting ways around each of these problems; I leave it up to you to figure out how. So it's up to your team to design the physical aspects of robot and the software that coordinate that minimize this error as much as possible. Battery life causes robots to move less far, tires grip differently on different surfaces, etc. These aspects of robotics are best anticipated and dealt with as soon as possible. IR communication between your IR tower and the RCX is difficult in bright light (you may have to make a shield to get the transmission working. If you have any questions, please ask me ahead of the deadline. If you are planning on doing this assignment, plan on having access to a laptop that you have administrative rights to, it will make your work much easier to handle. If you don't have this equipment and are still interested in this assignment, you should approach me. If you need spare parts from other RCX kits, you are welcomed to loan extra parts from the spare RCX kits that we have; approach Mr. Chong for this.
Rather than play the game, think about how it can be turned into a search problem. A solution needs to use some version of graph search, as opposed to tree search (why?).
There are plenty of sokoban games on the net. You can play these to get an idea of the game if you have not played it before.
Min-Yen Kan <kanmy@comp.nus.edu.sg> Mon Mar 7 15:29:26 2005 | Version: 1.0 | Last modified: Mon Jul 31 16:44:01 2006