Planning under uncertainty faces a scalability problem when considering multi-robot teams, as the information space scales exponentially with the number of robots. To address this issue, this paper proposes to decentralize multi-robot partially observable Markov decision processes (POMDPs) while maintaining cooperation between robots by using POMDP policy auctions. Auctions provide a flexible way of coordinating individual policies modeled by POMDPs and have low communication requirements. In addition, communication models in the multi-agent POMDP literature severely mismatch with real inter-robot communication. We address this issue by exploiting a decentralized data fusion method in order to efficiently maintain a joint belief state among the robots. The paper presents two different applications: environmental monitoring with unmanned aerial vehicles (UAVs); and cooperative tracking, in which several robots have to jointly track a moving target of interest. The first one is used as a proof of concept and illustrates the proposed ideas through different simulations. The second one adds real multi-robot experiments, showcasing the flexibility and robust coordination that our techniques can provide.
BernsteinDSGivanRImmermanNZilbersteinS (2002) The complexity of decentralized control of Markov decision processes. (d) Mathematics of Operations Research27: 819–840.
2.
BourgaultFDurrant-WhyteH (2004) Communication in general decentralized filters and the coordinated search strategy. (d) In: Proceedings of the 7th International Conference on Information Fusion.
3.
BoutilierC (1996) Planning, learning and coordination in multiagent decision processes. (d) In: Proceedings of the 6th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 195–210.
4.
BurdakovODohertyPHolmbergKKvarnstromJOlsonPM (2010) Relay positioning for unmanned aerial vehicle surveillance. (d) The International Journal of Robotics Research29(8): 1069–1087.
CapitanJMerinoLCaballeroFOlleroA (2011) Decentralized delayed-state information filter (DDSIF): A new approach for cooperative decentralized tracking. (d) Robotics and Autonomous Systems59: 376–388.
7.
ChoiHLBrunetLHowJ (2009) Consensus-based decentralised auctions for robust task allocation. (d) IEEE Transactions on Robotics25: 912–926.
8.
ColeDSukkariehSGoktoganA (2006) System development and demonstration of a UAV control architecture for information gathering missions. (d) Journal of Field Robotics23(6–7): 417–440.
9.
de HoogJCameronSVisserA (2009) Role-based autonomous multi-robot exploration. (d) In: Proceedings of COMPUTATIONWORLD’09, pp. 482–487.
10.
DoshiFRoyN (2008) The permutable POMDP: fast solutions to POMDPs for preference elicitation. (d) In: Proceedings of AAMAS, volume 1, pp. 493–500.
11.
FokaATrahaniasP (2007) Real-time hierarchical POMDPs for autonomous robot navigation. (d) Robotics and Autonomous Systems55(7): 561–571.
12.
GerkeyBPMatarićMJ (2004) A formal analysis and taxonomy of task allocation in multi-robot systems. (d) The International Journal of Robotics Research23(9): 939–954.
13.
GmytrasiewiczPJDoshiP (2005) A framework for sequential planning in multi-agent settings. (d) Journal of Artificial Intelligence Research24: 49–79.
14.
HeRBachrachARoyN (2010) Efficient planning under uncertainty for a target-tracking micro-aerial vehicle. (d) In: Proceedings of ICRA, pp. 1–8.
15.
HeRBrunskillERoyN (2011) Efficient planning under uncertainty with macro-actions. (d) Journal of Artificial Intelligence Research40: 523–570.
16.
HoeyJLittleJJ (2007) Value-directed human behavior analysis from video using partially observable Markov decision processes. (d) IEEE Transactions on Pattern Analysis and Machine Intelligence29(7): 1–15.
17.
HsiaoKKaelblingLLozano-PerezT (2007) Grasping POMDPs. (d) Proceedings of ICRA, pp. 4685–4692.
18.
HsiehMACowleyAKellerJF. (2007) Adaptive teams of autonomous aerial and ground robots for situational awareness. (d) Journal of Field Robotics24: 991–1014.
19.
KaelblingLPLittmanMLCassandraAR (1998) Planning and acting in partially observable stochastic domains. (d) Artificial Intelligence101: 99–134.
20.
KokJRSpaanMTJVlassisN (2005) Non-communicative multi-robot coordination in dynamic environments. (d) Robotics and Autonomous Systems50(2–3): 99–114.
21.
KurniawatiHDuYHsuDLeeWS (2011) Motion planning under uncertainty for robotic tasks with long time horizons. (d) The International Journal of Robotics Research30(3): 308–323.
22.
KurniawatiHHsuDLeeW (2008) SARSOP: Efficient point-based POMDP planning by approximating optimally reachable belief spaces. (d) In: Proceedings of the Robotics: Science and Systems Conference. Zurich, Switzerland.
23.
LeonardNEPaleyDADavisREFratantoniDMLekienFZhangF (2010) Coordinated control of an underwater glider fleet in an adaptive ocean sampling field experiment in Monterey Bay. (d) Journal of Field Robotics27: 718–740.
24.
LiuLShellDA (2011) Multi-level partitioning and distribution of the assignment problem for large-scale multi-robot task allocation. (d) In: Proceedings of RSS.
25.
MatignonLJeanpierreLMouaddibA (2012) Coordinated multi-robot exploration under communication constraints using decentralized Markov decision processes. (d) In: Proceedings of AAAI, pp. 2017–2023.
26.
MazaICaballeroFCapitanJde DiosJMOlleroA (2011) A distributed architecture for a robotic platform with aerial sensor transportation and self-deployment capabilities. (d) Journal of Field Robotics28(3): 303–328.
27.
MerinoLCaballeroFde DiosJMFerruzJOlleroA (2006) A cooperative perception system for multiple UAVs: application to automatic detection of forest fires. (d) Journal of Field Robotics23: 165–184.
28.
MerinoLGilbertACapitanJBowdenRIllingworthJOlleroA (2012) Data fusion in ubiquitous networked robot systems for urban services. (d) Annals of Telecommunications67(7–8): 355–375.
29.
MosteoAMontanoL (2007) Comparative experiments on optimization criteria and algorithms for auction based multi-robot task allocation. (d) In: Proceedings ICRA, pp. 3345–3350.
30.
NairRTambeMMarsellaS (2003) Role allocation and reallocation in multiagent teams: towards a practical analysis. (d) In: Proceedings AAMAS, pp. 552–559.
31.
NairRTambeMRothMYokooM (2004) Communication for improving policy computation in distributed POMDPs. (d) In: Proceedings AAMAS, volume 3, pp. 1098–1105.
32.
NairRVarakanthamPTambeMYokooM (2005) Networked distributed POMDPs: a synthesis of distributed constraint optimization and POMDPs. (d) In: Proceedings AAAI, pp. 133–139.
33.
NettletonEDurrant-WhyteHSukkariehS (2003) A robust architecture for decentralised data fusion. (d) In: Proceedings of ICRA.
34.
OliehoekFASpaanMTJ (2012) Tree-based pruning for multiagent POMDPs with delayed communication. (d) In: Proceedings AAAI, pp. 1415–1421.
35.
OngSPngSWHsuDLeeWS (2009) POMDPs for robotic tasks with mixed observability. (d) In: Proceedings of RSS.
36.
PapadimitriouCHTsitsiklisJN (1987) The complexity of Markov decision processes. (d) Mathematics of Operations Research12(3): 441–450.
37.
PineauJGordonGThrunS (2006) Anytime point-based approximations for large POMDPs. (d) Journal of Artificial Intelligence Research27: 335–380.
38.
PoupartP (2005) Exploiting Structure to Efficiently Solve Large Scale Partially Observable Markov Decision Processes. (d) Ph.D. thesis, University of Toronto.
39.
PynadathDVTambeM (2002) The communicative multiagent team decision problem: analyzing teamwork theories and models. (d) Journal of Artificial Intelligence Research16: 389–423.
40.
RabinovichZGoldmanCVRosenscheinJS (2003) The complexity of multiagent systems: the price of silence. (d) In: Proceedings of AAMAS, pp. 1102–1103.
41.
RothMSimmonsRVelosoM (2005) Decentralized communication strategies for coordinated multi-agent policies. (d) In: SchultzAParkerLSchneiderF (eds.), Multi-Robot Systems: From Swarms to Intelligent Automata, volume IV. Dordrecht: Kluwer Academic Publishers, pp. 93–105.
42.
RoyNGordonGThrunS (2005) Finding approximate POMDP solutions through belief compression. (d) Journal of Artificial Intelligence Research23: 1–40.
43.
SeukenSZilbersteinS (2008) Formal models and algorithms for decentralized decision making under uncertainty. (d) Autonomous Agents and Multi-Agent Systems17(2): 190–250.
44.
ShahJAConradPRWilliamsBC (2009) Fast distributed multi-agent plan execution with dynamic task assignment and scheduling. (d) In: Proceedings ICAPS, pp. 289–296.
45.
SimmonsRKoenigS (1995) Probabilistic robot navigation in partially observable environments. (d) In: Proceedings International Joint Conference on Artificial Intelligence, volume 2, pp. 1080–1087.
46.
SleightJDurfeeEH (2012) A decision-theoretic characterization of organizational influences. (d) In: Proceedings of AAMAS, volume 1, pp. 323–330.
47.
SondikEJ (1971) The Optimal Control of Partially Observable Markov Processes. (d) Ph.D. thesis, Stanford University.
48.
SpaanMGonçalvesNSequeiraJ (2010a) Multirobot coordination by auctioning POMDPs. (d) In: Proceedings of ICRA, pp. 1446–1451.
49.
SpaanMTJOliehoekFAVlassisN (2008) Multiagent planning under uncertainty with stochastic communication delays. (d) In: Proceedings of ICAPS, pp. 338–345.
50.
SpaanMTJVeigaTSLimaPU (2010b) Active cooperative perception in network robot systems using POMDPs. (d) In: Proceedings of International Conference on Intelligent Robots and Systems, pp. 4800–4805.
51.
SpaanMTJVlassisN (2004) A point-based POMDP algorithm for robot planning. (d) In: Proceedings of the IEEE International Conference on Robotics and Automation, New Orleans, Louisiana, pp. 2399–2404.
52.
StroupeABalchT (2005) Value-based action selection for observation with robot teams using probabilistic techniques. (d) Robotics and Autonomous Systems50: 85–97.
53.
TheocharousGKaelblingLP (2003) Approximate planning in POMDPs with macro-actions. (d) In: Advances in Neural Information Processing Systems.
54.
ThrunSBurgardWFoxD (2005) Probabilistic Robotics. (d) Cambrideg, MA: MIT Press.
55.
van der SluisL (ed.) (2011) Future Generation – Smartgrid Research in the Netherlands. (d) TU Delft Library.
56.
ViguriaAMazaIOlleroA (2008) S+T: an algorithm for distributed multirobot task allocation based on services for improving robot cooperation. (d) In: Proceedings of ICRA, pp. 3163–3168.
57.
WongEMBourgaultFFurukawaT (2005) Multi-vehicle Bayesian search for multiple lost targets. (d) In: Proceedings of ICRA, pp. 3169–3174.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
