DGORL: Distributed Graph Optimization Based Relative Localization of Multi-robot Systems | SpringerLink
Skip to main content
Springer Nature Link
Log in

DGORL: Distributed Graph Optimization Based Relative Localization of Multi-robot Systems

  • Conference paper
  • First Online:
Distributed Autonomous Robotic Systems (DARS 2022)

Part of the book series: Springer Proceedings in Advanced Robotics ((SPAR,volume 28))

Included in the following conference series:

Abstract

An optimization problem is at the heart of many robotics estimating, planning, and optimum control problems. Several attempts have been made at model-based multi-robot localization, and few have formulated the multi-robot collaborative localization problem as a factor graph problem to solve through graph optimization. Here, the optimization objective is to minimize the errors of estimating the relative location estimates in a distributed manner. Our novel graph-theoretic approach to solving this problem consists of three major components; (connectivity) graph formation, expansion through the transition model, and optimization of relative poses. First, we estimate the relative pose-connectivity graph using the received signal strength between the connected robots, indicating relative ranges between them. Then, we apply a motion model to formulate graph expansion and optimize them using g\(^2\)o graph optimization as a distributed solver over dynamic networks. Finally, we theoretically analyze the algorithm and numerically validate its optimality and performance through extensive simulations. The results demonstrate the practicality of the proposed solution compared to a state-of-the-art algorithm for collaborative localization in multi-robot systems.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 22879
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
JPY 28599
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    http://github.com/herolab-uga/DGORL.

References

  1. Islam, M.J., Mo, J., Sattar, J.: Robot-to-robot relative pose estimation using humans as markers. Auton. Robot. 45(4), 579–593 (2021)

    Article  Google Scholar 

  2. Xianjia, Y., Qingqing, L., Queralta, J.P., Heikkonen, J., Westerlund, T.: Applications of UWB networks and positioning to autonomous robots and industrial systems. In: 2021 10th Mediterranean Conference on Embedded Computing (MECO), pp. 1–6. IEEE (2021)

    Google Scholar 

  3. Najafi, M., Nadealian, Z., Rahmanian, S., Ghafarinia, V.: An adaptive distributed approach for the real-time vision-based navigation system. Measurement 145, 14–21 (2019)

    Article  Google Scholar 

  4. Guo, K., Qiu, Z., Meng, W., Xie, L., Teo, R.: Ultra-wideband based cooperative relative localization algorithm and experiments for multiple unmanned aerial vehicles in GPS denied environments. Int. J. Micro Air Veh. 9(3), 169–186 (2017)

    Article  Google Scholar 

  5. Fink, J., Michael, N., Kim, S., Kumar, V.: Distributed pursuit-evasion without global localization via local fronteirs. Auton. Robot. 32(1), 81–95 (2012)

    Article  Google Scholar 

  6. Dubé, R., Gawel, A., Sommer, H., Nieto, J., Siegwart, R., Cadena, C.: An online multi-robot slam system for 3D lidars. In: 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 1004–1011. IEEE (2017)

    Google Scholar 

  7. Mangelson, J.G., Dominic, D., Eustice, R.M., Vasudevan, R.: Pairwise consistent measurement set maximization for robust multi-robot map merging. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 2916–2923. IEEE (2018)

    Google Scholar 

  8. Tian, Y., Chang, Y., Arias, F.H., Nieto-Granda, C., How, J.P., Carlone, L.: Kimera-Multi: robust, distributed, dense metric-semantic slam for multi-robot systems. IEEE Trans. Robot. 38, 2022–2038 (2022)

    Article  Google Scholar 

  9. Latif, E., Parasuraman, R.: Multi-robot synergistic localization in dynamic environments. In: ISR Europe 2022; 54th International Symposium on Robotics, pp. 1–8 (2022)

    Google Scholar 

  10. Shorinwa, O., Yu, J., Halsted, T., Koufos, A., Schwager, M.: Distributed multi-target tracking for autonomous vehicle fleets. In: IEEE International Conference on Robotics and Automation (ICRA) 2020, pp. 3495–3501 (2020)

    Google Scholar 

  11. Wai, H.-T., Yang, Z., Wang, Z., Hong, M.: Multi-agent reinforcement learning via double averaging primal-dual optimization. In: Advances in Neural Information Processing Systems, vol. 31 (2018)

    Google Scholar 

  12. Wang, W., Jadhav, N., Vohs, P., Hughes, N., Mazumder, M., Gil, S.: Active rendezvous for multi-robot pose graph optimization using sensing over Wi-Fi. In: Asfour, T., Yoshida, E., Park, J., Christensen, H., Khatib, O. (eds.) Robotics Research. ISRR 2019. Springer Proceedings in Advanced Robotics, vol. 20, pp. 832–849. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-95459-8_51

  13. Parashar, R., Parasuraman, R.: Particle filter based localization of access points using direction of arrival on mobile robots. In: IEEE 92nd Vehicular Technology Conference (VTC2020-Fall), pp. 1–6. IEEE (2020)

    Google Scholar 

  14. Latif, E., Parasuraman, R.: Online indoor localization using DOA of wireless signals. arXiv preprint arXiv:2201.05105 (2022)

  15. Luo, S., Kim, J., Parasuraman, R., Bae, J.H., Matson, E.T., Min, B.-C.: Multi-robot rendezvous based on bearing-aided hierarchical tracking of network topology. Ad Hoc Netw. 86, 131–143 (2019)

    Article  Google Scholar 

  16. Parasuraman, R., Min, B.-C.: Consensus control of distributed robots using direction of arrival of wireless signals. In: Correll, N., Schwager, M., Otte, M. (eds.) Distributed Autonomous Robotic Systems. SPAR, vol. 9, pp. 17–34. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05816-6_2

    Chapter  Google Scholar 

  17. Parasuraman, R., Oegren, P., Min, B.-C.: Kalman filter based spatial prediction of wireless connectivity for autonomous robots and connected vehicles. In: IEEE 88th Vehicular Technology Conference (VTC-fall), pp. 1–5. IEEE (2018)

    Google Scholar 

  18. Kümmerle, R., Grisetti, G., Strasdat, H., Konolige, K., Burgard, W.: g\(^2\)o: a general framework for graph optimization. In: 2011 IEEE International Conference on Robotics and Automation, pp. 3607–3613. IEEE (2011)

    Google Scholar 

  19. Wiktor, A., Rock, S.: Collaborative multi-robot localization in natural terrain*. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 4529–4535 (2020)

    Google Scholar 

  20. Huang, G., Kaess, M., Leonard, J.J.: Consistent sparsification for graph optimization. In: European Conference on Mobile Robots, pp. 150–157 (2013)

    Google Scholar 

  21. Zheng, S., et al.: Multi-robot relative positioning and orientation system based on UWB range and graph optimization. Measurement 195, 111068 (2022)

    Article  Google Scholar 

  22. Hao, N., He, F., Hou, Y., Yao, Y.: Graph-based observability analysis for mutual localization in multi-robot systems. Syst. Control Lett. 161, 105152 (2022)

    Article  MathSciNet  Google Scholar 

  23. Sahawneh, L.R., Brink, K.M.: Factor graphs-based multi-robot cooperative localization: a study of shared information influence on optimization accuracy and consistency. In: Proceedings of the 2017 International Technical Meeting of the Institute of Navigation (ION ITM 2017), Monterey, California, pp. 819–838 (2017)

    Google Scholar 

  24. Carlevaris-Bianco, N., Eustice, R.M.: Generic factor-based node marginalization and edge sparsification for pose-graph SLAM. In: 2013 IEEE International Conference on Robotics and Automation, pp. 5748–5755. IEEE (2013)

    Google Scholar 

  25. Johannsson, H., Kaess, M., Fallon, M., Leonard, J.J.: Temporally scalable visual slam using a reduced pose graph. In: 2013 IEEE International Conference on Robotics and Automation, pp. 54–61. IEEE (2013)

    Google Scholar 

  26. Bar-Shalom, Y., Li, X.R., Kirubarajan, T.: Estimation with Applications to Tracking and Navigation: Theory Algorithms and Software. Wiley, New York (2004)

    Google Scholar 

  27. Indelman, V., Nelson, E., Michael, N., Dellaert, F.: Multi-robot pose graph localization and data association from unknown initial relative poses via expectation maximization. In: 2014 IEEE International Conference on Robotics and Automation (ICRA), pp. 593–600. IEEE (2014)

    Google Scholar 

  28. Chang, T.-K., Chen, K., Mehta, A.: Resilient and consistent multirobot cooperative localization with covariance intersection. IEEE Trans. Rob. 38(1), 197–208 (2021)

    Article  Google Scholar 

  29. Jiang, X., Zeng, X., Sun, J., Chen, J.: Distributed solver for discrete-time Lyapunov equations over dynamic networks with linear convergence rate. IEEE Trans. Cybern. 52(2), 937–946 (2022)

    Article  Google Scholar 

  30. Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2022)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computing, University of Georgia, Athens, GA, 30602, USA

    Ehsan Latif & Ramviyas Parasuraman

