Abstract
In this paper we present a new concept of robot-dependent reachability map (RDReachMap) for mobile platforms. In heterogeneous multi-robot systems, the reachability limit of robots motion and actuation must be considered when assigning tasks to them. We created an algorithm that generates those reachability maps, separating regions that can be covered by a robot from the unreachable ones, using morphological operations. Our method is dependent on the robot position, and is parameterized with the robot’s size and actuation radius. For this purpose we introduce a new technique, the partial morphological closing operation. The algorithm was tested both in simulated and real environment maps. We also present a common problem of multi robot routing, which we solve with a planner that uses our reachability maps in order to generate valid plans. We contribute a heuristic that generates paths for two robots using the reachability concept.
This work is financed by the ERDF European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness), by National Funds through the FCT Fundao para a Cincia e a Tecnologia (Portuguese Foundation for Science and Technology) within project FCOMP-01-0124-FEDER-037281, and under Carnegie Mellon-Portugal Program grant SFRH/BD/52158/2013.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Bektas, T.: The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3), 209–219 (2006)
Bruce, J., Veloso, M.: Real-time randomized path planning for robot navigation. In: IEEE/RSJ International Conference on Intelligent Robots and Systems, 2002, vol. 3, pp. 2383–2388. IEEE (2002)
Burgard, W., Moors, M., Stachniss, C., Schneider, F.: Coordinated multi-robot exploration. In: IEEE Transactions on Robotics (2005)
Coltin, B., Liemhetcharat, S., Meriçli, C., Tay, J., Veloso, M.: Multi-humanoid world modeling in standard platform robot soccer. In: 2010 10th IEEE-RAS International Conference on Humanoid Robots (Humanoids), pp. 424–429. IEEE (2010)
Coltin, B., Veloso, M.: Scheduling for transfers in pickup and delivery problems with very large neighborhood search. In: Twenty-Eighth AAAI Conference on Artificial Intelligence (2014)
Dias, M.B., Zlot, R., Kalra, N., Stentz, A.: Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE 94(7), 1257–1270 (2006)
Dorigo, M., et al.: Swarmanoid: A novel concept for the study of heterogeneous robotic swarms. IEEE Robotics and Automation Magazine 20(4), 60–71 (2013)
Fabrizi, E., Saffiotti, A.: Extracting topology-based maps from gridmaps. In: Proceedings of the IEEE International Conference on Robotics and Automation, ICRA2000, vol. 3, pp. 2972–2978. IEEE (2000)
Grana, C., Borghesani, D., Cucchiara, R.: Fast block based connected components labeling. In: 2009 16th IEEE International Conference on Image Processing (ICIP), pp. 4061–4064. IEEE (2009)
Grisetti, G., Stachniss, C., Burgard, W.: Improved techniques for grid mapping with rao-blackwellized particle filters. IEEE Transactions on Robotics 23(1), 34–46 (2007)
Howard, A.: Multi-robot mapping using manifold representations. In: Proceedings of the 2004 IEEE International Conference on Robotics and Automation, ICRA 2004, vol. 4, pp. 4198–4203. IEEE (2004)
Howard, A., Parker, L., Sukhatme, G.: Experiments with a large heterogeneous mobile robot team: Exploration, mapping, deployment and detection. The International Journal of Robotics Research 25(5–6), 431–447 (2006)
LaValle, S.M.: Planning algorithms. Cambridge University Press (2006)
Lu, D.V., Smart, W.D.: Towards more efficient navigation for robots and humans. In: 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1707–1713. IEEE (2013)
Luo, C., Espinosa, A., Pranantha, D., De Gloria, A.: Multi-robot search and rescue team. In: 2011 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR) (2011)
Pandey, A.K., Alami, R.: Mightability maps: a perceptual level decisional framework for co-operative and competitive human-robot interaction. In: 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5842–5848. IEEE (2010)
Pereira, T., Moreira, A.P., Veloso, M.: Coordination for multi-robot exploration using topological maps. In: CONTROLO2014–Proceedings of the 11th Portuguese Conference on Automatic Control, pp. 515–524. Springer (2015)
Soille, P.: Morphological image analysis: principles and applications. Springer-Verlag, New York (2003)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Pereira, T., Veloso, M., Moreira, A. (2016). Multi-robot Planning Using Robot-Dependent Reachability Maps. In: Reis, L., Moreira, A., Lima, P., Montano, L., Muñoz-Martinez, V. (eds) Robot 2015: Second Iberian Robotics Conference. Advances in Intelligent Systems and Computing, vol 417. Springer, Cham. https://doi.org/10.1007/978-3-319-27146-0_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-27146-0_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-27145-3
Online ISBN: 978-3-319-27146-0
eBook Packages: Computer ScienceComputer Science (R0)