Motion planning: A journey of robots, molecules, digital actors, and otherartifacts

During the past three decades, motion planning has emerged as a crucial and productive research area in robotics. In the mid-1980s, the most advanced planners were barely able to compute collision-free paths for objects crawl ing in planar workspaces. Today, planners efficiently deal with robots with many degrees of freedom in complex environments. Techniques also exist to generate quasioptimal trajectories, coordinate multiple robots, deal with d ynamic and kinematic constraints, and handle dynamic environments. This pap er describes some of these achievements, presents new problems that have re cently emerged, discusses applications likely to motivate future research, and finally gives expectations for the coming years. It stresses the fact t hat nonrobotics applications (e.g., graphic animation, surgical planning, c omputational biology) are growing in importance and are likely to shape fut ure motion-planning research more than robotics itself.