A Route Search System Considering Urgency and Efficient Coverage Without Complete Information

Masaki Matsubara, Yuta Nakamura, Nobutaka Suzuki, Munenari Inoguchi, Atsuyuki Morishima

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

1 Scopus citations

Abstract

Path planning to visit all nodes in a graph with deadlines has applications such as the route search for shooting aerial photography in a natural disaster. In such applications, we need to calculate the route that covers all graph nodes as efficiently as possible while satisfying the urgency requirements. This paper proposes a system to find routes in such a situations. In our system, information on the urgency (the deadline for visiting each node) is not necessarily fully known in advance and can be updated at any time, and we cannot totally optimize the route in advance. Therefore, we devised a greedy method tries to go to the nodes with high urgency while keeping all of the remaining nodes being directly connected to each other. Our preliminary experiments show that the proposed method is better in the performance than the simple greedy method that does not consider the factor; the proposed method was 29.42% better to the simple greedy method in terms of missed deadlines and 36.52% better in terms of the total flight time.

Original languageEnglish
Title of host publication2019 IEEE International Conference on Big Data and Smart Computing, BigComp 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781538677896
DOIs
StatePublished - 2019/04/01
Event2019 IEEE International Conference on Big Data and Smart Computing, BigComp 2019 - Kyoto, Japan
Duration: 2019/02/272019/03/02

Publication series

Name2019 IEEE International Conference on Big Data and Smart Computing, BigComp 2019 - Proceedings

Conference

Conference2019 IEEE International Conference on Big Data and Smart Computing, BigComp 2019
Country/TerritoryJapan
CityKyoto
Period2019/02/272019/03/02

Keywords

  • Natural disaster response
  • Route search algorithm

ASJC Scopus subject areas

  • Information Systems and Management
  • Artificial Intelligence
  • Computer Networks and Communications
  • Information Systems

Fingerprint

Dive into the research topics of 'A Route Search System Considering Urgency and Efficient Coverage Without Complete Information'. Together they form a unique fingerprint.

Cite this