Real-time multi-robot path planning revisited as a caching problem

Abhijeet Ravankar, Ankit A. Ravankar, Yukinori Kobayashi, Chao Chung Peng, Takanori Emaru

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

Path planning is a fundamental component of mobile robots. In case of large maps, path planning is a time consuming process, particularly for robots equipped with embedded computers and has adverse effects on the real-time response of the robots. This paper takes a fresh look at the path planning problem by considering it to be a caching or tabular-lookup problem. The robots 'cache' their generated paths and arm trajectories across various start and goal configurations. These cached paths are stored in a database accessible to robots in the network. Robot path planning is then reduced to a simple table-lookup which can be resolved in real-time. To overcome a cache-miss, a micro-grid and macro-grid based caching is proposed for real-time path generation for 'nearby' start and goal configurations. Another important characteristic of the proposed cache based path planning is that multiple robots also update the locations of the new obstacles in the map. This benefits other robots as they are able to get an updated information about the new obstacles in remote locations of the map, without explicitly discovering those obstacles by themselves. We show that by considering the robot path planning as a caching problem, robots can achieve faster and real-time responses, particularly in case of large maps with multiple robots in a sensor network.

Original languageEnglish
Title of host publicationProceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018
EditorsArtde Donald Kin-Tak Lam, Stephen D. Prior, Teen-Hang Meen
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages350-353
Number of pages4
ISBN (Electronic)9781538643426
DOIs
Publication statusPublished - 2018 Jun 22
Event4th IEEE International Conference on Applied System Innovation, ICASI 2018 - Chiba, Japan
Duration: 2018 Apr 132018 Apr 17

Publication series

NameProceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018

Other

Other4th IEEE International Conference on Applied System Innovation, ICASI 2018
CountryJapan
CityChiba
Period18-04-1318-04-17

Fingerprint

Multi-robot
Caching
Path Planning
Motion planning
Robot
Robots
Real-time
Cache
Path
Microgrid
Configuration
Table lookup
Look-up Table
Mobile Robot
Mobile robots
Sensor networks
Sensor Networks
Macros
Update
Trajectories

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Hardware and Architecture
  • Energy Engineering and Power Technology
  • Control and Systems Engineering
  • Mechanical Engineering
  • Control and Optimization
  • Modelling and Simulation
  • Biomedical Engineering

Cite this

