CSCE 452/752: Homework 12 Solutions

A certain robot lives in the two-dimensional configuration space $\mathcal{C} = [0,10] \times [0, 10]$ shown below. The robot wants to move from the configuration marked in blue near the top center, to the configuration marked in blue near the bottom right. Obstacles are shown in green. The grid is shown for your reference.

Use your favorite pseudo-random number generator to create a sequence of 20 random configurations. List them below.

Solution:
One possible answer:

( 9.66, 4.41)
( 0.07, 9.11)
( 9.39, 5.82)
( 6.72, 0.84)
( 7.66, 2.37)
( 0.31, 7.89)
( 3.46, 6.23)
( 6.16, 1.49)
( 1.83, 1.14)
( 0.15, 4.87)
( 9.65, 0.65)
( 5.41, 4.66)
( 6.01, 0.89)
( 5.79, 2.70)
( 5.56, 6.45)
( 4.81, 3.55)
( 2.49, 9.34)
( 4.53, 5.30)
( 0.19, 5.08)
( 0.06, 1.44)

Generated using
Python's
random.random
function
.
Show the operation of the PRM algorithm with these samples, using 2 for the connection distance. What calls are made to the collision checker? What edges are included in the graph?

Solution:
Answers will depend on the specific random samples you used. In general, you should get one point collision check for each of the samples, and one segment collision check for each pair of samples that are closer than 2 units from each other.
Did the algorithm solve the motion planning problem? If not, why not?

Solution:
It's very likely that the answer will be No. To get a solution, you would almost certainly need to increase the number of samples. Increasing the connection distance may help as well.