Multi-Robot Coordination

A robot team on a planetary surface has to agree on where each member is, what each has seen, and who decides, over a radio link that is intermittent and slow, on processors that are individually weaker than one rover’s. CADRE is the flight article for that problem: three identical rovers plus a base station, targeted at Reiner Gamma [1]. Its stated objective is to demonstrate the first autonomous exploration and distributed measurement by a team of rovers on another planetary body, with the least possible ground intervention.

The platform the algorithms run on

Property	Value
Team	3 identical rovers plus 1 base station
Rover dimensions with solar panels deployed	about 0.75 x 0.5 x 0.2 m
Rover mass	under 10 kg each
Compute	ModalAI VOXL with Qualcomm Snapdragon 821 SoC
Memory	4 GB RAM, 32 GB flash
Radio	Microhard mesh network, minimum 1 Mbps aggregate shared between all stations
Base station	comparable computing and wireless capability, no sensors and no mobility

Source: [1]. The 1 Mbps figure is aggregate across the whole network, hundreds of times slower than a terrestrial equivalent, and the concept of operations cannot assume continuous transmission across the mesh at all.

Bandwidth as the classification axis

Coordination algorithms are usefully sorted by how much communication they demand. Low bandwidth algorithms have each agent communicate with a subset of its neighbors; medium bandwidth algorithms have each agent communicate with all its neighbors at each time step; high bandwidth algorithms require every agent to reach every other, potentially over multiple hops, at each time step, which is the class that contains centralized algorithms implemented over a shared-world architecture [5]. Scalability is classified in tiers of 2, 20, 100 and over 1000 agents, and maturity by whether a technique has been demonstrated in hardware in the lab or in flight. A three-rover team on a shared 1 Mbps mesh sits at the bottom of the scalability axis and cannot afford the top of the bandwidth axis [1][5].

Shared state under intermittent communication

MoonDB is the shared state database. It stratifies data into three classes by urgency [1]:

• Key data: what every agent needs to hold a consistent view for multi-agent planning.
• Mission-critical data: large asynchronous products where total transmission matters more than latency, maps being the example.
• Time-sensitive data: information whose value expires, such as relative positioning between neighboring rovers on a collision trajectory.

Each data type carries an explicit sharing policy of none, latest or all [1]. Replication is implemented with two tables, replica and replication_log: any record marked for sharing is entered in replica keyed by the table and key of the underlying record, and each transmission attempt is logged with sent status and acknowledgement, so a record found in replica but not in replication_log is one still owed to a peer, and duplication is avoided by checking the log. A received record is appended to the data table and to both replication tables, so a relayed record propagates onward, and the database persists across the periodic shutdowns the rovers undergo, which is what makes data from previous wake cycles available at all.

Map merging

Each rover builds a robocentric local traversability map as a four-layer pyramid, each layer at half the resolution of the layer below, so the same map holds high resolution near the rover’s path and low resolution further out. Merging maps from several rovers therefore means merging maps of differing resolution covering different regions, which is why simple raster merging heuristics were rejected. The merge policy resolves disagreement on two assumptions: higher-resolution information is more accurate than lower-resolution information, and newer information at the same resolution is more accurate than older. Three sources of disagreement are identified [1]:

1. The multi-resolution structure itself, where a low-resolution cell assigns one value to a region covered by several high-resolution cells.
2. One rover appearing in another’s field of view, which enters the observer’s local traversability map as an obstacle. Because rovers do not share their positions directly into the map, the obstacle persists until the observer sees the region again with the other rover gone.
3. Inconsistency between mapping components, from pose or extrinsic error.

Merging is implemented in OpenGL so it can use the GPU. The accelerated implementation gives an order-of-magnitude speedup over a naive CPU implementation when merging 100 or more maps, and the OpenGL implementation is faster than the naive one even when executed on a CPU [1]. Pose graph optimization periodically recomputes the set of past and current rover poses that maximizes the likelihood of the observed visual-inertial odometry and ultra-wideband ranging measurements, and each stored local map is registered by two transforms, global frame to robot pose and robot pose to map origin, so a map can be repositioned after the fact when the pose estimate improves.

Who decides

CADRE assigns three roles: a leader that coordinates the team, a designated survivor that backs the leader up, and standard rovers [2]. Leader election has to run onboard because selecting a leader from the ground is cumbersome or impossible in situ, and because a leader that stops being fit for efficient operation has to be replaced without waiting for a ground cycle.

