Probabilistic roadmaps
In August 1996 Kavraki and Latombe of Stanford and Švestka and Overmars of Utrecht published in IEEE Transactions on Robotics and Automation (volume 12, issue 4, pages 566-580) a two-phase motion planning method: in a learning phase, randomly sampled collision-free configurations of the robot are joined by a simple, fast local planner into a graph, the roadmap; in a query phase the start and goal configurations are connected to the graph and a path is searched in it. For planar articulated robots with many degrees of freedom, planning takes a fraction of a second on a workstation of about 150 MIPS after a few dozen seconds of learning.
Why it matters
Motion planning for bodies with many degrees of freedom, which exact methods had made practically impossible through the size of the configuration space, became a matter of seconds: instead of describing free space, one samples it. Planning for the manipulators and humanoids of the following decades stands on this.
By the abstract, the method is general and easy to implement, applicable to virtually any holonomic robot, requires choosing a few parameters (for instance the duration of the learning phase) that depend on the scene but turned out to be easy to choose, and can be made more efficient by tailoring components (for instance the local planner) to the robot at hand. The full text, read later, adds one of the experiments (page 576): a free-base articulated robot with seven degrees of freedom, two for the base and five revolute joints, in a scene with eight test configurations; with a customised planner and expansion, after about 70 seconds of learning all eight were connected to the roadmap. The manuscript was received on 18 August 1994 and revised on 1 May 1995. What the record does not claim: the results of the other scenes or any figure beyond those quoted.