TY - GEN
T1 - A Route Search System Considering Urgency and Efficient Coverage Without Complete Information
AU - Matsubara, Masaki
AU - Nakamura, Yuta
AU - Suzuki, Nobutaka
AU - Inoguchi, Munenari
AU - Morishima, Atsuyuki
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/4/1
Y1 - 2019/4/1
N2 - 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.
AB - 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.
KW - Natural disaster response
KW - Route search algorithm
UR - http://www.scopus.com/inward/record.url?scp=85064605618&partnerID=8YFLogxK
U2 - 10.1109/BIGCOMP.2019.8679212
DO - 10.1109/BIGCOMP.2019.8679212
M3 - 会議への寄与
AN - SCOPUS:85064605618
T3 - 2019 IEEE International Conference on Big Data and Smart Computing, BigComp 2019 - Proceedings
BT - 2019 IEEE International Conference on Big Data and Smart Computing, BigComp 2019 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 IEEE International Conference on Big Data and Smart Computing, BigComp 2019
Y2 - 27 February 2019 through 2 March 2019
ER -