Beyond Changing Light Bulbs: How Many Robots are Needed for Search and Rescue, Military Ops, and Mine Sweeps? New Equations Seek Best Answer
By Lori Cameron
Share this on:
Here’s a riddle for you: How many robots does it take to patrol an area, covering a certain point every few seconds, on some of the biggest missions possible—surveillance, infrastructure security, search and rescue, mine clearing, military ops, environmental monitoring, and, yes, even household cleaning?
Researchers have now devised an elaborate set of equations to seek an answer.
Now that the age of robots has dawned, we humans will be expecting a lot from them. But, whatever they do—saving lives or vacuuming the floor—we want it done quickly and efficiently.
Traveling salesman problem: Effective and near-optimal multi-robot patrol routes
The authors analyzed and studied two classical problems to produce effective and near-optimal multi-robot patrol (MRP) routes: graph partitioning, in which an area can be partitioned into smaller spaces depending on the tasks to complete in each, and the traveling salesman problem (TSP), in which researchers look for the shortest distance a robot can go to cover a set of points, passing through each one only once.
Then, based on these routes, they provided a numerical treatment to estimate the upper-bound performance of the team of robots prior to the mission, using worst idleness as the performance criterion.
Finding effective trajectories for multi-robot patrol routes
The authors describe two classical approaches have been used in the past to obtain optimal and near-optimal patrol routes: cyclic and partitioning-based routes.
However, partitioning-based trajectories proved superior to cyclic ones because cyclic strategies aren’t suited for graphs containing long edges. In partitioning-based trajectories, each robot behaves optimally inside each subgraph by running a traveling salesman problem (TSP) tour on it.
Conducting simulated and real-world experiments
Using these methods, the authors ran simulation and real-world experiments to compare actual results against the estimates. Below are six graphs showing strikingly close parallels between the simulated (blue dotted line) and actual (solid red line) experiments.
Tests using a larger area and smaller robot team
Additional tests with a smaller group of mobile robots were performed in a huge indoor area at the University of Coimbra. Each trial was repeated three times, and the figure below presents the average results.
Because smaller teams were used in these experiments, a slightly larger gap appears between the estimated data and practical results.
“This is likely to be caused by the fact that, despite having the same hardware, each robot has small peculiarities, and these differences cannot be modeled in simulations,” the authors say.
Calculating optimal performance for robot patrols
In their research, the author propose a patrolling graph, ɡ = (V, E), where each vertex vi ∈ V must be visited at least every Ω seconds by any patrolling agent r. In light of these parameters, they were able to calculate the minimum number of robots R needed in the patrol mission.
There were a few takeaways from conducting these tests. One trajectory approach might have benefits over the other (and vice versa), and the size of the robot team matters.
“The cyclic approach can result in better idle times but might result in greater overall team cost, especially in teams with many robots. Partition approaches could be desirable from a security viewpoint, use fewer resources, and require less coordination between robots. However, they tend to lead to inferior collective performance, especially in teams with few robots. As such, team size has an important impact on the patrolling task,” say the authors.
Related research on robots and robotic technology in the Computer Society Digital Library
Lori Cameron is a Senior Writer for the IEEE Computer Society and currently writes regular features for Computer magazine, Computing Edge, and the Computing Now and Magazine Roundup websites. Contact her at firstname.lastname@example.org. Follow her on LinkedIn.