ABSTRACT
In the first two examples, the moving obstacles cre ate narrow passages through which the robot must pass to reach the goal. Yet planning time remains much under 1 second. The fact that the planner never failed in 100 runs indicates its reliability. The configuration x time space for Example (b) is shown in Figure 8. The robot maps to a point (x ,y ,t), and the obstacles to cylinders. The velocity and accelera tion constraints force any solution trajectory to pass through a small gap between cylinders. Example (c) is much simpler. There are two stationary obstacles ob structing the middle of the workspace and three mov ing obstacles. Planning time is well below 0.01 second, with an average of 0.002 second. The number of mile stones is also small, confirming the result of Theorem 5 that in the absence of narrow passages, KDP is very efficient. As in the experiments on nonholonomic ro bot carts, the running time distribution of the planner tends to have a long and thin tail.
