Project 4: Implementing driver algorithms that make the robot escape from the maze

To Deliver: release 6.0 in svn repository (tags/release6.0), email with crc card design to your grader: Md Atiqur Rahman <mrahman@email.wm.edu> (Section 1), Jianhua Sun <jsun01@email.wm.edu> (Section 2).

To Download: 

Due date for submission:    Oct 26

Drop out date:                     Oct 29, at 5 AM (EARLY MORNING)

Motivation

There are many different ways to escape from a maze.  In this project, we want to implement such algorithms for the robot whose functionality is specified by a given Robot.java interface which you implemented in Project 3.

The interface follows what a Lego robot may provide for as sensors to recognize distant objects (here walls) and the ability to move forward, backward and to turn on the spot. 

We also want to compare algorithms in terms of their energy efficiency to operate the robot. So there is a some energy consumption being involved in any movement and sensor operation and the robot draws energy from its battery on its journey. 

Operating the robot needs care, hitting a wall will damage it and will cause an emergency stop. 

We want to consider four different Robot driver algorithms:

• Gambler: the gambler is a simple random search algorithm with no memory. Once started it looks moves a step, checks its options by asking its available distance sensors, randomly picks a direction, moves a stop and so on. 
• CuriousGambler: the curious gambler has a bias to select an adjacent cell that was not visited as often as other (curious to explore new territories). So it needs a memory to count how often it has visited particular cells. Hint: a hashmap is a great data structure for this, but there are lots of choices that all work (check for Collections). 
• WallFollower: the wall follower is a classic solution technique. The robot needs a distance sensor at the front and at one side (here: pick left) to perform. It follows the wall on its left hand side.  Warning: Think how the robot's limitations in recognizing its environment may have an impact on properties of this classic solution algorithm (termination, correctness).
• Wizard: as there is little magic in algorithms, the wizard is in fact a cheater who knows the distance matrix and uses it to find the exit. The wizard is intended to work as a baseline algorithm to see who the most efficient algorithm can perform in terms of energy consumption and path length. It is also a good candidate for testing a maze, a robot implementation …

We also need to adjust the maze application class to provide us with a user interface such that we can select a robot driver algorithm (plus one option for a manual operation). Hint: check for Combo Boxes. The RobotDriver will basically do the same thing as the manual driver implemented in Project 3 but this time in a fully automated way. 

The robot configuration we will consider at this point is the following:

• It has 2 distance sensors, one in forward and one in left direction. 
• The robot can move forward and backwards. 
• The robot can turn.
• The initial battery level is 2500.
• The energy costs are: 
• Distance sensing in one direction: 1
• Rotating by 90 degrees (left or right): 3
• Moving forward or backward one cell: 5

What to learn from this project:

- Experience in test-driven design and limitations of testing when it comes to randomized algorithms and graphics. 

- Using inheritance to share code across classes that solve same problems in different ways

- Implementing different versions of algorithms in an object oriented manner

- Learn to work with exceptions

Design decision

To retain a reasonably uniform design, I would like to fix the following naming conventions for classes:

Classes that implement the RobotDriver interface for the different algorithms are named: Gambler.java, CuriousGambler.java, WallFollower.java, Wizard.java.

Provide each class with at least one constructor that has no parameters and operates a robot with the default configuration we consider.

Classes that implement test cases for each class have the class name followed by suffix Test, e.g. GamblerTest.java for the Gambler.java class.

To do list:

• Perform a class design with CRC cards. 
• Note: there are several reasonable designs! Aside: for the RobotDriver consider the use of an abstract driver following the Template Pattern.  
• Put your crc design in writing, simple list each class, its responsibilities and collaborators. Email this to the grader.
• Implement the Robot Driver algorithms. 
• You can use as many additional other classes, methods as you like. 
• For testing: ask yourself what a correct robot driver implementation distinguishes from a faulty one. 
• Update your subversion repository whenever you made progress and got a particular feature or method going. 
• When you have finished the project assignment, create a tag with a Release 6.0 before the drop out date (due date is recommended for your own sanity). Include your junit test cases in your release. Keep source code and test code in separate directories (src and test). 
• Send CRC design description by email to the grader.

Grading

• You will receive points for the CRC design description.
• You will receive points for a subversion release 6.0 that includes source code and test code and that can be checked out by the grader. 
• You will receive points for implementing the four robot driver classes. Code is expected to have comments, at least a statement per method (using the javadoc format with /** …. */ . 
• You will receive points for implementing test cases. Test cases are expected to come with a comment that specifies what is tested, what is the correct behavior and (if not obvious) why that behavior is correct.
• You will receive points if test cases perform and your code passes our own tests. We will run and evaluate your tests as well as some additional ones of our own that will test the Robot Driver classes based on the interface specification. We will evaluate your tests to see if they perform a rigid test and if they achieve a reasonable coverage on the tested classes.
• You will receive points if the overall MazeApplication runs, comes with a menu to start each of the four algorithms or a manual operation and if the algorithms in fact operate correctly on a maze that is displayed in the first person perspective as well as the map perspective with the current location and the suggest path to the exit (based on the distance matrix).