Homework 2 Introduction to Robotics

1. You want to find a driving route that minimizes the number of turns
between two locations in Boulder.
(a) Would you rather employ a sampling-based or a discrete algorithm such as Dijkstra or A* for doing this and why?
(b) Provide a possible cost function that encodes both path length l
and the number of turns t.
2. Assuming points are sampled uniformly at random in a randomized
planning algorithm. Calculate the limiting behaviour of the following
ratio (number of points in tree)/(number of points sampled) as the
number of points sampled goes to infinity. Assume the total area
Atotal (including free space and obstacles) and the area of free space
Afree (not including obstacles) within are known.
3. Assuming a k-d-tree is used as a nearest-neighbour data structure
to store a RRT data structure, and points are sampled uniformly at
random, calculate the run-time of inserting a point into a tree of size
N. Use “big-Oh” notation, e.g. O(N).
4. Why does the bandwidth of a Ultra-sound based distance sensor decreases significantly when increasing its dynamic range, but that of a
laser range scanner does not for typical operation?
5. You are designing an autonomous electric car to transport goods on
campus. As you are worried about cost, you are thinking about
whether to use a laser scanner or an ultra-sound sensor for detecting obstacles. As you drive rather slow, you are required to sense up
to 15 meters. The laser scanner you are considering can sense up to
this range and has a bandwidth of 10Hz.
1
(a) Calculate the time it takes until you hear back from the US sensor
when detecting an obstacle 15m away. Assume that the robot is
not moving at this point. Use c = 300m/s for the speed of sound.
(b) Calculate the time it takes until you hear back from the laser
scanner. Hint: you don’t need the speed of light to answer this
question.
6. A Global Positioning System sensor provides position estimates within
a circle of approximately 3m diameter. Every now and then the satellites on the horizon change and the center of this circle moves elsewhere, approximately staying within a 30 meter radius of the true
location of the receiver.
(a) Given the error data above, which value corresponds to accuracy
and which to precision?
(b) The sensor provides 18000 readings per hour. What is its bandwidth?
2