Skip to main content
Top
Published in: Autonomous Robots 4/2018

22-07-2017

Decentralized multi-robot belief space planning in unknown environments via identification and efficient re-evaluation of impacted paths

Authors: Tal Regev, Vadim Indelman

Published in: Autonomous Robots | Issue 4/2018

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper we develop a new approach for decentralized multi-robot belief space planning in high-dimensional state spaces while operating in unknown environments. State of the art approaches often address related problems within a sampling based motion planning paradigm, where robots generate candidate paths and are to choose the best paths according to a given objective function. As exhaustive evaluation of all candidate path combinations from different robots is computationally intractable, a commonly used (sub-optimal) framework is for each robot, at each time epoch, to evaluate its own candidate paths while only considering the best paths announced by other robots. Yet, even this approach can become computationally expensive, especially for high-dimensional state spaces and for numerous candidate paths that need to be evaluated. In particular, upon an update in the announced path from one of the robots, state of the art approaches re-evaluate belief evolution for all candidate paths and do so from scratch. In this work we develop a framework to identify and efficiently update only those paths that are actually impacted as a result of an update in the announced path. Our approach is based on appropriately propagating belief evolution along impacted paths while employing insights from factor graph and incremental smoothing for efficient inference that is required for evaluating the utility of each impacted path. We demonstrate our approach in a synthetic simulation.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literature
go back to reference Agha-Mohammadi, A.-A., Chakravorty, S., & Amato, N. M. (2014). Firm: Sampling-based feedback motion planning under motion uncertainty and imperfect measurements. The International Journal of Robotics Research, 33, 268–304.CrossRef Agha-Mohammadi, A.-A., Chakravorty, S., & Amato, N. M. (2014). Firm: Sampling-based feedback motion planning under motion uncertainty and imperfect measurements. The International Journal of Robotics Research, 33, 268–304.CrossRef
go back to reference Agha-mohammadi, A. A., Agarwal, S., Chakravorty, S., & Amato, N. M. (2015). Simultaneous localization and planning for physical mobile robots via enabling dynamic replanning in belief space. arXiv:1510.07380. Agha-mohammadi, A. A., Agarwal, S., Chakravorty, S., & Amato, N. M. (2015). Simultaneous localization and planning for physical mobile robots via enabling dynamic replanning in belief space. arXiv:​1510.​07380.
go back to reference Agha-Mohammadi, A. A., Agarwal, S., Mahadevan, A., Chakravorty, S., Tomkins, D., Denny, J., et al. (2014). Robust online belief space planning in changing environments: Application to physical mobile robots. In IEEE International Conference on Robotics and Automation (ICRA) (pp. 149–156). Agha-Mohammadi, A. A., Agarwal, S., Mahadevan, A., Chakravorty, S., Tomkins, D., Denny, J., et al. (2014). Robust online belief space planning in changing environments: Application to physical mobile robots. In IEEE International Conference on Robotics and Automation (ICRA) (pp. 149–156).
go back to reference Amato, C., Konidaris, G., Anders, A., Cruz, G., How, J. P., & Kaelbling, L. P. (2016). Policy search for multi-robot coordination under uncertainty. The International Journal of Robotics Research, 35(14), 1760–1778.CrossRef Amato, C., Konidaris, G., Anders, A., Cruz, G., How, J. P., & Kaelbling, L. P. (2016). Policy search for multi-robot coordination under uncertainty. The International Journal of Robotics Research, 35(14), 1760–1778.CrossRef
go back to reference Atanasov, N., Le Ny, J., Daniilidis, K., Pappas, G. J. (2015). Decentralized active information acquisition: Theory and application to multi-robot slam. In IEEE International Conference on Robotics and Automation (ICRA). Atanasov, N., Le Ny, J., Daniilidis, K., Pappas, G. J. (2015). Decentralized active information acquisition: Theory and application to multi-robot slam. In IEEE International Conference on Robotics and Automation (ICRA).
go back to reference Bernstein, D., Givan, R., Immerman, N., & Zilberstein, S. (2002). The complexity of decentralized control of markov decision processes. Mathematics of operations research, 27(4), 819–840.MathSciNetCrossRefMATH Bernstein, D., Givan, R., Immerman, N., & Zilberstein, S. (2002). The complexity of decentralized control of markov decision processes. Mathematics of operations research, 27(4), 819–840.MathSciNetCrossRefMATH
go back to reference Bry, A., Roy, N. (2011). Rapidly-exploring random belief trees for motion planning under uncertainty. In IEEE International Conference on Robotics and Automation (ICRA) (pp. 723–730). Bry, A., Roy, N. (2011). Rapidly-exploring random belief trees for motion planning under uncertainty. In IEEE International Conference on Robotics and Automation (ICRA) (pp. 723–730).
go back to reference Chaves, S. M., Kim, A., Eustice, R. M. (2014). Opportunistic sampling-based planning for active visual slam. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 3073–3080). IEEE. Chaves, S. M., Kim, A., Eustice, R. M. (2014). Opportunistic sampling-based planning for active visual slam. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (pp. 3073–3080). IEEE.
go back to reference Cunningham, A., Indelman, V., Dellaert, F. (2013). DDF-SAM 2.0: Consistent distributed smoothing and mapping. In IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany. Cunningham, A., Indelman, V., Dellaert, F. (2013). DDF-SAM 2.0: Consistent distributed smoothing and mapping. In IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany.
go back to reference Dellaert, F. (2012). Factor graphs and GTSAM: A hands-on introduction. Technical Report GT-RIM-CP&R-2012-002, Georgia Institute of Technology. Dellaert, F. (2012). Factor graphs and GTSAM: A hands-on introduction. Technical Report GT-RIM-CP&R-2012-002, Georgia Institute of Technology.
go back to reference Farhi, E. I., Indelman, V. (2017) Towards efficient inference update through planning via jip - joint inference and belief space planning. In IEEE International Conference on Robotics and Automation (ICRA). Farhi, E. I., Indelman, V. (2017) Towards efficient inference update through planning via jip - joint inference and belief space planning. In IEEE International Conference on Robotics and Automation (ICRA).
go back to reference Golub, G. H., & Plemmons, R. J. (1980). Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition. Linear Algebra and Its Applications, 34, 3–28.MathSciNetCrossRefMATH Golub, G. H., & Plemmons, R. J. (1980). Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition. Linear Algebra and Its Applications, 34, 3–28.MathSciNetCrossRefMATH
go back to reference Hollinger, G. A., & Sukhatme, G. S. (2014). Sampling-based robotic information gathering algorithms. The International Journal of Robotics Research, 33, 1271–1287.CrossRef Hollinger, G. A., & Sukhatme, G. S. (2014). Sampling-based robotic information gathering algorithms. The International Journal of Robotics Research, 33, 1271–1287.CrossRef
go back to reference Indelman, V. (2015a). Towards cooperative multi-robot belief space planning in unknown environments. In Proceedings of the International Symposium of Robotics Research (ISRR). Indelman, V. (2015a). Towards cooperative multi-robot belief space planning in unknown environments. In Proceedings of the International Symposium of Robotics Research (ISRR).
go back to reference Indelman, V. (2015b) Towards multi-robot active collaborative state estimation via belief space planning. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Indelman, V. (2015b) Towards multi-robot active collaborative state estimation via belief space planning. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
go back to reference Indelman, V., Carlone, L., & Dellaert, F. (2015). Planning in the continuous domain: a generalized belief space approach for autonomous navigation in unknown environments. The International Journal of Robotics Research, 34(7), 849–882.CrossRef Indelman, V., Carlone, L., & Dellaert, F. (2015). Planning in the continuous domain: a generalized belief space approach for autonomous navigation in unknown environments. The International Journal of Robotics Research, 34(7), 849–882.CrossRef
go back to reference Indelman, V., Gurfil, P., Rivlin, E., & Rotstein, H. (2012). Graph-based distributed cooperative navigation for a general multi-robot measurement model. The International Journal of Robotics Research, 31(9), 1057–1080.CrossRef Indelman, V., Gurfil, P., Rivlin, E., & Rotstein, H. (2012). Graph-based distributed cooperative navigation for a general multi-robot measurement model. The International Journal of Robotics Research, 31(9), 1057–1080.CrossRef
go back to reference Indelman, V., Wiliams, S., Kaess, M., & Dellaert, F. (2013). Information fusion in navigation systems via factor graph based incremental smoothing. Robotics and Autonomous Systems, 61(8), 721–738.CrossRef Indelman, V., Wiliams, S., Kaess, M., & Dellaert, F. (2013). Information fusion in navigation systems via factor graph based incremental smoothing. Robotics and Autonomous Systems, 61(8), 721–738.CrossRef
go back to reference Kaess, M., Johannsson, H., Roberts, R., Ila, V., Leonard, J., & Dellaert, F. (2012). iSAM2: Incremental smoothing and mapping using the Bayes tree. The International Journal of Robotics Research, 31, 217–236.CrossRef Kaess, M., Johannsson, H., Roberts, R., Ila, V., Leonard, J., & Dellaert, F. (2012). iSAM2: Incremental smoothing and mapping using the Bayes tree. The International Journal of Robotics Research, 31, 217–236.CrossRef
go back to reference Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7), 846–894.CrossRefMATH Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7), 846–894.CrossRefMATH
go back to reference Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566–580.CrossRef Kavraki, L. E., Svestka, P., Latombe, J.-C., & Overmars, M. H. (1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4), 566–580.CrossRef
go back to reference Kopitkov, D., Indelman, V. (2016). Computationally efficient decision making under uncertainty in high-dimensional state spaces. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Kopitkov, D., Indelman, V. (2016). Computationally efficient decision making under uncertainty in high-dimensional state spaces. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
go back to reference Kopitkov, D., & Indelman, V. (2017). Computationally efficient belief space planning via augmented matrix determinant lemma and re-use of calculations. IEEE Robotics and Automation Letters (RA-L), 2(2), 506–513.CrossRef Kopitkov, D., & Indelman, V. (2017). Computationally efficient belief space planning via augmented matrix determinant lemma and re-use of calculations. IEEE Robotics and Automation Letters (RA-L), 2(2), 506–513.CrossRef
go back to reference Kurniawati, H., Hsu, D., Lee, W. S. (2008). Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces. In Robotics: Science and Systems (RSS) (vol. 2008). Kurniawati, H., Hsu, D., Lee, W. S. (2008). Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces. In Robotics: Science and Systems (RSS) (vol. 2008).
go back to reference LaValle, S. M., & Kuffner, J. J. (2001). Randomized kinodynamic planning. The International Journal of Robotics Research, 20(5), 378–400.CrossRef LaValle, S. M., & Kuffner, J. J. (2001). Randomized kinodynamic planning. The International Journal of Robotics Research, 20(5), 378–400.CrossRef
go back to reference Levine, D., Luders, B., & How, J. P. (2013). Information-theoretic motion planning for constrained sensor networks. Journal of Aerospace Information Systems, 10(10), 476–496.CrossRef Levine, D., Luders, B., & How, J. P. (2013). Information-theoretic motion planning for constrained sensor networks. Journal of Aerospace Information Systems, 10(10), 476–496.CrossRef
go back to reference Olson, E., & Agarwal, P. (2013). Inference on networks of mixtures for robust robot mapping. The International Journal of Robotics Research, 32(7), 826–840.CrossRef Olson, E., & Agarwal, P. (2013). Inference on networks of mixtures for robust robot mapping. The International Journal of Robotics Research, 32(7), 826–840.CrossRef
go back to reference Papadimitriou, C., & Tsitsiklis, J. (1987). The complexity of markov decision processes. Mathematics of Operations Research, 12(3), 441–450.MathSciNetCrossRefMATH Papadimitriou, C., & Tsitsiklis, J. (1987). The complexity of markov decision processes. Mathematics of Operations Research, 12(3), 441–450.MathSciNetCrossRefMATH
go back to reference Pathak, S., Thomas, A., Feniger, A., & Indelman, V. (2016). Robust active perception via data-association aware belief space planning. arXiv:1606.05124. Pathak, S., Thomas, A., Feniger, A., & Indelman, V. (2016). Robust active perception via data-association aware belief space planning. arXiv:​1606.​05124.
go back to reference Platt, R., Tedrake, R., Kaelbling, L.P., & Lozano-Pérez, T. (2010). Belief space planning assuming maximum likelihood observations. In Robotics: Science and Systems (RSS) (pp. 587–593). Zaragoza, Spain. Platt, R., Tedrake, R., Kaelbling, L.P., & Lozano-Pérez, T. (2010). Belief space planning assuming maximum likelihood observations. In Robotics: Science and Systems (RSS) (pp. 587–593). Zaragoza, Spain.
go back to reference Prentice, S., & Roy, N. (2009). The belief roadmap: Efficient planning in belief space by factoring the covariance. The International Journal of Robotics Research, 28, 1448–1465.CrossRef Prentice, S., & Roy, N. (2009). The belief roadmap: Efficient planning in belief space by factoring the covariance. The International Journal of Robotics Research, 28, 1448–1465.CrossRef
go back to reference Regev, T., & Indelman, V. (2016). Multi-robot decentralized belief space planning in unknown environments via efficient re-evaluation of impacted paths. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). Regev, T., & Indelman, V. (2016). Multi-robot decentralized belief space planning in unknown environments via efficient re-evaluation of impacted paths. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
go back to reference Stachniss, C., Grisetti, G., & Burgard, W. (2005). Information gain-based exploration using rao-blackwellized particle filters. In Robotics: Science and Systems (RSS) (pp. 65–72). Stachniss, C., Grisetti, G., & Burgard, W. (2005). Information gain-based exploration using rao-blackwellized particle filters. In Robotics: Science and Systems (RSS) (pp. 65–72).
go back to reference Van Den Berg, J., Patil, S., & Alterovitz, R. (2012). Motion planning under uncertainty using iterative local optimization in belief space. The International Journal of Robotics Research, 31(11), 1263–1278.CrossRef Van Den Berg, J., Patil, S., & Alterovitz, R. (2012). Motion planning under uncertainty using iterative local optimization in belief space. The International Journal of Robotics Research, 31(11), 1263–1278.CrossRef
Metadata
Title
Decentralized multi-robot belief space planning in unknown environments via identification and efficient re-evaluation of impacted paths
Authors
Tal Regev
Vadim Indelman
Publication date
22-07-2017
Publisher
Springer US
Published in
Autonomous Robots / Issue 4/2018
Print ISSN: 0929-5593
Electronic ISSN: 1573-7527
DOI
https://doi.org/10.1007/s10514-017-9659-4

Other articles of this Issue 4/2018

Autonomous Robots 4/2018 Go to the issue