Ravankar, A., Ravankar, A. A., Kobayashi, Y., Peng, C. C., & Emaru, T. (2018). Real-time multi-robot path planning revisited as a caching problem. In A. D. K-T. Lam, S. D. Prior, & T-H. Meen (Eds.), Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018 (pp. 350-353). (Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ICASI.2018.8394606
Ravankar, Abhijeet ; Ravankar, Ankit A. ; Kobayashi, Yukinori ; Peng, Chao Chung ; Emaru, Takanori. / Real-time multi-robot path planning revisited as a caching problem. Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018. editor / Artde Donald Kin-Tak Lam ; Stephen D. Prior ; Teen-Hang Meen. Institute of Electrical and Electronics Engineers Inc., 2018. pp. 350-353 (Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018).
@inproceedings{0782a22d65c74fcb8a65e632eba9077d,
title = "Real-time multi-robot path planning revisited as a caching problem",
abstract = "Path planning is a fundamental component of mobile robots. In case of large maps, path planning is a time consuming process, particularly for robots equipped with embedded computers and has adverse effects on the real-time response of the robots. This paper takes a fresh look at the path planning problem by considering it to be a caching or tabular-lookup problem. The robots 'cache' their generated paths and arm trajectories across various start and goal configurations. These cached paths are stored in a database accessible to robots in the network. Robot path planning is then reduced to a simple table-lookup which can be resolved in real-time. To overcome a cache-miss, a micro-grid and macro-grid based caching is proposed for real-time path generation for 'nearby' start and goal configurations. Another important characteristic of the proposed cache based path planning is that multiple robots also update the locations of the new obstacles in the map. This benefits other robots as they are able to get an updated information about the new obstacles in remote locations of the map, without explicitly discovering those obstacles by themselves. We show that by considering the robot path planning as a caching problem, robots can achieve faster and real-time responses, particularly in case of large maps with multiple robots in a sensor network.",
author = "Abhijeet Ravankar and Ravankar, {Ankit A.} and Yukinori Kobayashi and Peng, {Chao Chung} and Takanori Emaru",
year = "2018",
month = "6",
day = "22",
doi = "10.1109/ICASI.2018.8394606",
language = "English",
series = "Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "350--353",
editor = "Lam, {Artde Donald Kin-Tak} and Prior, {Stephen D.} and Teen-Hang Meen",
booktitle = "Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018",
address = "United States",

}

Ravankar, A, Ravankar, AA, Kobayashi, Y, Peng, CC & Emaru, T 2018, Real-time multi-robot path planning revisited as a caching problem. in ADK-T Lam, SD Prior & T-H Meen (eds), Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018. Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018, Institute of Electrical and Electronics Engineers Inc., pp. 350-353, 4th IEEE International Conference on Applied System Innovation, ICASI 2018, Chiba, Japan, 18-04-13. https://doi.org/10.1109/ICASI.2018.8394606

Real-time multi-robot path planning revisited as a caching problem. / Ravankar, Abhijeet; Ravankar, Ankit A.; Kobayashi, Yukinori; Peng, Chao Chung; Emaru, Takanori.

Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018. ed. / Artde Donald Kin-Tak Lam; Stephen D. Prior; Teen-Hang Meen. Institute of Electrical and Electronics Engineers Inc., 2018. p. 350-353 (Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Real-time multi-robot path planning revisited as a caching problem

AU - Ravankar, Abhijeet

AU - Ravankar, Ankit A.

AU - Kobayashi, Yukinori

AU - Peng, Chao Chung

AU - Emaru, Takanori

PY - 2018/6/22

Y1 - 2018/6/22

N2 - Path planning is a fundamental component of mobile robots. In case of large maps, path planning is a time consuming process, particularly for robots equipped with embedded computers and has adverse effects on the real-time response of the robots. This paper takes a fresh look at the path planning problem by considering it to be a caching or tabular-lookup problem. The robots 'cache' their generated paths and arm trajectories across various start and goal configurations. These cached paths are stored in a database accessible to robots in the network. Robot path planning is then reduced to a simple table-lookup which can be resolved in real-time. To overcome a cache-miss, a micro-grid and macro-grid based caching is proposed for real-time path generation for 'nearby' start and goal configurations. Another important characteristic of the proposed cache based path planning is that multiple robots also update the locations of the new obstacles in the map. This benefits other robots as they are able to get an updated information about the new obstacles in remote locations of the map, without explicitly discovering those obstacles by themselves. We show that by considering the robot path planning as a caching problem, robots can achieve faster and real-time responses, particularly in case of large maps with multiple robots in a sensor network.

AB - Path planning is a fundamental component of mobile robots. In case of large maps, path planning is a time consuming process, particularly for robots equipped with embedded computers and has adverse effects on the real-time response of the robots. This paper takes a fresh look at the path planning problem by considering it to be a caching or tabular-lookup problem. The robots 'cache' their generated paths and arm trajectories across various start and goal configurations. These cached paths are stored in a database accessible to robots in the network. Robot path planning is then reduced to a simple table-lookup which can be resolved in real-time. To overcome a cache-miss, a micro-grid and macro-grid based caching is proposed for real-time path generation for 'nearby' start and goal configurations. Another important characteristic of the proposed cache based path planning is that multiple robots also update the locations of the new obstacles in the map. This benefits other robots as they are able to get an updated information about the new obstacles in remote locations of the map, without explicitly discovering those obstacles by themselves. We show that by considering the robot path planning as a caching problem, robots can achieve faster and real-time responses, particularly in case of large maps with multiple robots in a sensor network.

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

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

U2 - 10.1109/ICASI.2018.8394606

DO - 10.1109/ICASI.2018.8394606

M3 - Conference contribution

AN - SCOPUS:85050286966

T3 - Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018

SP - 350

EP - 353

BT - Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018

A2 - Lam, Artde Donald Kin-Tak

A2 - Prior, Stephen D.

A2 - Meen, Teen-Hang

PB - Institute of Electrical and Electronics Engineers Inc.

ER -

Ravankar A, Ravankar AA, Kobayashi Y, Peng CC, Emaru T. Real-time multi-robot path planning revisited as a caching problem. In Lam ADK-T, Prior SD, Meen T-H, editors, Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018. Institute of Electrical and Electronics Engineers Inc. 2018. p. 350-353. (Proceedings of 4th IEEE International Conference on Applied System Innovation 2018, ICASI 2018). https://doi.org/10.1109/ICASI.2018.8394606