In recent years, robots play an active role in everyday life: medical robots assist in complex surgeries; search-and-rescue robots are employed in mining accidents; and low-cost commercial robots clean houses. There is a growing need for sophisticated algorithmic tools enabling stronger capabilities for these robots. One fundamental problem that robotic researchers grapple with is motion planning—which deals with planning a collision-free path for a moving system in an environment cluttered with obstacles.13,29
To a layman, it may seem the wide use of robots in modern life implies that the motion-planning problem has already been solved. This is far from true. There is little to no autonomy in surgical robots and every owner of a house-cleaning robot has experienced the highly simplistic (and often puzzling) routes taken by the robot.