TY - GEN
T1 - Efficient algorithms for pursuing moving evaders in terrains
AU - Efrat, Alon
AU - Mitchell, Joseph S.B.
AU - Sankararaman, Swaminathan
AU - Myers, Parrish
PY - 2012
Y1 - 2012
N2 - We propose algorithms for computing optimal trajectories of a group of flying observers (such as helicopters or UAVs) searching for a lost child in a hilly terrain. Very few assumptions are made about the speed or direction of the child's motion and whether it might (either deliberately or accidentally) try to avoid being found. This framework can also be applied to seekers searching for hostile evaders, such as smugglers/criminals, or friendly evaders, such as lost hikers. Based on the features of the area of the terrain where the pursuit takes place, and the visibility and motion characteristics of the UAVs, we show how to plan their synchronized trajectories in a way that maximizes the likelihood of a successful pursuit, while minimizing their battery or fuel usage, which may, in turn, enable a longer pursuit. Our algorithm explores useful I/O-efficient data structures and branch-cutting (search pruning) techniques to achieve further speedup by limiting the storage requirements and the total number of graph nodes searched, respectively.
AB - We propose algorithms for computing optimal trajectories of a group of flying observers (such as helicopters or UAVs) searching for a lost child in a hilly terrain. Very few assumptions are made about the speed or direction of the child's motion and whether it might (either deliberately or accidentally) try to avoid being found. This framework can also be applied to seekers searching for hostile evaders, such as smugglers/criminals, or friendly evaders, such as lost hikers. Based on the features of the area of the terrain where the pursuit takes place, and the visibility and motion characteristics of the UAVs, we show how to plan their synchronized trajectories in a way that maximizes the likelihood of a successful pursuit, while minimizing their battery or fuel usage, which may, in turn, enable a longer pursuit. Our algorithm explores useful I/O-efficient data structures and branch-cutting (search pruning) techniques to achieve further speedup by limiting the storage requirements and the total number of graph nodes searched, respectively.
KW - I/O-efficient data structures
KW - UAV
KW - algorithms
KW - branch-cutting
KW - coordinated route planning
KW - search and rescue
KW - sensors
UR - https://www.scopus.com/pages/publications/84872773574
UR - https://www.scopus.com/inward/citedby.url?scp=84872773574&partnerID=8YFLogxK
U2 - 10.1145/2424321.2424327
DO - 10.1145/2424321.2424327
M3 - Conference contribution
AN - SCOPUS:84872773574
SN - 9781450316910
T3 - GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems
SP - 33
EP - 42
BT - 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012
T2 - 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, ACM SIGSPATIAL GIS 2012
Y2 - 6 November 2012 through 9 November 2012
ER -