Ask someone with her hands in her lap to pick up a coffee mug on the table she’s sitting at, and she’ll extract her hand from under the table and stretch her arm out toward the mug. Instruct an autonomous robot to perform the same feat, and it may think for a few seconds, zigzag its robotic hand back and forth under the table, then perform what looks like calisthenics for a few seconds more before finally reaching for the mug.

As intuitive as it seems to a human being, spontaneously planning a trajectory around obstacles in free space is a monstrously complex computation. As a consequence, most motion-planning algorithms give up on the idea of finding the most efficient path between the robot’s initial state and its goal, settling for any path that won’t introduce collisions.

 …