Homework 1
Due Thursday, 1 February 2007
-
Discuss how motion planning differs from collision avoidance.
-
Under what assumptions is it reasonable to assume that a wheeled
robot is a two-dimensional object moving freely in a plane?
-
Give two examples of a non-holonomic robot and explain why they are
non-holonomic. Why do we use non-holonomic vehicles?
-
You have a robot that can move at a maximum velocity of 1m/s, with
the ability to accelerate at +/- 2m/s. You have sonar sensors that
are useful between 0.5m and 3m, and it takes you 50ms to decide upon
and implement an action. How often do you have to sample the sonars
to ensure that you are not going to run into a stationary
obstacle?
-
Using the same robot as above, how often do you have to sample the
sonars and make decisions to ensure that you do not run into an
obstacle going 1m/s towards the your robot? What, therefore, is the
maximum number of computer operations you can execute in a single
sense-act cycle on a 500MHz computer, assuming 1 operation per clock
cycle. This is an estimate of how complex a program you can run
while navigating in real time. Divide this number by 86,400 to get
an upper bound on the number of image processing operations you can
use on half-size video. If N is the number of pixels (86,400) Is it
possible to use any image processing operations that are more
complex than O(N)?
Homework 2
Due Thursday, 15 February 2007
Download the kalman1d.c and
gaussDist.c source files. Then you need to
fill in the Kalman filter update equations in the middle of the main
loop. You will also need to initialize the H, Q, and phi variables,
as appropriate. Use a scalar state variable to begin with, storing
and updating only position. Any change to to a non-zero velocity will
need to be modeled as process noise (Q).
-
Try out different combinations of sensor noise and estimated
sensor noise (R, in the Kalman filter equations). Plot the output,
which is spewed to the data file, and look at the different responses
for different values of Q and R. Learn gnuplot.
-
Make the system use a 2-element state vector (position and velocity),
but still only a single measurement vector. The Kalman gain equation
should still be a scalar equation, but the state update matrix will be
2x2, as will the system covariance matrix P. Compare the results for
different levels of noise.
Hand in a copy of your code as well as a few plots of the sensor
readings and the Kalman state values. Summarize your observations
about what happens for different values of Q and R. Also observe
how the various Kalman filter parameters affect the behavior of the
proportional control system.
Homework 3
Due Tuesday, 27 February 2007
Do this exercise with a partner in the Kohlberg or Science Center
coffee bar areas.
-
Pick a starting location on one side of the room, and a goal point
on the far side of the room. Navigate your way to the goal point
as quickly as you can while still walking while your partner notes
the strategy you use to move around obstacles. In particular, note
how far away from obstacles you pass, and how and when you change
direction. Switch and have your partner repeat the exercise. Try
not to consciously manage your movements.
-
Repeat the exercise, but this time try to stay equidistant from
obstacles. In other words, try to keep the distance to obstacles
on either side of you the same. Comment on whether it felt natural
to follow this strategy and how it affected your speed.
-
Finally, close your eyes and have your partner adjust the
obstacles (probably chairs) such that there are dead ends and
blocked paths between you and your goal point. Then put something
over your eyes, or shade them so that you can see at most a meter
or so ahead of you. Try to get to your goal point as fast as
possible without going over or through any obstacles. Have your
partner note your strategy. Then switch roles.
-
Based on your exercises, comment on strategies for navigation and
planning in complex environments. What was natural, what worked,
and what didn't?
Homework 4
Due Thursday, 5 April 2007
-
Code up Dijkstra's algorithm and test it on the simple visibility
graph below. A simple way to represent the visibility graph is to
use an array to represent the vertices, and a 2D matrix to represent
whether a connection exists between any two vertices. You can use
this file to get started. It defines
some basic data types as well as the graph itself. Run your
algorithm for both the goal point specified below and for the goal
point (18, 7). Report the complete path in both cases along with the
cost (distance traveled) from the start point to each intermediate
point and to the final goal.
