Reliability of Information Gathering under Dynamic and Stochastic Utility

Scheduling tasks across multiple resources is a critical challenge in many domains, including the process of information gathering via drones. The complexity increases when tasks (i.e., reconnaissance operations) have dynamic utility functions that represent the value or benefit provided by completing the task at any given time. These utility functions can change over time due to external factors, and the goal is to maximize the total or expected utility while minimizing the costs associated with switching between tasks. The stochastic job scheduling problem addresses scenarios in which tasks are dynamically assigned to resources with utility values that may be probabilistic. Each task's utility varies over time, and switching tasks incurs costs such as time, energy, or other penalties, adding complexity to optimizing resource schedules.We demonstrate that the deterministic version (utility values are fixed) of the problem, involving a single information gathering agent (i.e., drone) and multiple monitoring regions, is NPHard. To address this, we develop an integer linear programming (ILP) model with constraints that ensure feasible solutions. By introducing uncertainty and a decay function, we make the utility values stochastic and dynamic and use the ILP model to solve the problem effectively. Additionally, we propose an iterative algorithm to determine a nonzero switching cost matrix that maximizes total utility, providing a practical approach to optimizing resource scheduling in dynamic environments.

Keywords: Defense, Security risks, Socio-technical systems, Crisis management, Disaster management.