Markovian search games in heterogeneous spaces

Area of Science:

• Robotics and Automation
• Operations Research
• Game Theory

Background:

• Searching for mobile evaders in large, heterogeneous regions presents significant challenges.
• Sensor detection probabilities are often non-uniform due to environmental factors.

Purpose of the Study:

• To develop an optimal probabilistic search strategy for mobile evader detection.
• To address the complexities of heterogeneous environments and sensor limitations.

Main Methods:

• The problem is modeled as a graph-search problem.
• A dynamic game played on a Markov chain is used to derive the search strategy.
• The strategy's optimality is proven in the sense of Nash equilibrium.

Main Results:

• A tractable optimal probabilistic search strategy was derived.
• The strategy effectively handles non-uniform sensor detection probabilities.
• Simulations validated the approach and confirmed its optimality.

Conclusions:

• The proposed dynamic game on a Markov chain provides an effective framework for mobile evader search.
• This research offers a robust solution for optimizing search operations in complex, uncertain environments.