16311 Introduction to Robotics 

Main Schedule Homework Labs Links 
Lab 5: Path Planning 

Challenge StatementUsing a known map, determine the best path from given start and finish points. Lab Goals
BackgroundPrinciplesYou may have to combat the following while developing your machines:
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 waypointbased (right) representations of the configuration space. 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 graphbased searches in the next week. A few algorithms that may be helpful for this lab are Dijkstra's Algorithm and A*. These two methods may require more computational power than your NXTs can handle, so we recommend performing those algorithms in a program like MATLAB, and then entering the path into your ROBOTC program. Don't forget that for a waypointbased 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 waypointbased (right) paths through basic environment. Just as in Lab 3, you will need to know where you are using only the information from the encoders (and any other sensors if you choose to use them). You will not be able to achieve the required precision without careful dead reckoning. 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. Lab RequirementsThe specifications for Lab 5 are presented in the following document. This will be the most uptodate resource for lab requirements. Extensions 

