Space D*: Um Algoritmo para Path Planning Multi-Robôs
Resumo
Este trabalho descreve um novo método de path planning para múltiplos robôs em ambientes desconhecidos. O método, chamado Space D*, é baseado em dois algoritmos: o D*, que é um algoritmo de busca em grafos incremental, e o algoritmo de Colonização do Espaço, utilizado previamente para a simulação do comportamento de multidões. A maior contribuição do método proposto é o enfoque sobre a geração de caminhos por ambientes espaçosos, visando facilitar o controle dos robôs, e, dessa forma, apresentando-se de forma viável para a utilização em ambientes reais. Os resultados obtidos validam a abordagem e mostram a vantagem em relação ao método D*.Referências
Bicho, A. L. (2009). Da modelagem de plantas à dinâmica de multidões: um modelo de animação comportamental bio-inspirado. Doutorado em engenharia elétrica, Universidade Estadual de Campinas - UNICAMP.
Chen, J. and Li, L.-R. (2005). Path planning protocol for collaborative multi-robot systems. In Proceedings 2005 IEEE International Symposium on Computational Intelligence in Robotics and Automation, pages 721–726, Espoo, Finland.
Choset, H. and Burdick, J. W. (1994). Sensor-based planning and nonsmooth analysis. In ICRA, pages 3034–3041.
Clark, C. M., Rock, S. M., and Latombe, J.-C. (2003). Dynamic networks for motion planning in multi-robot space systems. In In Intl. Symp. of Artificial Intelligence, Robotics and Automation in Space.
Ferguson, D. and Stentz, A. T. (2005). Field d*: An interpolation-based path planner and replanner. In Proceedings of the International Symposium on Robotics Research (ISRR).
Gerkey, B. P., Vaughan, R. T., and Howard, A. (2003). The player/stage project: Tools for multi-robot and distributed sensor systems. In In Proceedings of the 11th International Conference on Advanced Robotics, pages 317–323.
Jung, J. H., Park, S., and Kim, S.-L. (2010). Multi-robot path finding with wireless multihop communications. Comm. Mag., 48:126–132.
Koenig, S. and Likhachev, M. (2002). Improved fast replanning for robot navigation in unknown terrain. In Robotics and Automation, 2002. Proceedings. ICRA ’02. IEEE International Conference on, volume 1, pages 968 – 975 vol.1.
Latombe, J.-C. (1991). Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA, USA.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press, Cambridge, U.K. Also available at [link].
Likhachev, M., Ferguson, D. I., Gordon, G. J., Stentz, A., and Thrun, S. (2005). Anytime dynamic a*: An anytime, replanning algorithm. In Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005), June 5-10 2005, Monterey, California, USA, pages 262–271. AAAI.
López de Màntaras, R., Amat, J., Esteva, F., López, M., and Sierra, C. (1997). Generation of unknown environment maps by cooperative low-cost robots. In Proceedings of the first international conference on Autonomous agents, AGENTS ’97, pages 164–169, New York, NY, USA. ACM.
Okada, T., Beuran, R., Nakata, J., Tan, Y., and Shinoda, Y. (2007). Collaborative motion planning of autonomous robots. In Proceedings of the 2007 International Conference on Collaborative Computing: Networking, Applications and Worksharing, pages 328–335, Washington, DC, USA. IEEE Computer Society.
Pallottino, L., Scordio, V. G., Frazzoli, E., and Bicchi, A. (2007). Decentralized cooperative policy for conflict resolution in multi-vehicle systems. IEEE Trans. on Robotics, 23(6):1170–1183.
Pereira, G. A. S., Das, A. K., Kumar, V., and Campos, M. F. M. (2003). Decentralized motion planning for multiple robots subject to sensing and communication constraints. In in Proceedings of the Second MultiRobot Systems Workshop, pages 267–278. Kluwer Academic Press.
Rekleitis, I. M., Dudek, G., and Milios, E. E. (1997). Multi-robot exploration of an unknown environment, efficiently reducing the odometry error. In Proceedings of the Fifteenth international joint conference on Artifical intelligence - Volume 2, pages 1340–1345, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
Runions, A., Fuhrer, M., Lane, B., Federl, P., Rolland-Lagan, A.-G., and Prusinkiewicz, P. (2005). Modeling and visualization of leaf venation patterns. ACM Trans. Graph., 24(3):702–711.
Stentz, A. T. (1995). The focussed d* algorithm for real-time replanning. In Proceedings of the International Joint Conference on Artificial Intelligence.
van den Berg, J., Snoeyink, J., Lin, M., and Manocha, D. (2009). Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In Proceedings of Robotics: Science and Systems, Seattle, USA.
van den Berg, J. P., Ferguson, D., and Kuffner, J. (2006). Anytime path planning and replanning in dynamic environments. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation, ICRA 2006, May 15-19, 2006, Orlando, Florida, USA, pages 2366–2371.
Chen, J. and Li, L.-R. (2005). Path planning protocol for collaborative multi-robot systems. In Proceedings 2005 IEEE International Symposium on Computational Intelligence in Robotics and Automation, pages 721–726, Espoo, Finland.
Choset, H. and Burdick, J. W. (1994). Sensor-based planning and nonsmooth analysis. In ICRA, pages 3034–3041.
Clark, C. M., Rock, S. M., and Latombe, J.-C. (2003). Dynamic networks for motion planning in multi-robot space systems. In In Intl. Symp. of Artificial Intelligence, Robotics and Automation in Space.
Ferguson, D. and Stentz, A. T. (2005). Field d*: An interpolation-based path planner and replanner. In Proceedings of the International Symposium on Robotics Research (ISRR).
Gerkey, B. P., Vaughan, R. T., and Howard, A. (2003). The player/stage project: Tools for multi-robot and distributed sensor systems. In In Proceedings of the 11th International Conference on Advanced Robotics, pages 317–323.
Jung, J. H., Park, S., and Kim, S.-L. (2010). Multi-robot path finding with wireless multihop communications. Comm. Mag., 48:126–132.
Koenig, S. and Likhachev, M. (2002). Improved fast replanning for robot navigation in unknown terrain. In Robotics and Automation, 2002. Proceedings. ICRA ’02. IEEE International Conference on, volume 1, pages 968 – 975 vol.1.
Latombe, J.-C. (1991). Robot Motion Planning. Kluwer Academic Publishers, Norwell, MA, USA.
LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press, Cambridge, U.K. Also available at [link].
Likhachev, M., Ferguson, D. I., Gordon, G. J., Stentz, A., and Thrun, S. (2005). Anytime dynamic a*: An anytime, replanning algorithm. In Proceedings of the Fifteenth International Conference on Automated Planning and Scheduling (ICAPS 2005), June 5-10 2005, Monterey, California, USA, pages 262–271. AAAI.
López de Màntaras, R., Amat, J., Esteva, F., López, M., and Sierra, C. (1997). Generation of unknown environment maps by cooperative low-cost robots. In Proceedings of the first international conference on Autonomous agents, AGENTS ’97, pages 164–169, New York, NY, USA. ACM.
Okada, T., Beuran, R., Nakata, J., Tan, Y., and Shinoda, Y. (2007). Collaborative motion planning of autonomous robots. In Proceedings of the 2007 International Conference on Collaborative Computing: Networking, Applications and Worksharing, pages 328–335, Washington, DC, USA. IEEE Computer Society.
Pallottino, L., Scordio, V. G., Frazzoli, E., and Bicchi, A. (2007). Decentralized cooperative policy for conflict resolution in multi-vehicle systems. IEEE Trans. on Robotics, 23(6):1170–1183.
Pereira, G. A. S., Das, A. K., Kumar, V., and Campos, M. F. M. (2003). Decentralized motion planning for multiple robots subject to sensing and communication constraints. In in Proceedings of the Second MultiRobot Systems Workshop, pages 267–278. Kluwer Academic Press.
Rekleitis, I. M., Dudek, G., and Milios, E. E. (1997). Multi-robot exploration of an unknown environment, efficiently reducing the odometry error. In Proceedings of the Fifteenth international joint conference on Artifical intelligence - Volume 2, pages 1340–1345, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
Runions, A., Fuhrer, M., Lane, B., Federl, P., Rolland-Lagan, A.-G., and Prusinkiewicz, P. (2005). Modeling and visualization of leaf venation patterns. ACM Trans. Graph., 24(3):702–711.
Stentz, A. T. (1995). The focussed d* algorithm for real-time replanning. In Proceedings of the International Joint Conference on Artificial Intelligence.
van den Berg, J., Snoeyink, J., Lin, M., and Manocha, D. (2009). Centralized path planning for multiple robots: Optimal decoupling into sequential plans. In Proceedings of Robotics: Science and Systems, Seattle, USA.
van den Berg, J. P., Ferguson, D., and Kuffner, J. (2006). Anytime path planning and replanning in dynamic environments. In Proceedings of the 2006 IEEE International Conference on Robotics and Automation, ICRA 2006, May 15-19, 2006, Orlando, Florida, USA, pages 2366–2371.
Publicado
19/07/2011
Como Citar
MAFFEI, Renan; BOTELHO, Silvia; SILVEIRA, Luan; DREWS JR., Paulo; DUARTE FILHO, Nelson; BICHO, Alessandro; ALMEIDA, Felipe; LONGARAY, Matheus.
Space D*: Um Algoritmo para Path Planning Multi-Robôs. In: ENCONTRO NACIONAL DE INTELIGÊNCIA ARTIFICIAL E COMPUTACIONAL (ENIAC), 8. , 2011, Natal/RN.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2011
.
p. 607-618.
ISSN 2763-9061.
