Abstract
Autonomous mobile robots are promising tools for operations in environments that are difficult to access for humans. When these environments are dynamic and non-deterministic, like in collapsed buildings, the robots must coordinate their actions and the use of resources using planning. This paper presents Planner9, a hierarchical task network (htn) planner that runs on groups of miniature mobile robots. These robots have limited computational power and memory, but are well connected through Wi-Fi. Planner9 takes advantage of this connectivity to distribute the planning over different robots. We have adapted the htn algorithm to perform parallel search using A* and to limit the number of search nodes through lifting. We show that Planner9 scales well with the number of robots, even on non-linear tasks that involve recursions in their decompositions. We show that contrary to JSHOP2, Planner9 finds optimal plans.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kumar, V., Rus, D., Singh, S.: Robot and sensor networks for first responders. IEEE Pervasive Computing 3(4), 24–33 (2004)
Stormont, D.: Autonomous rescue robot swarms for first responders. In: Proceedings of the 2005 IEEE International Conference on Computational Intelligence for Homeland Security and Personal Safety, pp. 151–157. IEEE Press, Los Alamitos (2005)
Ghallab, M., Nau, D., Traverso, P.: Automated Planning: theory and practice. Morgan Kaufmann, San Francisco (2004)
Mondada, F., Pettinaro, G.C., Guignard, A., Kwee, I., Floreano, D., Deneubourg, J.L., Nolfi, S., Gambardella, L., Dorigo, M.: SWARM-BOT: a New Distributed Robotic Concept. Autonomous Robots, special Issue on Swarm Robotics 17(2-3), 193–221 (2004)
Erol, K., Hendler, J.A., Nau, D.S.: HTN Planning: Complexity and Expressivity. In: AAAI, pp. 1123–1128. AAAI Press, Menlo Park (1994)
Obst, O., Boedecker, J.: Flexible Coordination of Multiagent Team Behavior Using HTN Planning. In: Bredenfeld, A., Jacoff, A., Noda, I., Takahashi, Y. (eds.) RoboCup 2005. LNCS (LNAI), vol. 4020, pp. 521–528. Springer, Heidelberg (2006)
Dix, J., Munoz-Avila, H., Nau, D., Zhang, L.: IMPACTing SHOP: Putting an AI planner into a multi-agent environment. Annals of Mathematics and Artificial Intelligence 37(4), 381–407 (2003)
Durfee, E.: Distributed problem solving and planning. Multiagent systems: a modern approach to distributed artificial intelligence, 121–164 (1999)
DesJardins, M., Durfee, E., Ortiz, C., Wolverton, M.: A survey of research in distributed, continual planning. AI Magazine (1999)
Dias, M., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE 94(7), 1257–1270 (2006)
Zlot, R., Stentz, A.: Market-based multirobot coordination for complex tasks. The International Journal of Robotics Research 25(1), 73–102 (2006)
Pellier, D., Fiorino, H.: A Unified Framework Based on HTN and POP Approaches for Multi-Agent Planning. In: IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pp. 285–288. IEEE Press, Los Alamitos (2007)
Hayashi, H., Tokura, S., Ozaki, F.: Towards Real-World HTN Planning Agents. Knowledge Processing and Decision Making in Agent-based Systems 170, 13–41 (2009)
Nau, D., Au, T., Ilghami, O., Kuter, U., Murdock, W., Wu, D., Yaman, F.: SHOP2: An HTN planning system. Journal of Artificial Intelligence Research 20(1), 379–404 (2003)
Davis, M., Logemann, G., Loveland, D.: A machine program for theorem-proving. Commun. ACM 5(7), 394–397 (1962)
Hart, P., Nilsson, N., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics 4, 100–107
Rao, V.N., Kumar, V.: Superlinear speedup in parallel state-space search. In: Proceedings of the Eighth Conference on Foundations of Software Technology and Theoretical Computer Science, London, UK, pp. 161–174. Springer, Heidelberg (1988)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Magnenat, S., Voelkle, M., Mondada, F. (2009). Planner9, a HTN Planner Distributed on Groups of Miniature Mobile Robots. In: Xie, M., Xiong, Y., Xiong, C., Liu, H., Hu, Z. (eds) Intelligent Robotics and Applications. ICIRA 2009. Lecture Notes in Computer Science(), vol 5928. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-10817-4_99
Download citation
DOI: https://doi.org/10.1007/978-3-642-10817-4_99
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-10816-7
Online ISBN: 978-3-642-10817-4
eBook Packages: Computer ScienceComputer Science (R0)