Multi-target rendezvous search

In this paper, we examine multi-target search, where one or more targets must be found by a moving robot. Given the target's initial probability distribution or the expected search region, we present an analysis of three search strategies - Global maxima search, Local maxima search, and Spiral search. We aim at minimizing the mean-time-to-find and maximizing the total probability of finding the target. This leads to two types of illustrative performance metrics: minimum time capture and guaranteed capture. We validate the search strategies with respect to these two performance metrics. In addition, we study the effect of different target distributions on the performance of the search strategies. We also consider the practical realization of the proposed algorithms for multi-target search. The search strategies are analytically evaluated, through simulations and illustrative deployments, in open-water with an Autonomous Surface Vehicle (ASV) and drifting sensor targets.

Authors

• Malika Meghjani
• Sandeep Manjanna
• Gregory Dudek

Keywords

• Search problems
• Spirals
• Robots
• Probability distribution
• Target tracking
• Trajectory
• Search Strategy
• Performance Metrics
• Local Search
• Local Maxima
• Autonomous Vehicles
• Performance Of Strategies
• Global Search
• Target Distribution
• Target Search
• Search Region
• Maximum Search
• Autonomous Surface Vehicles
• Uniform Distribution
• Central Region
• Target Location
• Maximum Speed
• Field Trials
• Heuristic Search
• Pattern Search
• Search Area
• Spiral Pattern
• Autonomous Underwater Vehicles
• Local Search Strategy
• Circular Pattern
• Capture Time
• Search Problem
• Deterministic Strategy
• Speed Of The Robot
• Search Costs
• Substitution Rule