Lab 5: Path Planning

Challenge Statement

Using a known map, determine the best path from given start and finish points.

Lab Goals

1. Implement a path-planning algorithm to navigate a known course.
2. Optimize your planner for accuracy of final positionand L2 distance of the path.

Background

You may have to combat the following while developing your machines:

Representing the world

For a path planning problem like this, there are two main ways to represent the world. The first is a grid. You can divide the world up into uniform shapes that you can or cannot travel to. Another method of representing the world is a series of waypoints. Instead of representing all of the available places you can travel to, this method just includes a few key locations that you can travel to.

Grid (left) and waypoint-based (right) representations of the configuration space.
Planning a path

In class we talked about several path planning algorithms. For this lab, the most likely candidates are a wavefront/potential function or a search algorithm. We discussed a potential function where we stay away from obstacles and weight the goal as the lowest number and each adjacent element as sucessively increasing numbers. We will go into graph-based searches in the next week. A few algorithms that may be helpful for this lab are Dijkstra's Algorithm and A*. Don't forget that for a waypoint-based algorithm, you will not only need to traverse between waypoints (and some waypoints should not be "visible" to each other if that would mean going through an obstacle) but you will also need to travel from the starting point to the ending point. You should strategically play your waypoints such that any possible start and end can traverse to at least one waypoint without hitting an obstacle.

Grid (left) and waypoint-based (right) paths through basic environment.
Executing the path

Just as in Lab 3, you will need to know where you are using only the information from the encoders. Feel free to use your code from Lab 3 but keep in mind that changing your robot dimensions will change some of the constants in this algorithm.

For groups who are interested, added functionality of the MotorGo boards includes an IMU sensor, which you used for Lab 4 and you are permitted to use for Lab 5 as well. You will not be able to achieve the required precision without careful dead reckoning, either from very well-calibrated pure odometry or sensor fusion between your gyroscopes and wheel odometry. If you use the IMU, be wary of sensor drift.

Lab Requirements

The specifications for Lab 5 are presented in the following document. This will be the most up-to-date resource for lab requirements.

Lab 5 Writeup

Lab 5 Resources Folder

Additional Information

Computerphile video on Dijkstra's Algorithm

Computerphile video on Dijkstra's Algorithm