Optimal Decision-Making in an Opportunistic Sensing Problem.

Area of Science:

• Robotics and Automation
• Operations Research
• Sensor Networks

Background:

• Sensing moving objects with fixed sensors presents challenges due to limited control and time constraints.
• Opportunistic sensing strategies are crucial for maximizing data acquisition in dynamic environments.

Purpose of the Study:

• To formulate and solve the problem of maximizing sensor return for detecting moving objects over a finite horizon.
• To analyze the computational complexity and develop efficient algorithms for opportunistic sensing.

Main Methods:

• Formulation of an integer programming model to optimize sensor return.
• Analysis of computational complexity, demonstrating non-deterministic polynomial-hardness (NP-hard).
• Derivation of a strongly polynomial-time heuristic algorithm for computationally simpler subclasses.

Main Results:

• The proposed integer program effectively maximizes sensor return for deterministic or probabilistic object routes.
• The problem's NP-hard nature is established, highlighting the need for efficient heuristics.
• The derived heuristic provides a computationally feasible solution for practical applications.

Conclusions:

• The study provides a robust framework for opportunistic sensing of moving objects.
• The developed heuristic offers an efficient approach to a computationally complex problem.
• Findings are validated using both real-world and constructed datasets.