Email this article A Task Decomposition Using (HDec-POSMDPs) Approach for Multi-robot Exploration and Fire Searching
Abstract
In this paper, hierarchical control architecture for coordinated multi-robot systems (MRS) task decomposition is presented; based on a hybrid decentralized Partially Observable Semi-Markov Decision Processes (HDec-POSMDPs). In this architecture, robots can make their own decisions according to their locally collected data with limited communication between a robot team. In this proposed architecture, the global task is decomposed into multiple local sub-tasks using divide and conquer design, each task is described as a set of regular languages. MRS are modeled as a discrete event system and each robot is represented by a deterministic finite state automaton model. Direct Cross-Entropy (DICE) can be used for searching the space of the best frontier cells to solve the Dec-POSMDP and each sub-task is assigned to one or more robots to be executed. The proposed algorithm is implemented, tested and evaluated in the computer simulator. By using this architecture, the task execution time is minimized, the fire sources cluttered in an environment have been searched in an effective manner and the performance of MRS has been enhanced with respect to energy consumption and communication load; when they are used for exploring different environments as well as when they are used for detecting the sources of the fire and reporting about them.
Keywords
Full Text:
PDFReferences
M. Al-khawaldah, T.M. Younes, I. Al-Adwan, M. Nisirat and M. Alshamasin, “Automated Multi-Robot Search for a Stationary Target,” International Journal of Control Science and Engineering, vol. 4, no. 1, pp. 9-15, 2014.
M.G. Earl and R. D’Andrea, “A decomposition approach to multi-vehicle cooperative control,” Robotics and Autonomous Systems, vol. 55, no. 4, pp. 276-291, 2007.
J.G.M. Fu, T. Bandyopad and M H.A. Jr, “Local Voronoi Decomposition for Multi-Agent Task Allocation,” IEEE International Conference on, Robotics and Automation (ICRA), 2009
K. Hirayama, “A New Approach to Distributed Task Assignment using Lagrangian Decomposition and Distributed Constraint Satisfaction,” American Association for Artificial Intelligence (www.aaai.org), 2006.
A. Marjovi, J.G. Nunes, L. Marques and A.d. Almeida, “Multi-Robot Exploration and Fire Searching,” IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009.
T. Gunn and J. Anderson, “Effective Task Allocation for Evolving Multi-Robot Teams in Dangerous Environments,” IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT), 2013.
M. Andriesand and F. Charpillet, “Multi-robot exploration of unknown environments with identification of exploration completion and post-exploration rendez-vous using ant algorithms,” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2013.
F.F. Carvalho, R.C. Cavalcante, M.A.M. Vieira, L. Chaimowicz and M.F.M. Campos, “A multi-robot exploration approach based on distributed graph coloring,” Latin American Robotics Symposium and Competition (LARS/LARC), 2013.
A. Tsalatsanis, A. Yalcin and K.P. Valavanis, “Optimized Task Allocation in Cooperative Robot Teams,” 17th Mediterranean Conference on Control and Automation, 2009.
G. Pini, A. Brutschy, C. Pinciroli, M. Dorigo and M. Birattari, “Autonomous task partitioning in robot foraging: an approach based on cost estimation,” Adaptive Behavior, vol. 21, no. 2, pp. 118–136, 2013.
H. Choi, A.K. Whitten and J.P. How, “Decentralized Task Allocation for Heterogeneous Teams with Cooperation Constraints,” American Control Conference (ACC), 2010.
G.A. Korsah, A. Stentz and M.B. Dias, “A comprehensive taxonomy for multi-robot task allocation,” The International Journal of Robotics Research, vol. 32, no. 12, pp. 1495–1512, 2013.
B.P. Gerkey and M.J. Mataric, “A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems,” The International Journal of Robotics Research, vol. 23, no. 9, pp. 939-954, 2004.
A. Partovi and H. Lin, “Assume-guarantee Cooperative Satisfaction of Multi-agent Systems,” American Control Conference (ACC), 2014.
J. Dai and H. Lin, “Automatic synthesis of cooperative multi-agent systems,” IEEE 53rd Annual Conference on Decision and Control (CDC), 2014.
J. Dai, A. Benini, H. Lin, P. J. Antsaklis, M. J. Rutherford and K. P. Valavanis, “Learning-based Formal Synthesis of Cooperative Multi-agent Systems with an Application to Robotic Coordination,” 24th Mediterranean Conference on Control and Automation (MED), 2016.
M. Guo and D.V. Dimarogonas, “Bottom-up Motion and Task Coordination for Loosely-coupled Multi-agent Systems with Dependent Local Tasks,” IEEE International Conference on Automation Science and Engineering (CASE), 2015.
J. Elston and E.W. Frew, “Hierarchical Distributed Control for Search and Tracking by Heterogeneous Aerial Robot Networks,” IEEE International Conference on Robotics and Automation, 2008.
J. Tumova and D.V. Dimarogonas, “A Receding Horizon Approach to Multi-Agent Planning from Local LTL Specifications,” American Control Conference (ACC), 2014.
P. Schillinger, M. Bürger and D.V. Dimarogonas, “Decomposition of Finite LTL Specifications for Efficient Multi-Agent Planning,” 13th International Symposium on Distributed Autonomous Robotic Systems, Cite this publication, 2016.
M. Karimadini and H. Lin, “Guaranteed global performance through local coordinations,” Elsevier, Automatica, vol. 47, pp 890-898, 2011.
X. Dai, L. Jiang and Y. Zhao, “Cooperative exploration based on supervisory control of multi-robot systems,” Springer, Applied Intelligence, vol. 45, no. 1, pp. 18–29, 2016.
S. Omidshafiei, A.A. Mohammadi, C. Amato, S. Liu, J.P. How and J. Vian, “Decentralized control of multi-robot partially observable Markov decision processes using belief space macro-actions,” The International Journal of Robotics Research, vol. 36, no. 2, pp. 231–258. 2017.
Y. Kantaros and M.M. Zavlanos, “Distributed Intermittent Connectivity Control of Mobile Robot Networks,” IEEE Transactions on Automatic Control, vol. 62, no. 7, pp. 3109- 3121, 2016.
M. Liu, K. Sivakumar, S. Omidshafiei, C. Amato and J. P. How, “Learning for Multi-robot Cooperation in Partially Observable Stochastic Environments with Macro-actions,” IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2017.
V. Spirin and S. Cameron, “Rendezvous Through Obstacles in Multi-Agent Exploration,” IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), 2014.
J. Banfi, A.Q. Li, I. Rekleitis, F. Amigoni and N. Basilico, “Strategies for coordinated multirobot exploration with recurrent connectivity constraints,” Springer, Autonomous Robots, vol. 42, no. 4, pp. 875–894,2017.
J. Faigl, M.K and L. Preucil, “Goal Assignment using Distance Cost in Multi-Robot Exploration,” IEEE International Conference on Intelligent Robots and Systems, 2012.
A. Pal, R. Tiwari and A. Shukla, “Coordinated Multi-Robot Exploration under Connectivity Constraints,” Journal of Information Science and Engineering, vol. 29, no. 4, pp. 711-727, 2013.
J.d. Hoog, S. Cameron and A. Visser, “Role-Based Autonomous Multi-Robot Exploration,” Computation World: Future Computing, Service Computation, Cognitive, Adaptive, Content, Patterns, pp. 482-487, 2009.
A. Pal, R. Tiwari and A. Shukla, “Multi-Robot Exploration in Wireless Environments,” Cognitive Computation Springer Science+Business Media, vol. 4, pp. 526–542, 2012.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.