Multi-agent Time-based Decision-making for the Search and Action Problem

In short: many real robot jobs mean finding things and then doing something with them, as a team and against the clock. A drone competition turns that into a concrete, scorable test.

Robots are getting good enough to work in messy, changing places: search-and-rescue, exploring an area with several robots, monitoring terrain. In many of these jobs a team has to search an area and act on what it finds. How to split that work between robots is still an open question.

The paper uses Challenge 3 of the Mohamed Bin Zayed International Robotics Challenge (MBZIRC) as its test case. Three drones share a 100 m × 60 m field. Objects of three kinds are scattered around, each colour worth a different number of points:

• static objects lie still and come in several point values (10 of them),
• moving objects wander randomly and are worth more (10 of them),
• large objects need two drones to lift (3 of them; left out of this paper, which notes they could be added with simple cooperative logic).

A drone must fly over the field with a downward-looking camera, find objects, pick one up, and drop it in a box in the middle of the field. Points count only on delivery. All three drones start from the same spot, and the mission lasts 20 minutes.

The authors list four difficulties: coordinating several drones to explore; tracking moving objects; trading off exploring for new objects against collecting known ones; and deciding with a hard time limit.

In short: whether to grab what you have found or keep looking depends on how much time is left, so a fixed rule cannot get it right.

The paper’s own example: a drone could greedily pick up an object it has found and bank its points. But it might do better to keep exploring and find a more valuable object nearby. Which is better depends on the time remaining. With a strict time limit, exploring becomes risky and acting greedily may be the better choice.

To reason about this, every action gets a price in seconds. Collecting object i costs

and earns its points r_i on delivery. In the paper’s simulations the drone flies at 2 m/s, picking up takes 25 s for a static object and 45 s for a moving one, and dropping takes 20 s. A search action costs its flight time.

Scene 2 plays the same find under two clocks. With 150 s left, a 60 s search followed by collecting a 3-point object fits; with 100 s left, it does not, and collecting the 1-point object now is the only way to score. The distances there are made up for the example; the pick-up and drop times are the paper’s.

In short: earlier approaches either search well or act on what they find, but none of them trades the two off against a clock.

What earlier work did

• Coverage. Plan a path that passes over every point of the area, for example a zig-zag sweep, possibly split among several drones. Great for things that stay put, but a moving object can wander into ground that was already swept.
• Pursuit–evasion games (“cops and robbers”). Guarantee capture even if the target moves in the worst possible way. They assume perfect knowledge or ignore real sensing limits.
• Probabilistic search. Keep track of how likely a target is in each place and search where it pays most. This paper follows that line. Planning it exactly (as a POMDP, a model for deciding under uncertainty) becomes far too slow as the number of searchers grows. A shortcut by Hollinger and Singh lets searchers plan one after another, with near-optimal results and effort growing only linearly with team size. It assumes all searchers act in lock-step.
• Search and action. Hollinger and colleagues first combined searching with acting on targets, minimising the total time. Their method acts as soon as a target is found. This paper lets each agent choose between searching and acting, given the time budget.

The three benchmark rules

To test their method, the authors compare against three fixed strategies:

• Random: all drones fly random paths and pick up any object the moment they find it.
• Cover-field-first: first sweep the whole field in a zig-zag, then collect the static objects in order of time per point. Moving objects are grabbed as soon as they are seen. After that, fly randomly to find more moving ones.
• Cover-and-pickup: each drone sweeps its own part of the field and grabs every object it finds, then returns to where it left off.

In short: from what has been found so far and the time left, the method computes the best score the team could still deliver. Every decision is judged by how it changes that number.

The main idea is to treat time as a budget. Each drone starts with the mission time limit, and every action spends some of it while earning some reward. Suppose the team has found a set of objects 𝒯, each with a cost c_i and reward r_i. The reward prediction J(𝒯, t) is the largest total reward the drones could collect from those objects within their remaining time:

This is the knapsack problem: pack the most valuable items into a bag of limited size. The paper solves it exactly with dynamic programming.

A detail that matters: the first object is special

The cost of an object depends on where the drone starts. After a delivery the drone is always at the box, so every object after the first is costed from the box, and their order does not matter. Only the first one is costed from the drone’s current position. The paper therefore keeps two dynamic-programming tables, one with costs from the box and one with costs from the drone. Each found object ends up with one of three labels: pick up now, pick up later, or do not pick up.

Moving objects are treated as static for a short while after they are seen. If a drone has not seen one for longer than a threshold (4 s in the 2-D simulation), it counts as unknown again and has to be searched for.

In short: to value a search before flying it, each drone keeps a map of how likely each patch is to hide an object, and updates it with everything the team sees.

The chance of finding new objects comes from a probability density map: the field is cut into a grid, and a Bayes filter keeps, for every cell, the probability that a given object is there. Each object has its own map. At every step the filter does two things:

