A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems

Yi Zhang; Daniel Boley; John Harwell; Maria Gini

doi:10.1007/978-3-031-22216-0_48

A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems

Yi Zhang, Daniel Boley, John Harwell, Maria Gini

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

Multi-robot systems are frequently used for tasks involving searching, so it is important to be able to estimate the searching time. Yet, simulation approaches and real-world experiments to determine searching time can be cumbersome and even impractical. In this work, we propose a correlated-random-walk based model to efficiently approximate hitting time distributions of multi-robot systems in large arenas. We verified the computational results by using ARGoS, a physics-based simulator. We found that the Gamma distribution can provide a good fit to the hitting time distributions of random walkers.

Original language	English (US)
Title of host publication	Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17
Editors	Ivan Petrovic, Ivan Markovic, Emanuele Menegatti
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	724-736
Number of pages	13
ISBN (Print)	9783031222153
DOIs	https://doi.org/10.1007/978-3-031-22216-0_48
State	Published - 2023
Event	17th International Conference on Intelligent Autonomous Systems, IAS-17 - Zagreb, Croatia Duration: Jun 13 2022 → Jun 16 2022

Publication series

Name	Lecture Notes in Networks and Systems
Volume	577 LNNS
ISSN (Print)	2367-3370
ISSN (Electronic)	2367-3389

Conference

Conference	17th International Conference on Intelligent Autonomous Systems, IAS-17
Country/Territory	Croatia
City	Zagreb
Period	6/13/22 → 6/16/22

Bibliographical note

Funding Information:
Acknowledgements. This research was partially supported by the University of Minnesota Robotics Institute.

Publisher Copyright:
© 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

Correlated random walk
Hitting time distribution
Multi-robot systems

Publisher link

10.1007/978-3-031-22216-0_48

Find It

Find It at U of M Libraries

Cite this

Zhang, Y., Boley, D., Harwell, J., & Gini, M. (2023). A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems. In I. Petrovic, I. Markovic, & E. Menegatti (Eds.), Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17 (pp. 724-736). (Lecture Notes in Networks and Systems; Vol. 577 LNNS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-22216-0_48

A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems. / Zhang, Yi; Boley, Daniel; Harwell, John et al.
Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17. ed. / Ivan Petrovic; Ivan Markovic; Emanuele Menegatti. Springer Science and Business Media Deutschland GmbH, 2023. p. 724-736 (Lecture Notes in Networks and Systems; Vol. 577 LNNS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Zhang, Y, Boley, D, Harwell, J & Gini, M 2023, A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems. in I Petrovic, I Markovic & E Menegatti (eds), Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17. Lecture Notes in Networks and Systems, vol. 577 LNNS, Springer Science and Business Media Deutschland GmbH, pp. 724-736, 17th International Conference on Intelligent Autonomous Systems, IAS-17, Zagreb, Croatia, 6/13/22. https://doi.org/10.1007/978-3-031-22216-0_48

Zhang Y, Boley D, Harwell J, Gini M. A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems. In Petrovic I, Markovic I, Menegatti E, editors, Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17. Springer Science and Business Media Deutschland GmbH. 2023. p. 724-736. (Lecture Notes in Networks and Systems). doi: 10.1007/978-3-031-22216-0_48

Zhang, Yi ; Boley, Daniel ; Harwell, John et al. / A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems. Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17. editor / Ivan Petrovic ; Ivan Markovic ; Emanuele Menegatti. Springer Science and Business Media Deutschland GmbH, 2023. pp. 724-736 (Lecture Notes in Networks and Systems).

@inproceedings{658a02ddf03c4ca6a2ff483a34cce02a,

title = "A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems",

abstract = "Multi-robot systems are frequently used for tasks involving searching, so it is important to be able to estimate the searching time. Yet, simulation approaches and real-world experiments to determine searching time can be cumbersome and even impractical. In this work, we propose a correlated-random-walk based model to efficiently approximate hitting time distributions of multi-robot systems in large arenas. We verified the computational results by using ARGoS, a physics-based simulator. We found that the Gamma distribution can provide a good fit to the hitting time distributions of random walkers.",

keywords = "Correlated random walk, Hitting time distribution, Multi-robot systems",

author = "Yi Zhang and Daniel Boley and John Harwell and Maria Gini",

note = "Funding Information: Acknowledgements. This research was partially supported by the University of Minnesota Robotics Institute. Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 17th International Conference on Intelligent Autonomous Systems, IAS-17 ; Conference date: 13-06-2022 Through 16-06-2022",

year = "2023",

doi = "10.1007/978-3-031-22216-0_48",

language = "English (US)",

isbn = "9783031222153",

series = "Lecture Notes in Networks and Systems",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "724--736",

editor = "Ivan Petrovic and Ivan Markovic and Emanuele Menegatti",

booktitle = "Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17",

address = "Germany",

}

TY - GEN

T1 - A Correlated Random Walk Model to Rapidly Approximate Hitting Time Distributions in Multi-robot Systems

AU - Zhang, Yi

AU - Boley, Daniel

AU - Harwell, John

AU - Gini, Maria

N1 - Funding Information: Acknowledgements. This research was partially supported by the University of Minnesota Robotics Institute. Publisher Copyright: © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.

PY - 2023

Y1 - 2023

N2 - Multi-robot systems are frequently used for tasks involving searching, so it is important to be able to estimate the searching time. Yet, simulation approaches and real-world experiments to determine searching time can be cumbersome and even impractical. In this work, we propose a correlated-random-walk based model to efficiently approximate hitting time distributions of multi-robot systems in large arenas. We verified the computational results by using ARGoS, a physics-based simulator. We found that the Gamma distribution can provide a good fit to the hitting time distributions of random walkers.

AB - Multi-robot systems are frequently used for tasks involving searching, so it is important to be able to estimate the searching time. Yet, simulation approaches and real-world experiments to determine searching time can be cumbersome and even impractical. In this work, we propose a correlated-random-walk based model to efficiently approximate hitting time distributions of multi-robot systems in large arenas. We verified the computational results by using ARGoS, a physics-based simulator. We found that the Gamma distribution can provide a good fit to the hitting time distributions of random walkers.

KW - Correlated random walk

KW - Hitting time distribution

KW - Multi-robot systems

UR - http://www.scopus.com/inward/record.url?scp=85148721836&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85148721836&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-22216-0_48

DO - 10.1007/978-3-031-22216-0_48

M3 - Conference contribution

AN - SCOPUS:85148721836

SN - 9783031222153

T3 - Lecture Notes in Networks and Systems

SP - 724

EP - 736

BT - Intelligent Autonomous Systems 17 - Proceedings of the 17th International Conference IAS-17

A2 - Petrovic, Ivan

A2 - Markovic, Ivan

A2 - Menegatti, Emanuele

PB - Springer Science and Business Media Deutschland GmbH

T2 - 17th International Conference on Intelligent Autonomous Systems, IAS-17

Y2 - 13 June 2022 through 16 June 2022

ER -