Motion Planning : Final Project

Due : Dec/10/2007

Hyun Soo Park, Iacopo Gentilini

Goal

Find path from start position to goal position using D* algorithm and update its position using sonar sensor and vision.

Environment

Robot : Nomad scout robot (equiped with 16 sonar sensors, camera and differential wheel)

Workspace : NSH, A floor at CMU

Map building

Map has been built using sonar sensors and it is discretized in order to generate grid map.

(red x : sonar output)

Main Algorithm

• LOAD map
• Path planning with D*
• WHILE Mission completed || Can't find path
  • READ sonar data
  • READ current position(encorder output)
  • IF (current position == way point)
    • UPDATE map using sonar data
    • IF (Good region)
      • Image Processing
      • UPDATE current position
    • ELSE
      • Kalman filtering using sonar data
    • ENDIF
    • D*
  • ENDIF
  • MOVE to way point
  • IF (current position == goal position)
    • Mission completed = true
  • ENDIF
• ENDWHILE

Project Detail

1. D* algorithm

Map of workspace is updated every moment when robot reaches to the way point. When robot reaches to the way point, it senses obstacles. If the obstacle is not in before map, then it addes new obstacles. Since map is updated, the cost of each neighbor is changed so it has to generate new path. This is D* algorithm and it is called whenever cost is changed.

2. Kalman filtering using sonar sensor

Since our map is primarily composed of long corridor, we decided to use Kalman filter in order to calibrate its right/left position. Since encorder output is quite reliable, Kalman filter is useful when the orientation of robot is not accurate.

3. Image Processing

This algorithm also generates whenever it reaches to way point. The FindLANdamrk (FLAN) recognizes the presence of landmarks (pink boxes) within the images captured by the on-board camera. Then, if the robot lies within a region defined by three landmarks, the algorithm computates the robot global position and orientation just using as input the global coordinates of the three closest landmarks and the three angles measured in the image between robot and landmarks. If the robot does not lie within the triangle defined by the three pik boxes, then the position error could be very high. However, if it lies in the “good region” the error of the algorithm is about three inches.

Demo

VIDEO

Result

Presentation Slides

Paper presentation : Numerical Potential Field Techniques for Robot Path Planning (Sept, 19, 2007)

Project Proposal (Oct, 3, 2007)

Project 1st Progress (Oct, 22, 2007)

Project 2nd Progress (Nov, 13, 2007)

Project Final (Dec, 10, 2007)

Special Thanks

Reference

[1] H. Choset, K. M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L. E. Kavraki and S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Implementations,
MIT Press, Boston, 2005.