• Predict: move probability according to how the object can move. A static object’s probability stays exactly where it is. A moving object is treated as a random walk: it stays in its cell with probability 1 − p_out, or moves to each of its 8 neighbours with p_out/8.
• Correct: fold in what the cameras saw. Detections come from a downward-facing camera; each drone’s position comes from GPS fused with visual odometry. Cells seen empty drop, cells with a detection rise.

Search paths are planned on a coarser grid whose cells are the size of the camera’s view (10 m × 10 m in the 2-D simulation). Each cell’s colour is the sum over objects of (chance of finding it there × its points).

In short: a drone searches only if the best search path is expected to raise the predicted final score; otherwise it collects. The same rule covers every situation, with no tuning knob.

For a search action a that takes time c_a, the paper defines its value as the expected change in the predicted score:

The two J terms do the work. Finding something new can raise the predicted score, but the search itself eats time (t − c_a), which can push known objects out of the knapsack. So the value of searching can be negative even when finding something is likely.

The decision rule (Algorithm 1): evaluate every candidate search path and take the best one. If even the best value is below zero, execute a known task (collect an object) instead.

Four decisions from the 3-D simulation

The paper shows the rule producing sensible, situation-dependent choices (scene 6 lets you replay each one):

1. Explore. Early in the mission the drones skip objects they have already found, because there is plenty of time to find better ones.
2. Pick up a moving object. A drone collects a moving object as soon as it sees it. If it flew away, the object would become unknown and the predicted score would drop.
3. Pick up static objects. With many static objects found and little time left, searching lowers the predicted score, so the drones collect.
4. Static instead of moving. A drone finds a new static and a new moving object at once. With enough time it would go for the moving one; with little time it takes the static one, whose pick-up is shorter. A simple rule like “always grab moving objects first” cannot do this.

In short: the drones plan one after another, each counting what the others already chose. This is fast enough for real time and provably close to the best team plan.

The method extends Hollinger and Singh’s multi-robot search planner (MESPP). Instead of searching over all combinations of the drones’ actions, one drone chooses its best action; the next drone chooses while taking the first drone’s choice into account; and so on. The effort grows linearly with the number of drones instead of exponentially.

Why this is near-optimal

The paper defines a team objective F(A) = J(𝒯_A, t₀): the predicted score from all objects found along the actions A, with the initial time limit. Running the decision rule is the same as greedily adding the action that raises F the most. The appendix sketches proofs of two properties:

• non-decreasing: finding more objects never lowers the best achievable score;
• submodular (diminishing returns): a new find adds less when you already know more objects, because the knapsack is fuller.

For such functions, greedy one-at-a-time planning is guaranteed to reach at least 1 − 1/e ≈ 63.2 % of the optimum.

Running as a real system

Each drone keeps its own probability map and shares its decisions, position and detections with the others, so all maps are updated from the same information. A drone decides again every time it finishes an action (an exploration path or a pick-up), so the drones do not need to act in lock-step. They also notice when a teammate is unavailable and plan around it, so the team can adapt if a drone crashes.

In short: thinking about the clock pays off most when time is short; with lots of time, the method keeps up with a full sweep.

Setup

The comparison ran in a 2-D Python simulator in which three drones fly at a constant height and reliably detect objects in their camera view. Each method was run with time limits of 100, 200, … 900 s, with five trials per limit and random object positions.

What this means: picking up and delivering one object takes most of a minute even next to the box, so in a 200 s mission a drone can make only a few deliveries, and every choice counts.

Scores across time limits

The paper reports results as plots only, so here are its written conclusions rather than numbers read off the chart:

What this means: a strategy that ignores the clock can do well when time is plentiful, but only a time-aware one does well across the whole range.

Full system in a 3-D simulator

The decision module also ran inside the team’s complete drone software in RotorS, a Gazebo-based simulator, with three simulated AscTec Firefly drones. That system includes attitude control, localisation, object detection, a state machine, visual servoing for pick-up and collision avoidance. The decision module takes detected objects and drone states and outputs either waypoints to explore or an object to pick up. The four decision examples in section 6 come from this setup, showing that the framework is ready to integrate with a real system.

In short: one principled rule for “search or act” under a deadline, shown in simulation; the next steps are other missions, other resources and less known worlds.

What to keep in mind

• All results are from simulation: a 2-D simulator for the comparison and a Gazebo simulation for system integration.
• The comparison uses five trials per time limit, and results are reported as plots.
• Large objects that need two drones are not handled (the paper argues simple cooperative logic could add them).
• The 2-D simulator assumes objects in view are always detected, and the value of a search uses an approximation that sums over individual objects.

Where it could go

• Other search-and-action missions such as search-and-rescue, wherever each task and each search move has a time cost and a reward.
• The “time” budget could be another limited resource, such as battery charge or energy.
• Other ways of estimating the chance of finding new tasks, for fields of unknown size or unknown distributions.
• Flying at different heights, other sensors, and unknown environments or tasks.