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
Published 05/15/2018
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.
“We present two computational methods to estimate the outcome of different near-optimal approaches to approximate and serve as an upper bound for the performance of any generic multirobot patrol (MRP) strategy. These methods make use of graph theory concepts and do not require running an entire patrol mission, thus enabling us to foresee the result beforehand and understand which approach best suits a given generic environment,” say David Portugal of Ingeniarius, Ltd. in Portugal and Rui P. Rocha of the University of Coimbra, Portugal, in their article “Performance Estimation and Dimensioning of Team Size for Multirobot Patrol.” (login may be required for full text)
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.
For cyclic trajectories, the researchers used TSP_GA, which was developed by Joseph Kirk, a contributor to MathWorks.com. The method quickly obtained the optimal cyclic trajectory for every graph they tested.
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.
Environments used in the simulation (a, b, c) and real-world (d) experiments with corresponding topological maps.
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.
Results in environments A, B, and C for “worst idleness (WI) theoretical estimates versus performance evaluation in simulation 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.
HTSP estimates versus real-world results in ɡd.
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.
Lessons learned
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 l.cameron@computer.org. Follow her on LinkedIn.
