Extending Harmonic Function Methods via Root Locus for Coordinated Path Generation

Matteo Frascarelli; Lucia Pallottino; Alberto Landi

cs.ROOct 22, 2026

Extending Harmonic Function Methods via Root Locus for Coordinated Path Generation

Authors: Matteo Frascarelli, Lucia Pallottino, Alberto Landi

Organizations: Department of Information Engineering, University of Pisa, Pisa, Italy · Research Center E. Piaggio, Department of Information Engineering, University of Pisa, Pisa, Italy

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.

Figures & tables

Panel of Figure 1 — Figure 1: Conformal map of the polygonal workspace of the Flagship example onto a circular domain.

Figure 2: Two-robot example: GRL branches for

\theta=0.2

(solid) and

\theta=-0.2

(dash-dotted), and the critical family

\theta=0

(dashed) through the break point

b=0

. The assignment is exchanged across the critical phase. Crosses: starts; circles: goals.

Panel of Figure 3 — Figure 3: Reciprocal root locus in $D_{+}$ : (a) streamlines and equipotential lines of $\Omega_{r}$ ; (b) RRL branches for $\theta=0$ (dashed) and induced trajectories (solid).

	$m$	$\max_{i}\bar{\varepsilon}_{i}$	crit.	certified	margin of $\theta=0$
Flagship	1	3.48	6/6	27%	rejected
	2	2.01	7/7	53%	0.04 rad
	3	1.04	7/7	70%	0.33 rad
Warehouse	1	15.1	3/3	44%	0.30 rad
	2	8.39	5/5	73%	0.23 rad
	3	2.87	4/4	83%	0.22 rad

Table 1: Certificate on the reference examples: largest residual

\max_{i}\bar{\varepsilon}_{i}

, number of critical points found/predicted by ( 27 ), fraction of certified phases, and margin of

\theta=0

(distance to

\Theta_{b}\cup\Theta_{\partial}

Panel of Figure 4 — Figure 4: Flagship example, $m=3$ : (a) streamlines (blue) and equipotential lines (red) of $\Omega^{(3)}_{\mathrm{obs}}$ in $D$ ; (b) GRL branches for $\theta=0$ ; (c) paths mapped back to the workspace. Crosses: starts; circles: goals.

Panel of Figure 5 — Figure 5: Warehouse example, $m=3$ : (a) field of $\Omega^{(3)}_{\mathrm{obs}}$ in $D$ ; (b) branches for $\theta=0$ ; (c) paths in the workspace, with the shelves as obstacles.

	Flagship domain		Warehouse domain
	success	$L/L_{0}$	success	$L/L_{0}$
GRL (certified)	100%	1.15	100%	1.13
Independent HFM	74% ∗	1.06	78% ∗	1.03
APF	24%	1.12	6%	1.00 †

Table 2: Monte Carlo comparison (50 instances per domain,

N=5

, medians).

$i$	$c_{i}$	$r_{i}$	$i$	$c_{i}$	$r_{i}$
1	$-0.414-0.326j$	0.092	6	$\phantom{-}0.392+0.106j$	0.079
2	$\phantom{-}0.082-0.503j$	0.077	7	$-0.281+0.409j$	0.086
3	$-0.069+0.108j$	0.090	8	$\phantom{-}0.183+0.397j$	0.077
4	$\phantom{-}0.456-0.268j$	0.086	9	$-0.375-0.024j$	0.081
5	$\phantom{-}0.196-0.257j$	0.060	10	$-0.111-0.148j$	0.096

Table 3: Forest example: centers and radii of the obstacles in the unit disk.

Panel of Figure 6 — Figure 6: Forest example. (a) Streamlines (blue) and equipotential lines (red, dashed) of $\Omega^{(3)}_{\mathrm{obs}}$ ; grey diamonds: the 18 critical points. (b) Branches of $\mathrm{GRL}(\theta^{\ast})$ , $\theta^{\ast}=106.2^{\circ}$ , and positions of the robots at four common gains $k_{1}<k_{2}<k_{3}<k_{4}$ ; robot $i$ reaches $\zeta_{11-i}$ . (c) Top: arc of $\Theta_{\partial}$ contributed by each circle ( $C_{0}$ is the outer wall); bottom: distance of $\theta$ from $\Theta_{\partial}$ ; red dotted lines: critical phases; blue line: $\theta^{\ast}$ .

Multi-Robot Motion Planning

Multi-Robot Motion Planning coordinates collision-free paths and trajectories for robot teams sharing space, tasks, and changing environments.

See all 145 papers

Motion planning in high dimensional spaces hybridizing RRT and HAR via position-direction decoupling
Sep 15, 2026Frederic Cazals, Nelson FeyeuxMulti-Robot Motion Planning Motion Planning
Centre Inria at Université Côte d’Azur, France
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs
Mar 19, 2026Tsuri Farhana, Omrit Filtser, Shalev GoldshteinMulti-Robot Motion Planning Approximation Algorithms
Department of Computer Science, Ben Gurion University, Beer Sheva, Israel. · Department of Mathematics and Computer Science, The Open University of Israel, Ra’anana, Israel
Continuous-Time Motion Planning and Steering with Global Convergence
Oct 22, 2026Mohsen Amiri, Sima Didari, Davoud Ataee Tarzanagh +2Constrained Motion Planning Motion Planning
Samsung SDS Research America, Mountain View, CA, USA

Sep 15, 2026J/K move · Enter open · S save

Motion planning in high dimensional spaces hybridizing RRT and HAR via position-direction decoupling

Frederic Cazals, Nelson Feyeux

Centre Inria at Université Côte d’Azur, France

Multi-Robot Motion Planning Motion Planning Sampling-Based Motion Planning

Open paper AskPDF arXiv

The exploration of high-dimensional spaces remains a challenging problem, in particular in the presence of narrow passages and small clearances. We propose novel sampling-based path-planning methods for high-dimensional spaces combining Rapidly-exploring Random Trees (RRT) and Hit-and-Run (HAR) random walks by decoupling the point being extended from the direction of extension. We also show that RRT and HAR appear as special cases of a generic algorithm coupling the biases used for the point and direction extension, respectively. We further study a sparse-move strategy in which only a fraction p_r of the robots is moved at each step, helping both RRT and the proposed HAR algorithms handle cluttered instances. Tests are presented for two families of models: classical piano mover problems in 3D, and complex molecular systems involving tens of rigid domains moving relatively to one another -- the latter viewed as independent robots exploring the motion space SE(3)N . Within seconds on a standard laptop, our algorithms solve instances with up to 64 robots and 384 degrees of freedom. We conclude by suggesting one of our methods, HARF, as the method of choice for complex multi-robot planning problems, being up to two orders of magnitude faster than the classical RRT moving all robots at each step--when it succeeds at all, and still up to 2.4 fold faster on most instances when both use their best p_r.

Abstract

Multi-Robot Motion Planning

Explore similar work

Motion planning in high dimensional spaces hybridizing RRT and HAR via position-direction decoupling

Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-offs

Continuous-Time Motion Planning and Steering with Global Convergence