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 record rests on the abstract, because the full text is paywalled. What the record does not claim: the number of degrees of freedom in the experiments, the share of successful queries, the size of the roadmap or any figure beyond those quoted.