Algorithm Design and Analysis
Assignment Two
The purpose of this assignment is to develop an intelligent system for moving
a vehicle through variable terrain.
The terrain consists of a rectangular region
broken up into quadrants, where each
quadrant is assigned a difficulty factor between
−5 and 15. A vehicle can start
anywhere along the bottom of the terrain
and must move one quadrant at a time
either directly forward, or diagonally forward
(one quadrant forward to the left or
right unless the vehicle is on one of the two
edges of the terrain). Some sample terrains
are available on the raptor2 database
server in a database called terrains. The
goal is to move through the terrain so as to
minimize the total difficulty for a vehicle.
The system should include the following components:
User Interface which should allow any of the terrains on the database to be
obtained and present some graphical representation of the chosen terrain.
Parts of the user interface should utilize the Observer design pattern, so
that they are notified by a vehicle whenever the vehicle moves in the
terrain. (15 marks)
Manual Control which allows the user to manually move a vehicle through
the terrain, displaying a tally of the difficulty as the vehicle is moved.
5 marks)
Automated Control which should move an automated vehicle intelligently
through the terrain, and present the path in a suitable manner.(10 marks)
Intelligence Algorithm which should use some level of intelligence (selectable
between 0% and 100% by the user) to efficiently choose the most appropriate
path through the terrain. For example, with an intelligence of 100%
a vehicle would be able to choose its path based on the entire terrain, so
it might start in the third (or fourth) quadrant along, and progressively
move forward-left, forward, forward-left, forward for a total difficulty of
10. Instead, with an intelligence of 40% a vehicle would only be able to
choose its path based on the two rows (40% of the maze) that are currently
ahead of it. (15 marks)
Justification which should be a text document that justifies why your algorithm
chosen for the automated control does give a path with minimum
difficulty when the intelligence is set to 100%, its order, along with some
reasoning for how it works for lower levels of intelligence. (5 marks)