MA-LIPP: Cooperative Multi-Agent Load-Aware Informative Path Planning for Heterogeneous Robot Teams

Hojune Kim; Guangyao Shi; Gaurav S. Sukhatme

cs.ROSep 18, 2026

MA-LIPP: Cooperative Multi-Agent Load-Aware Informative Path Planning for Heterogeneous Robot Teams

Authors: Hojune Kim, Guangyao Shi, Gaurav S. Sukhatme

Organizations: School of Electrical and Computer Engineering University of Southern California Los Angeles, California · School of Computer Science University of Southern California Los Angeles, California

Abstract

Field robotics missions often require physical samples to be returned to laboratories for analysis, making path planning inherently load-aware and order-dependent as accumulated samples increase payload and traversal energy costs. In single-robot Load-Aware Informative Path Planning (LIPP), this rigidly couples sensing with hauling: a solitary robot must transport every collected sample, forcing frequent depot returns that severely restrict its spatial coverage. Heterogeneous multi-robot teams can overcome this bottleneck by dividing labor---enabling high-precision samplers to collect while high-capacity carriers handle transport. However, this introduces a complex coordination challenge regarding when, where, what, and to whom handoffs should occur on top of the LIPP problem. To address this tightly coupled problem, we introduce Multi-Agent LIPP (MA-LIPP), which enables teams to cooperate through asynchronous "dead drops," allowing one robot to deposit samples for another to retrieve later without requiring synchronous rendezvous. We formulate MA-LIPP as an exact Mixed-Integer Quadratic Program (MIQP) alongside a scalable Pairwise Large-Neighborhood Search (LNS) heuristic for complex real-world applications. The heuristic matches exact optima in $95.5\%$ of certified cases and reduces weighted posterior variance by $16.1$ -- $19.8\%$ relative to a sequential baseline on larger instances of up to 12 robots, providing a robust framework for cooperative physical-sampling missions.

Figures & tables

Fig. 1 : Planetary physical sampling with heterogeneous teams (samplers, carriers, and hybrid rovers) requires joint optimization of routing decisions, visitation order, and handoff locations/timing. MA-LIPP coordinates asynchronous sample transfers to decouple sensing from transportation, preventing payload-induced range limits and maximizing information gain.

Fig. 2 : Under Seq-LIPP, the scout cannot reach the right region after sampling the left because it must carry its accumulated payload. MA-LIPP enables the scout to drop its left-region samples at $H$ , cross the corridor empty-handed, sample the right region, drop there, and return to the depot empty-handed. A more capable carrier then retrieves and consolidates all samples for final delivery, decoupling information acquisition from transport.

Fig. 3 : Information gain over Seq-LIPP for joint planning without handoffs versus full MA-LIPP across three team sizes. The gap between bars highlights the incremental value of handoff. Error bars denote

95\%

confidence intervals across

100

instances per bin. Takeaway: Both joint planning and handoffs consistently outperform sequential routing, with physical transfers contributing roughly three times more value than joint routing alone—an advantage that widens as fleet size increases.

Fig. 4 : Mean information gain of MA-LIPP over Seq-LIPP across sample mass

\lambda

and sensor-noise ratio (

\sigma^{2}_{\mathrm{worst}}/\sigma^{2}_{\mathrm{best}}

). Surface height indicates the percentage reduction in weighted posterior variance across 120 base instances per configuration. Takeaway: Greater sensor disparity favors cooperation, but handoffs offer limited benefit when samples are too light to make transport costly or too heavy for the available energy budget to support much collection.

Fig. 5 : Top : Evaluation of LNS solution quality on the 334 instances where the exact MIQP solver successfully certified the global optimum, grouped by problem scale, with suboptimality rates reported at right. Bottom : mean posterior-variance reduction over Seq-LIPP versus search time since each run’s first incumbent. Shading denotes

95\%

confidence intervals; dashed lines mark mean baseline completion offsets. Each curve ends at its group’s shortest search duration to retain all 60 instances; an earlier endpoint does not indicate that all runs have stopped. Takeaway: LNS matches exact optima in

95.5\%

of certified cases and reaches a better plan earlier than the baseline finishes, with performance steadily increasing as we provide more time.

Multi-Robot Coordination

Multi-robot coordination studies how teams of robots plan, communicate, allocate tasks, and act together safely and efficiently.

See all 328 papers

LIPP: Load-Aware Informative Path Planning with Physical Sampling
Mar 6, 2026Hojune Kim, Guangyao Shi, Gaurav S. SukhatmeInformative Path Planning Constrained Optimization
School of Electrical and Computer Engineering University of Southern California Los Angeles, California · School of Computer Science University of Southern California Los Angeles, California
Collaborative Task and Path Planning for Heterogeneous Robotic Teams using Multi-Agent PPO
Apr 1, 2026Matthias Rubio, Julia Richter, Hendrik Kolvenbach +1Multi-Robot Task Allocation Multi-Robot Motion Planning
Robotic Systems Lab (RSL), ETH Zürich, Zürich, Switzerland
Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding
May 15, 2026Ning Zhou, Nikolai W. F. Bode, Edmund R. HuntMulti-Agent System Optimization Multi-Robot Coordination
University of Bristol

Mar 6, 2026J/K move · Enter open · S save

LIPP: Load-Aware Informative Path Planning with Physical Sampling

Hojune Kim, Guangyao Shi, Gaurav S. Sukhatme

School of Electrical and Computer Engineering University of Southern California Los Angeles, California · School of Computer Science University of Southern California Los Angeles, California

Informative Path Planning Constrained Optimization Motion Planning Mixed-Integer QP Robot Motion Planning

Open paper AskPDF arXiv

In classical Informative Path Planning (C-IPP), robots are typically modeled as mobile sensors that acquire digital measurements such as images or radiation levels. In this model, since making a measurement leaves the robot's physical state unchanged, the cost of traversing an edge remains static regardless of when it is traversed. This is a natural assumption for many missions, but does not extend to settings involving physical sample collection, where each collected sample adds mass and increases the energy cost of all subsequent motion. As a result, IPP formulations that ignore this coupling between information gain and load-dependent traversal cost can produce plans that are distance-efficient but energy-suboptimal, collecting fewer samples and less data than the energy budget would permit. In this paper, we first introduce Load-aware Informative Path Planning (LIPP), a strict generalization of C-IPP that explicitly models this coupling, with C-IPP recovered as the special case of zero sample mass. We then formulate LIPP as a Mixed-Integer Quadratic Program (MIQP) that jointly optimizes visitation location, order, and per-location sampling count under an energy budget. We further derive theoretical bounds on the path-length increase of LIPP relative to C-IPP, characterizing the trade-off for improved energy efficiency. Finally, through extensive simulations across 2,000 diverse mission scenarios, we demonstrate that LIPP progressively achieves higher uncertainty reduction per unit energy as sample mass increases.

Abstract

Multi-Robot Coordination

Explore similar work

LIPP: Load-Aware Informative Path Planning with Physical Sampling

Collaborative Task and Path Planning for Heterogeneous Robotic Teams using Multi-Agent PPO

Multi-Agent Cooperative Transportation: Optimal and Efficient Task Allocation and Path Finding