Comp150-07: Intelligent Robotics
Homework 5: Configuration space
Due Tuesday, February 24th, in class
This homework is 100% individual. You are welcome to discuss ideas and
solutions with others, but you have to write up (and draw) everything
on your own to hand in.
Consider the following rhombic robot in a closed workspace with
polygonal obstacles. The robot's starting point is in the upper-left
corner.
Print or copy the image several times in order to hand in one image
per question.
- Draw the configuration space
- Draw the visibility graph in c-space
- Choose a heuristic function, and draw a path planned using A*
using your heuristic on the visibility
graph. Separately, draw the search tree constructed by A*. Is your
heuristic admissible? Is it consistent? Justify your answers. Is the
path found optimal?
- Which is better: behavior-based or planning-based navigation
architecture? What is either better for? Justify your answer.
Make your answers concise, but make sure to answer the
questions. Please hand in all your answers as one document.
Tips and things to think about
Configuration space is an abstraction of the robot workspace for
planning purposes. It is
the result of reducing the robot's footprint
and degrees of freedom to a point and correspondingly augmenting the
obstacles in the world. Read these notes on
c-space for a better understanding of c-space.
A* is an informed search algorithm on any graph that is guaranteed
to find the optimal path from start to goal if the heuristic
function used is both admissible (optimistic, never greater
than the actual distance) and consistent (obeys the triangle
inequality). For a better understanding of the algorithm, read the
A*
wikipedia article, the first 20 slides or so of the lecture on informed search from Comp131 last Fall, or these notes from Trinity
College.
Extra credit
We have not covered this in class. You can research the following
question on your own for extra credit:
- Draw as good an approximation as you can to the Generalized
Voronoi Diagram for the same c-space; plan a path through the GVD
and draw the result
- What is the difference between a plan and a policy? When should
you use either one?
The Voronoi diagram or tesselation is a decomposition of a metric
space into convex regions according to a set of generating points, such that
every point in a region is closer to that region's generating point
(called the Voronoi centroid of that region) than any other
generating points. Details, for example on Wolfram
MathWorld.
Generalized Voronoi Diagrams (GVD) are used in c-space motion
planning, as a kind of abstract decomposition from continuous c-space
to a graph representation. In GVD convex regions are generated not
from points, but
from c-space obstacles. So, all points inside a GVD region are closer
to its generating obstacle than to any others. And so, the
demarkation line between two GVD regions is made of points
equidistant from the corresponding two obstacles. The intersections
of these demarkation lines form the nodes of the graph, and the lines
its edges. The motion planner
can then use these lines as "highways", planning a path from start to
the closest point on the "highway system", a path from goal to the
closest point, then a path along the "highways" between these two
points. The advantage is that the robot will mostly be as far away
from obstacles as possible when moving. For more on GVD and other
decomposition and planning techniques, look for example at Chapter 5:
Roadmaps of
Choset et al. Principles of Robot Motion, 2005.
Paulina Varshavskaya, paulina [at] cs.tufts.edu