Baochen Sun
May 3, 2012

Adaptive Waypoint Planning


The goal of waypoint planning, more generally, multi-goal path planning, is to find the shortest Hamiltonian path through all the way points(goals). Adaptive waypoint planning allows user to add human knowledge as a prior as well as adjusting the path at run time.


Concepts Demonstrated

  • Path planning is used to find a path between two points.
  • Euclidian distance is used as a heuristic.


  • Adaptive technique is used to adjust the order of visiting all the points while the robot is moving. For example, while the robot heading towards point A, it could move away from A and get close to point B. Then it could change its current goal to B.
  • Integrating human knowledge as a prior is used to add (partial or full) human preferences. For example, the preference vector [1 2 2 2 3 3 3 4] means we want the robot to visit point 1 first and then points 2 - 4 followed by points 5 7 and visit point 8 in the end. However, there is no preference among points 2-4 or 5-7. The preference vector [1 1 1 1 1 1 1 1] means there is no preference and [1 2 3 4 5 6 7 8] means full preference(fixed order).

Technology Used Block Diagram

Additional Remarks

  • There is a bug in the GPS reading: when the robot stops, the latitude will always go up.
  • The path planning algorithm between two points is not working right now. The reasons are: the GPS reading are not accurate enough; in order to do that I have to implement SLAM(simultaneous localization and mapping), which could be another final project; that part is a classic problem and has been proved to be working well, I could just assume it works and use keyboard and mouse instead to test my framework; the real innovation of my project is the adaptive techniques and integrating human knowledge as a prior; the last problem of the final exam of the online Udacity course(Programming a Robotic Car) is path planning and I got 100% correct on the whole final exam(thus, I got the CERTIFICATE OF ACCOMPLISHMENT WITH HIGHEST DISTINCTION).
  • Certificate from Udacity