New method plans safe paths for multiple robots around obstacles
Extending Harmonic Function Methods via Root Locus for Coordinated Path Generation
Robotics
Summary
When many robots need to reach targets without crashing into obstacles or each other, planning their paths can be complicated. The authors propose a mathematical way to design smooth, non-colliding routes for multiple robots using special functions and a unique mapping of the environment. Their method ensures each robot reaches a unique goal safely and at the same time without hitting obstacles. They tested this approach on different robot and obstacle setups and compared it with other planning methods.
What this means in practice
- •For robotics engineers: Generate coordinated, collision-free paths for multiple robots working together in known environments with obstacles.
- •For industrial automation teams: Plan precise and timed robot movements in manufacturing spaces with complex layouts to improve workflow safety and efficiency.
Authors
Matteo Frascarelli, Lucia Pallottino, Alberto Landi
Abstract
We consider the offline generation of coordinated paths for N interchangeable robots and N goals in planar environments with polygonal obstacles. After a conformal map to a circular domain, starts and goals become the poles and zeros of a rational function R, and the paths are the branches of its Generalized Root Locus (GRL), i.e. the streamlines of the logarithmic potential -log R. We show that, for every phase outside a finite set of critical phases and a set of boundary phases, the induced gradient motion drives each robot to a distinct goal along pairwise disjoint paths that never reach the obstacles; the robot-goal assignment is produced by the construction, and with the gain used as a clock all robots move as the closed-loop roots of the GRL and arrive together at a prescribed time. Obstacles become streamlines through successive Milne-Thomson reflections, and for a finite number of reflections a finite test certifies safety for the potential that is actually computed. Reciprocal root-locus planning is recovered as a special case. The method is illustrated on two polygonal workspaces, 100 random instances compared with independent harmonic planning and artificial potentials, and a scene with ten robots and ten obstacles.