<-- Back

Project I FAQ


Phase1: I'm Lost!
Permitted Algorithms
Acceptable Performance
Controller


I don't know how to get started on Phase 1. Help me!

This is mostly for the students who are new to programming. I thought I would say a couple of things about it.

  • I suggest you write:
    • parse_environment(environment_text_file): a function that reads the text file and outputs the values
    • create_map(environment): a function that takes the environment values that you parsed and generates a map in the form of a 2D matrix
    • display_map(map): a function that takes in a map and displays - freespace, start,goal and obstacles in different colors and what not. For now, a mere wrapper around matlab's imagesc() function will suffice. Later on, you might want the function to take a path as an additional input so that a path can be displayed as well.
  • I guarantee the environment file we test your code with will contain the items (boundary, start,goal,obstacles...) in the same exact order as what is stated in the project description.
  • I suggest that you create a couple of test environments for yourselves with different number of obstacles to make sure your parsing code works.


Are we restricted to using A*? Can we use a sampling based planner instead?

I incorrectly told some of you that you were not restricted to A* for the project. I was wrong. You can use any planning algorithm that is a variant of A*, with A* being the bare minimum algorithm that you implement. I'm very sorry about the confusion. We will be more clear in the future. We will be covering sampling based approaches in the future.

What is 'acceptable performance' for path planning?

As you have read in the project description, one aspect of grading of project 1 will be on the time it takes for your planner to plan a path to the goal. Given that this project is the first time many of you have ever written a planner, I would guess you might be wondering what is considered an acceptable amount of time to allow for path planning for navigation.

The time required to plan is largely dependent on how you represent the environment. For example, if using an A*-type search, the more states (grid cells) you use to represent your environment, the longer the search may take to find a solution. Think hard about how you want to represent your environment such that the robot is able to traverse from any start point to any destination.

When discretizing an environment, the most important choice we make as path planning researchers, is the resolution of the map we'll use. To make an educated decision we have to ask the following questions.

  • What is the smallest sized obstacle that we want to take into for while planning? (i.e. what is the smallest size cylinder you may include in a map when testing our planners?)
    minimum cylinder diameter: 5cm
  • What is the width of the most narrow passageway we can expect in an environment description?
    minimum width passageway: 60cm
  • What is the maximum environment size we should be able to handle?
    maximum environment size: 50m x 50m
  • Finally, What do the graders consider acceptable planning times?
    t < 0.5 sec : very good
    t < 1.5 sec : good
    t < 2 sec : marginally acceptable

Shall we use X=[x,y,theta] to represent the robot state, and we can get the values from odometry position and orientation? We then have position error, velocity error and finally use equation (31) in the slides to compute u, am I right?

Yes.

For a smooth trajectory that passes through a given list of points, how to get the partial derivative matrix [f(y1),f(y2)]? Because we need it in equation (31). May I use such method: assume the list of points is[x1,y1;x2,y2;......xn,yn], for every two points, I view it as a line, for example:(x1,y1) and (x2,y2) forms a line ax+by+c=0, then the p! artial derivative in equation (31) is [a b]? If this is not good, perhaps we can find another approach instead of the slides you give us?

You can fit a line or any other smooth trajectory through the points. For a line, you can compute the error exactly and you can do better than using the approximation

e1(x, y) = gamma(x, y)

But yes, if you use a straight line and the approximation above, then the partial derivatives are as you suggest.