ROBOT MOTION PLANNING
"Efficiency Analysis and Software Implementation "

David Urrabazo Jr, Arie Litosky, Yuh-Jen (Mindy) Feng
Advising Professor: Sergey Bereg
Erik Johnson School of Engineering and Computer Science
University of Texas at Dallas, USA

Supported by a grant from the
Computer Research Association
Committee on the Status of Women in Computing Research
and the
National Science Foundation

Project Description

    Robotic motion planning is vital to the completion of any robot's task. Motion planning refers to the construction of inputs to a non-linear dynamical system that drives it from an initial state to a specified goal. we will study known algorithms, such as the left hand rule, angle constraint approach, and vertical decomposition. We will test the efficiency and productivity of these algorithms and take it a step further by composing a software implementation for the two most efficient algorithms. In this implementation we will create a user interface that allows variation of parameters such as view changes, algorithm and maze selection. Animation of algorithm's strategy will aid in analysis of algorithms roots as well as provide a generic test bench for any motion planning situation of inquiry.

Questions Addressed
   
1.     What algorithms are the most time efficient?
2.     What are the restrictions of these algorithms?
3   How can we get the robot to have a sense of space (proprioception)?
4   How can we get the robot to find a specific target in the maze?
5.     How can we get the robot to determine what type of shape and structure it is walking around?

Methodology and Approach

Click on the image below to see the UTD applet.

    BackgroundResearch
. a) Cell Decomposition
. b) Shortest Path Algorithm
. c) Visual Graphing Algorithms
. d) Canny's RoadMap Algorithm
Methods
  a) Random Sampling
  b) Software Implementation
  c) Coding Debugging
. d) Web Page Design
     
 

Project Progress/Notes

    Week 1__08/24/2007
    Week 2__08/31/2007
    Week 3__09/07/2007
    Week 4__09/14/2007
    Week 5__09/21/2007
    Week 6__09/28/2007
    Week 7__10/05/2007
    Week 8__10/12/2007
    Week 9__10/19/2007
    Week 10_10/29/2007
    Week 11_11/02/2007
Week 12_11/09/2007
Week 13_11/16/2007
Week 14_11/20/2007
Week 15_01/11/2008
Week 16_01/18/2008
Week 17_01/25/2008
Week 18_02/01/2008
Week 19_02/08/2008
Week 20_02/15/2008
Week 21_02/22/2008
Week 22_02/29/2008
Week 23_03/07/2008
Week 24_03/14/2008
Week 25_03/21/2008
Week 26_03/28/2008
Week 27_04/04/2008
Week 28_04/11/2008
Week 29_04/18/2008
Week 30_04/25/2008
 
A detailed report on the developed methods can be downloaded here.