Top

Autonomous Robots

Published in:

02-12-2017

Competitive target search with multi-agent teams: symmetric and asymmetric communication constraints

Authors: Michael Otte, Michael Kuhlman, Donald Sofge

Published in: Autonomous Robots | Issue 6/2018

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We study a search game in which two multi-agent teams compete to find a stationary target at an unknown location. Each team plays a mixed strategy over the set of search sweep-patterns allowed from its respective random starting locations. Assuming that communication enables cooperation we find closed-form expressions for the probability of winning the game as a function of team sizes and the existence or absence of communication within each team. Assuming the target is distributed uniformly at random, an optimal mixed strategy equalizes the expected first-visit time to all points within the search space. The benefits of communication enabled cooperation increase with team size. Simulations and experiments agree well with analytical results.

previous article Analyzing and improving multi-robot missions by using process mining

next article A sensor-based approach for fault detection and diagnosis for robotic systems

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

A discrete formulation can easily be obtained by replacing Lebesgue integrals over continuous spaces with summations over discrete sets, and reasoning about the probability of events directly instead of via probability density.

Note that in \(\mathbb {T}^D\) this is technically the push-forward extension of the Lebesgue measure that one would naturally assume.

Note that even for sensors with positive measure footprints, \({0< \mathscr {L}_{D-1}(B_r) < \infty }\) (e.g., a \(D\)-ball instead of a \((D\!-\!1)\)-ball) nearly all space is searched as the forward boundary of a sensor volume sweeps over it (in contrast to the space that is searched instantaneously at startup due to being within some agent’s sensor volume).

This prevents “cheating” where an agent that continuously rotates through an uncountably infinite number of points is able to use its zero-measure sweep sensor as if it were a volumetric sensor of non-zero-measure (the measure of a countably infinite union of sweep footprints is still 0).

This formulation is chosen because we are interested in scenarios where communication provides a significant coordination advantage. The topological constraints of \(\mathbb {S}^1\) significantly penalize an in-game redistribution from an initial i.i.d. space to an even spacing (that would otherwise be expected to facilitate maximum coordinated search). Although we do not explore it in this paper, an alternative game formulation in \({X= \mathbb {S}^1}\) would be to have all teams draw their start locations from \(\mathcal {D}_{X,\mathrm {fan}}\), regardless of their ability to communicate. In such a case, teams with communication can coordinate by having all members search in the directions expected to be most advantageous given their start locations.

To guarantee that this number is finite, we require that the sensor footprint contains some convex subset of space. In other words, degenerate sensors of measure zero or fractal-like geometry might produce an infinite number of different sweep rates.

That is, using the fact that \(G\) winning a game with n communicating agents versus m non-communicating adversaries is equivalent to \(G\) winning each of the m independent sub-games involving each different adversary (and vice versa). This is how the results from Sect. 4.1 were extended in Sects. 4.2 and 4.3.

In other words, the scenario we consider is provably worse than a worst-case scenario. Thus, the bounds we derive are outside bounds on a worst-case scenario; and as a result, they are also outside bounds on the actual scenario. Note that we choose to use the worse than worst-case scenario because it is straightforward to analyze (unlike the worst-case scenario and the actual scenario).

Beard, R. W., & McLain, T. W. (2003). Multiple uav cooperative search under collision avoidance and limited range communication constraints. In Proceedings of 42nd IEEE conference on decision and control, 2003, Vol. 1, pp. 25–30

Bertuccelli, L. F., & How, J. P. (2005). Robust UAV search for environments with imprecise probability maps. In 44th IEEE conference on decision and control, 2005 and 2005 European control conference. CDC-ECC ’05, pp. 5680–5685, https://doi.org/10.1109/CDC.2005.1583068

Bhattacharya, S., Khanafer, A., & Başar, T. (2016). A double-sided jamming game with resource constraints. Springer International Publishing, pp. 209–227

Chandler, P., & Pachter, M. (2001). Hierarchical control for autonomous teams. In Proceedings of the AIAA guidance, navigation, and control conference, pp. 632–642

Choset, H., & Pignon, P. (1998). Coverage path planning: The boustrophedon cellular decomposition. In Field and service robotics (pp. 203–209). Springer

Chung, T. H., Hollinger, G. A., & Isler, V. (2011). Search and pursuit-evasion in mobile robotics. Autonomous Robots, 31(4), 299–316.CrossRef

Demaine, E. D., Fekete, S. P., & Gal, S. (2006). Online searching with turn cost. Theoretical Computer Science, 361(2), 342–355.MathSciNetCrossRefMATH

Dias, M. B. (2004). Traderbots: A new paradigm for robust and efficient multirobot coordination in dynamic environments. PhD thesis, Carnegie Mellon University Pittsburgh

Dias, M. B., Zlot, R., Kalra, N., & Stentz, A. (2006). Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94(7), 1257–1270.CrossRef

Feinerman, O., Korman, A., Lotker, Z., Sereni, J. S. (2012). Collaborative search on the plane without communication. In Proceedings of the 2012 ACM symposium on principles of distributed computing, PODC ’12 (pp. 77–86). ACM, New York https://doi.org/10.1145/2332432.2332444,

Flint, M., Polycarpou, M., & Fernandez-Gaucherand, E. (2002). Cooperative control for multiple autonomous uav’s searching for targets. In Proceedings of the 41st IEEE Conference on Decision and Control, Vol. 3, pp. 2823–2828

Forsmo, E. J., Grotli, E. I., Fossen, T. I., & Johansen, T. A. (2013). Optimal search mission with unmanned aerial vehicles using mixed integer linear programming. In International conference on unmanned aircraft systems (ICUAS), pp. 253–259, https://doi.org/10.1109/ICUAS.2013.6564697

