Mapping a Physical Environment

Tom J Hancocks


Supervised by Frank C Langbein; Moderated by Dave Marshall

Project Aims & Objectives

Research and find ways of exploring a physical environment whilst building up a digital mapping of the environment - this will involve the use of a robot built with either an Arduino Kit or Lego Mindstorms.

Using the mapping built, determine the shortest path between two points - one point being the robots current location. Research different shortest path algorithms to find the most effective for the task. What kind of trade offs and compromises need to be made? Completion Time vs Accuracy.

Find ways of easily communicating between the computer and the robot.

Test the robot in an increasingly complex set of environments to ensure a accurately and well functioning set of algorithms.

Collision detection to stop the robot should the algorithms either fail or the robot is moving in unfamiliar environments.

Brief summary of the project

In this project I intend to determine what type of path finding algorithms are best suited to finding paths within a digitally constructed map of a physical environment. The algorithms will have to tested in a number of environments, to see how each one copes with different challenges and layouts.

The mapping of the physical environments will have to be built up using a series of sensors. These sensors will be attached to a small robot which the software upon a desktop or laptop computer can then control.

Data collected by the robot will be sent back to the computer, and instructions will be sent to the robot from the computer.

As the project progresses I will introduce the robot to increasingly complex environments. With each level of complexity debugging and testing of the algorithms can be done to ensure stability and accuracy.

Resource Requirement

Lego Mind-storms or Arduino Board - Access to both already.

Sensors and motors (if Arduino is used then IR Sensors, a motor and RGB sensor will be needed)

Bluetooth on both the computer and robot. (My laptop has bluetooth as does the Lego Mindstorms brick. Arduino would need a separate bluetooth chip.)

Java, C, Objective-C Programming Languages. Lego Mindstorms can be programmed in Java after flashing lejos_nxt on to it. Software on my computer will be programmed in either Java or Objective-C/C. Arduino is programmed using an extremely C like language.

Initial Plan (12/10/2011) [Zip Archive]

Interim Report (16/12/2011) [Zip Archive]

Final Report (04/05/2012) [Zip Archive]

Publication Form