Extending Harmonic Function Methods via Root Locus for Coordinated Path Generation

1. Introduction

• Existing approaches leave a gap: artificial potentials may have local minima, while reciprocal root-locus obstacle avoidance uses heuristic corrections without a non-penetration proof.Harmonic-function methods remove interior extrema, but the paper frames certified obstacle-respecting coordinated paths as unresolved.Source: §1 · pp. 1–2
• The GRL combines harmonic-field streamlines with root-locus branch structure by encoding starts and goals as poles and zeros of a rational function.Its branches are streamlines of the logarithmic potential −log R.Source: §1 · p. 1
• For phases outside finite critical and boundary sets, the GRL yields N disjoint start-to-distinct-goal paths, with construction-induced assignment and synchronized arrival at a prescribed time.The result applies to bounded domains with obstacles; gain serves as the clock for closed-loop root motion.Source: §1 · p. 2
• For finite reflection depth, a boundary-residual bound and finite test certify obstacle safety for the computed potential.Successive Milne–Thomson reflections make obstacles streamlines.Source: §1 · p. 2
• The reciprocal root-locus planner is recovered with the same guarantees, supplying its previously missing boundary-invariance argument.The paper identifies this as a special case of the GRL construction.Source: §1 · p. 2
• The work evaluates its complete procedure on reference examples, 100 random instances compared with independent harmonic planning and artificial potentials, and a ten-robot, ten-obstacle scene.The critical set is verified using the argument principle.Source: §1 · p. 2

2.1. Workspace and canonical domain

• At planning level, robots are interchangeable point agents; for radius ϱ, obstacle inflation and outer-boundary shrinkage provide environmental clearance, but mutual safety additionally requires paths separated by more than 2ϱ.The path-separation condition is checked after planning and may be included in phase selection.Source: §2.1 · p. 2
• A conformal map sends the polygonal workspace to a disk with Nobs −1 closed disks removed, and maps the workspace boundaries to circular components.The map and inverse are computed with PlgCirMap, and an interior point α in a central free region is normalized to the origin.Source: §2.1 · p. 2
• In the mapped domain, the planning task is to connect poles representing starts to zeros representing goals by smooth, pairwise disjoint curves, with pairing produced by the construction.Paths are mapped back to the workspace by f−1.Source: §2.1 · p. 2

2.2. Complex potential and Generalized Root Locus

• The scalar potential Φ = −log |R| is harmonic outside the poles and zeros, while the stream function Ψ = −arg R is defined modulo 2π.The associated gradient and stream-function gradients are orthogonal and have equal norm.Source: §2.2 · p. 3
• For fixed phase θ, the GRL consists of points satisfying 1 + ke^{jθ}R(z) = 0 for some k > 0; equivalently, Ψ(z) ≡ θ + π and k = e^Φ(z).The GRL extends classical root locus, with GRL(0) and GRL(−π) corresponding to its positive and negative root loci.Source: §2.2 · p. 3

2.3. Gradient-induced motion

• Each robot follows the scalar-potential gradient with positive locally Lipschitz speed modulation λ, which changes timing but not the integral curves.The stream function stays constant along the motion, and gain is nondecreasing.Source: §2.3 · pp. 3–4
• The gradient-motion lemma is local: it does not establish a trajectory’s destination, rule out branch meeting at a break point, or ensure that it stays in the workspace.These global questions motivate the subsequent certification analysis.Source: §2.3 · p. 4

3. Break points and critical phases

• A break point is a point outside the poles and zeros that is a multiple root of 1 + ke^{jθ}R(z) = 0 for some phase and positive gain.Break points are critical points, or stagnation points, of the complex potential.Source: §3 · p. 4
• For points outside the poles and zeros, vanishing ∇Φ, ∇Ψ, Ω′, and R′ are equivalent; each critical point determines a break-point phase.The associated phase is π −arg R(b).Source: §3 · p. 4
• For the rational function encoding N starts and N goals, the number of break points is at most 2N −2.The bound follows by identifying break points with zeros of the numerator of R′ outside the poles and zeros.Source: §3 · p. 4
• When image singularities are present, the obstacle-free break-point bound no longer applies, so the number of critical points in the domain is verified by the argument principle.Critical phases are the phases whose GRL family contains a break point.Source: §3 · p. 4
• When R is meromorphic near the domain, its critical points are finite, so the associated set of critical phases is finite and can be computed once.The critical points do not depend on θ.Source: §3 · p. 4

• Admissible phases exclude critical phases and families that touch the boundary; Assumption 1 requires simple interior zeros and poles and finite, nonzero R on ∂D.The theorem covers bounded domains under these assumptions.Source: §4 · p. 5
• Each admissible phase yields exactly N disjoint smooth arcs pairing starts bijectively to distinct goals, with no path meeting another or ∂D.The pairing is produced by the construction rather than prescribed.Source: §4 · pp. 5–6
• For locally Lipschitz positive gains, trajectories remain on their assigned arcs and converge to their assigned zeros.Along each arc, κ increases without bound, so the trajectory tends to its zero endpoint.Source: §4 · pp. 5–6
• A shared increasing gain k(t) that diverges at T makes the robots the closed-loop roots and brings them to their goals together at T.For k(t) = tan(πt/2T), the text states that speed is continuous and positive through the motion.Source: §4 · pp. 5–6
• The proof establishes regular branches away from critical points, rules out boundary endpoints, then uses simple pole and zero ends to prove bijective pairing.Compactness of D and exclusion of boundary phases force branch endpoints to be zeros; the same argument identifies pole endpoints.Source: §4 · pp. 5–6
• The pole residue and phase condition determine each branch’s departure direction, which is used to initialize numerical tracing.Source: §4 · p. 6
• The assignment is constant on each admissible phase interval and can change only across critical or boundary phases; phase also selects path shape.Source: §4 · p. 7
• In the obstacle-free plane, only phase −π remains boundary-excluded as the disk grows, matching the negative root locus; every other noncritical phase fits a sufficiently large disk.Source: §4 · p. 7

