16-311 Introduction to Robotics
         Main         Schedule         Homework         Labs         Links

  16-311 Lab 5: Path Planning

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

Principles

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.
    grid waypoint
    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*. 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 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.
    gridPath waypointPath
    Execuring the path

    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 Requirements

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

Lab 5 Presentation

Lab 5 Grading Sheet

Lab 5 Demonstration Sign Up Sheet

Extensions

Last updated 01/08/2017 by Hannah Lyness
(c) 1999-2017: Howie Choset, Carnegie Mellon