Authors
  1. Ehsan Latif
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ramviyas Parasuraman
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ramviyas Parasuraman .

Editor information

Editors and Affiliations

  1. University of Franche-Comté, Montbéliard, France

    Julien Bourgeois

  2. École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland

    Jamie Paik

  3. CNRS, University of Franche-Comté, Besancon, France

    Benoît Piranda

  4. Harvard University, Boston, MA, USA

    Justin Werfel

  5. University of Bristol, Bristol, UK

    Sabine Hauert

  6. Boston University, Boston, MA, USA

    Alyssa Pierson

  7. University of Lübeck, Lubeck, Germany

    Heiko Hamann

  8. The Chinese University of Hong Kong, Shenzhen, Shenzhen, China

    Tin Lun Lam

  9. Kyoto University, Kyoto, Japan

    Fumitoshi Matsuno

  10. University of Illinois System, Urbana, IL, USA

    Negar Mehr

  11. University of Franche-Comté, Montbéliard, France

    Abdallah Makhoul

Rights and permissions

Reprints and permissions

Copyright information

© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Latif, E., Parasuraman, R. (2024). DGORL: Distributed Graph Optimization Based Relative Localization of Multi-robot Systems. In: Bourgeois, J., et al. Distributed Autonomous Robotic Systems. DARS 2022. Springer Proceedings in Advanced Robotics, vol 28. Springer, Cham. https://doi.org/10.1007/978-3-031-51497-5_18

Download citation

Publish with us

Policies and ethics

Search

Navigation