Quality, Reliability, Security and Robustness in Heterogeneous Systems. 15th EAI International Conference, QShine 2019, Shenzhen, China, November 22–23, 2019, Proceedings

Research Article

Search Planning and Analysis for Mobile Targets with Robots

  • @INPROCEEDINGS{10.1007/978-3-030-38819-5_1,
        author={Shujin Ye and Wai Wong and Hai Liu},
        title={Search Planning and Analysis for Mobile Targets with Robots},
        proceedings={Quality, Reliability, Security and Robustness in Heterogeneous Systems. 15th EAI International Conference, QShine 2019, Shenzhen, China, November 22--23, 2019, Proceedings},
        proceedings_a={QSHINE},
        year={2020},
        month={1},
        keywords={Robot search Mobile target Search planning and analysis},
        doi={10.1007/978-3-030-38819-5_1}
    }
    
  • Shujin Ye
    Wai Wong
    Hai Liu
    Year: 2020
    Search Planning and Analysis for Mobile Targets with Robots
    QSHINE
    Springer
    DOI: 10.1007/978-3-030-38819-5_1
Shujin Ye1,*, Wai Wong1,*, Hai Liu1,*
  • 1: The Hang Seng University of Hong Kong
*Contact email: sye@hsu.edu.hk, wongwk@hsu.edu.hk, hliu@hsu.edu.hk

Abstract

With robotics technologies advancing rapidly, there are many new robotics applications such as surveillance, mining tasks, search and rescue, and autonomous armies. In this work, we focus on use of robots for target searching. For example, a collection of Unmanned Aerial Vehicle (UAV) could be sent to search for survivor targets in disaster rescue missions. We assume that there are multiple targets. The moving speeds and directions of the targets are unknown. Our objective is to minimize the searching latency which is critical in search and rescue applications. Our basic idea is to partition the search area into grid cells and apply the divide-and-conquer approach. We propose two searching strategies, namely, the circuit strategy and the rebound strategy. The robots search the cells in a Hamiltonian circuit in the circuit strategy while they backtrack in the rebound strategy. We prove that the expected searching latency of the circuit strategy for a moving target is upper bounded by where is the number of grid cells of the search region. In case of a static or suerfast target, we derive the expected searching latency of the two strategies. Simulations are conducted and the results show that the circuit strategy outperforms the rebound strategy.