5.1. Boundary conditions

• The homogeneous Neumann condition is equivalent to constant Ψ_obs on each obstacle circle, making each circle a streamline and reducing its contribution to boundary phases to one phase.Clearance margins still require inflating obstacles beforehand.Source: §5.1 · p. 7

5.2. One circle: the Milne–Thomson correction

• For one circle, the Milne–Thomson correction adds image singularities while making the circle a streamline; in a disk example, one reflection reduces excluded boundary phases to −π.The correction is rational and balanced, with image singularities inside the obstacle only.Source: §5.2 · p. 8

5.3. Several circles: successive reflections

• Successive reflections correct multiple circles, and the truncated rational function retains the original zeros and poles in D while placing image singularities outside D.Theorem 1 applies to the computed finite-depth potential; the number of images grows geometrically with reflection depth.Source: §5.3 · pp. 8–9

5.4. Residual and certificate

• The residual bounds the total length of excluded boundary phases, and sampled boundary values with a slope bound provide a finite test that certifies a phase is not excluded.The bound vanishes with the residual; the slope constant can be conservative and require many samples per circle when there are many images.Source: §5.4 · p. 9
• A finite test certifies that admissible phases yield convergent, mutually disjoint, obstacle-respecting paths for the computed potential, without assuming convergence of the reflection series.The residual bounds how many phases the test rejects; it does not itself establish non-penetration.Source: §5.4 · p. 9

5.5. The reciprocal root locus as a special case

• In D+, the reciprocal construction makes the unit semicircle and interval (−1, 1) level sets, so the classical θ = 0 branches remain inside and join distinct goals when 0 is not a boundary phase.The paper attributes geometric confinement to streamline invariance.Source: §5.5 · p. 10

Algorithm 1: Certified GRL planning

• The procedure maps the workspace and starts/goals into D, generates reflected images to depth m, and forms the corresponding rational potential.It uses a conformal map and the finite-depth reflected function.Source: §6 · p. 11

Critical points and Θ_b

• Critical points are found by Newton’s method from a grid, and the argument-principle count is used to check that the grid search found the full set.If the counts differ, the grid is refined.Source: §6 · p. 11

Boundary phases and certificate

• Boundary samples are reused across a grid of phases to evaluate the certificate, and the selected phase maximizes its margin from excluded phases.A secondary criterion such as path length or clearance may also be used.Source: §6 · p. 11

Branch tracing

• Branches are traced in log-gain Φ with predictor–corrector steps until a zero is reached, then mapped back to the workspace.The assigned goal is identified by the zero reached by each branch.Source: §6 · p. 11

7.1. Reference examples with polygonal obstacles

• For the reference examples, the critical-point count matched the argument-principle count, and the certified fraction of phases grew with reflection depth.For the Flagship example at m = 1, the θ = 0 certificate failed and the traced branch entered an obstacle by 0.04; at m = 2 and m = 3, it was certified with clearances of 0.004 and 0.025.Source: §7.1 · p. 12

7.2. Monte Carlo comparison

• All 100 GRL instances were certified; independent HFM paths were shorter but crossed in about one instance out of four, while GRL paths cost about 10% more in length.APF failed mostly because of local minima behind obstacles; the median computation time for the two harmonic methods was comparable at 18–42 s per instance.Source: Table 2 · p. 13, §7.2 · p. 13

7.3. Forest: ten robots and ten obstacles

• About 69% of the forest phase circle was admissible, with sampled boundary phases covering 120° in total and each circle removing an arc of 6.4° to 18.0°.The large constant in the certificate led the authors to report sampled boundary phases, whose spacing was much smaller than the margins involved.Source: §7.3 · p. 14
• In the ten-robot forest, the selected phase produced ten disjoint branches to distinct goals, with a minimum path-to-obstacle or wall distance of 0.011.The total path length was 15.35 versus 13.82 for straight segments with the same assignment, a ratio of 1.11.Source: §7.3 · p. 14, Figure 6 · p. 14
• Across all 47 admissible phases tested on a 5° grid in the forest, branches stayed inside the domain, remained disjoint, and reached distinct goals.The four assignments observed changed only across critical phases.Source: §7.3 · p. 14

8. Conclusions

• For every admissible phase, the construction gives distinct goals, disjoint paths, an induced assignment, and a gain-based time law for interchangeable robots in polygonal environments.The claim is for the computed potential when obstacle reflections are finite.Source: §8 · p. 14
• A finite test certifies obstacle safety for potentials computed with finitely many reflections, and RRL is recovered as a special case.The RRL recovery supplies the boundary-invariance argument that was missing.Source: §8 · p. 15
• The method is offline and geometric; tracking, dynamics, and online replanning remain for execution, robot size is handled through obstacle inflation, and path optimality is not claimed.Open directions include faster series-based obstacle potentials, a sharper certificate, phase and normalization studies, and coupling with an online layer.Source: §8 · p. 15