Gerkey, B. P., Thrun, S., & Gordon, G. (2005). Parallel stochastic hill-climbing with small teams. In Multi-robot systems. From swarms to intelligent automata Volume III (pp. 65–77). Springer

Hollinger, G. A., Yerramalli, S., Singh, S., Mitra, U., & Sukhatme, G. S. (2015). Distributed data fusion for multirobot search. IEEE Transactions on Robotics, 31(1), 55–66.CrossRef

Hopcroft, J. E., & Karp, R. M. (1971). A n5/2 algorithm for maximum matchings in bipartite. In IEEE 12th annual symposium on switching and automata theory, pp. 122–125

Hu, J., Xie, L., Lum, K. Y., & Xu, J. (2013). Multiagent information fusion and cooperative control in target search. IEEE Transactions on Control Systems Technology, 21(4), 1223–1235. https://doi.org/10.1109/TCST.2012.2198650.CrossRef

Huang, A. S., Olson, E., & Moore, D. C. (2010). Lcm: Lightweight communications and marshalling. In IEEE/RSJ international conference on, intelligent robots and systems (IROS), pp. 4057–4062

Huang, H., Ding, J., Zhang, W., & Tomlin, C. J. (2015). Automation-assisted capture-the-flag: A differential game approach. IEEE Transactions on Control Systems Technology, 23(3), 1014–1028.CrossRef

Kim, M. H., Baik, H., & Lee, S. (2013). Response threshold model based uav search planning and task allocation. Journal of Intelligent & Robotic Systems, 75(3), 625–640. https://doi.org/10.1007/s10846-013-9887-6.

Koopman, B. (1956). The theory of search. II Target detection. Operations Research, 4(5), 503–531.MathSciNetCrossRef

Kwak, D. J., & Kim, H. J. (2014). Policy improvements for probabilistic pursuit-evasion game. Journal of Intelligent & Robotic Systems, 74(3–4), 709–724. https://doi.org/10.1007/s10846-013-9857-z.CrossRef

Lynen, S., Achtelik, M. W., Weiss, S., Chli, M., Siegwart, R. (2013). A robust and modular multi-sensor fusion approach applied to mav navigation. In 2013 IEEE/RSJ international conference on intelligent robots and systems, pp. 3923–3929

Mangel, M. (1989). Marcel Dekker, New York

Noori, N., & Isler, V. (2013). Lion and man with visibility in monotone polygons. The International Journal of Robotics Research p 0278364913498291

Otte, M., Kuhlman, M., & Sofge, D. (2016). Competitive two team target search game with communication symmetry and asymmetry. In International workshop on the algorithmic foundations of robotics (WAFR), San Francisco, USA

Sato, H., & Royset, J. O. (2010). Path optimization for the resource-constrained searcher. Naval Research Logistics (NRL), 57(5), 422–440.MathSciNetMATH

Spieser, K., & Frazzoli, E. (2012). The cow-path game: A competitive vehicle routing problem. In IEEE 51st annual conference on decision and control (CDC), pp. 6513–6520

Spires, S. V., & Goldsmith, S. Y. (1998). Exhaustive geographic search with mobile robots along space-filling curves. In Collective robotics (pp. 1–12). Springer

Sujit, P. B., & Ghose, D. (2004). Multiple agent search of an unknown environment using game theoretical models. In Proceedings of the American control conference, 2004, Vol. 6, pp. 5564–5569

Sujit, P. B., & Ghose, D. (2009). Negotiation schemes for multi-agent cooperative search. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 223(6), 791–813.CrossRef

Sydney, N., Paley, D. A., Sofge, D. (2015). Physics-inspired motion planning for information-theoretic target detection using multiple aerial robots. Autonomous Robots pp 1–11

Trummel, K., & Weisinger, J. (1986). Technical note the complexity of the optimal searcher path problem. Operations Research, 34(2), 324–327.MathSciNetCrossRefMATH

Vidal, R., Shakernia, O., Kim, H. J., Shim, D. H., & Sastry, S. (2002). Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation. IEEE Transactions on Robotics and Automation 18(5):662–669, https://doi.org/10.1109/TRA.2002.804040

Vincent, P., & Rubin, I. (2004). A framework and analysis for cooperative search using uav swarms. In Proceedings of the 2004 ACM symposium on applied computing, SAC ’04. ACM, New York, pp. 79–86, https://doi.org/10.1145/967900.967919,

Waharte, S., & Trigoni, N. (2010). Supporting search and rescue operations with uavs. In International conference on emerging security technologies (EST), 2010, pp. 142–147

Zhu, M., Frazzoli, E. (2012). On competitive search games for multiple vehicles. In IEEE 51st annual conference on decision and control (CDC), 2012, pp. 5798–5803, https://doi.org/10.1109/CDC.2012.6426371

Title: Competitive target search with multi-agent teams: symmetric and asymmetric communication constraints
Authors: Michael Otte
Michael Kuhlman
Donald Sofge
Publication date: 02-12-2017
Publisher: Springer US
Published in: Autonomous Robots / Issue 6/2018
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI: https://doi.org/10.1007/s10514-017-9687-0

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Other articles of this Issue 6/2018

A sensor-based approach for fault detection and diagnosis for robotic systems

Design of vertebrae-inspired trunk mechanism for controlling walking behavior of semi-passive walker

BoCNF: efficient image matching with Bag of ConvNet features for scalable and robust visual place recognition

Long-term online multi-session graph-based SPLAM with memory management

Optimized vision-based robot motion planning from multiple demonstrations

Analyzing and improving multi-robot missions by using process mining