The algorithm is built on Gallager-Humblet-Spira: construct a minimum spanning tree over the possibly disconnected graph of agents, select a root node, and use that root as the appointer to name the leader [2]. Classical distributed leader election results assume properties that embedded space robotics hardware does not provide, and the practical requirements added are tolerance of shifting network connectivity including loss of agents, and implementation inside a spaceflight robotics software framework. Raft was rejected because it fails with fewer than three nodes, and Paxos for its complexity relative to the available redundancy. The algorithm was demonstrated in CADRE’s four-agent setting using CADRE’s flight software implementation.

Dividing the work

The exploration planner partitions the unexplored area into sub-regions, one per rover, regardless of the shape and size of the region, so that each rover explores its own sub-region without further inter-rover negotiation [3]. The leader performs the map division; a mission is counted complete when at least 95 percent of the total area has been explored.

Parameter	Simulation	Mercury-7 hardware
Environment	ROS, 30 x 30 m	JPL Moon Yard, 6 x 6 m and 8 x 6 m regions
Map	150 x 150 cells at 0.2 m per cell	as simulation
Obstacle density	3 percent cumulative fractional area	as in the yard
Agent size	0.25 x 0.20 m, differential drive	3D-printed chassis and wheels
Sensor footprint	2 m depth, 90 degree field of view	mapping reduced to 5 Hz to manage data processing load
Maximum velocity	2 m/s	0.05 m/s
Trials	50 per scenario, 3 map layouts	3 scenarios including a resilience test

Source: [3]. The 3 percent obstacle figure is described as a conservative estimate relative to what CADRE expects at Reiner Gamma. The metrics tracked are total exploration time, average distance traversed per agent, maximum distance traveled by any agent, and message count.

The gap between 2 m/s in simulation and 0.05 m/s on hardware, and the reduction of mapping to 5 Hz on the hardware rovers, is the practical cost of running the same algorithms on the real compute and sensing stack [3].

Onboard planning and execution

Each rover runs a planner beneath the team-level coordination: team planners generate cooperative activities subject to available resources and inter-rover separation constraints, and an agent planner on each leader refines the instructions it receives [1]. The underlying integrated planning and execution approach, MEXEC, merges planning and execution rather than separating them, using task networks to generate and execute conflict-free schedules against goals, with a tight coupling between planner and executive so that both share one timeline library [4]. When an unexpected event occurs the planner replans a new schedule while the executive continues executing tasks that are unaffected. Its flight qualification path ran through the ASTERIA 6U CubeSat, a collaboration between JPL and MIT launched on 20 November 2017 for a 90 day prime mission, used in its third extended mission as an onboard autonomy testbed [4]. The memory budget on ASTERIA was 2 MB, which limited task networks to 100 tasks or fewer [4]. MEXEC also served as an onboard planning prototype for the Mars 2020 rover.

The microgravity precedent

SPHERES flew the formation-flight version of the same problem inside the ISS. In the March 2007 test session, two satellites placed facing away from each other, with initial pointing errors of 160 and 151 degrees, executed a global search using the ultrasonic beacon frame and reduced pointing error below 10 degrees within 60 s, the first 15 s of which is allocated to global estimator convergence [6]. A relative search using only inter-satellite measurements, with initial errors of 167 and 158 degrees, brought both below 5 degrees within 60 s, and alignment error between the two body z-axes stayed within 15 degrees. The work covered formation acquisition with limited field of view relative sensors, synchronization of the satellites’ motion, and fuel balancing across the formation to extend mission duration. Close examination of the results showed a multipath problem in the ultrasonic signal.

Failure modes

The design assumption that breaks first is connectivity. MoonDB is built for a network that is neither continuously connected nor reliable, so every mechanism is an eventual-consistency mechanism rather than a consensus one, and the sharing policies exist to keep the traffic inside the shared 1 Mbps [1][5]. Leader election has to survive agents disappearing from the graph, which is the condition under which classical algorithms either fail or become non-deterministic [2].

Phantom obstacles are the mapping failure mode with an operational cost: another rover observed in transit is recorded as an obstacle, and clearing it requires the observing rover to spend enough time viewing that region after the other has left [1]. The merge policy’s preference for newer and higher-resolution data is what eventually removes it, so the failure is self-correcting only if the survey pattern revisits the area.