Probabilistic Response-Time-Aware Search for Transient Astrophysical Phenomena

Timely observation of transient astrophysical phenomena (TAP) is of crucial importance for our understanding of the universe and the laws of physics, as recognized by the National Academies in the Astro2020 decadal survey. Ultimately, the goal is to observe TAPs as early as possible using optical telescopes. This is non-trivial due to the probabilistic nature of the search problem, where multiple potential sky locations for a TAP, each with an associated probability, must be scheduled for observation before successful localization. The problem lies at the intersection of several research disciplines, including realtime systems, cyber-physical systems, astrophysics, and operations research, motivating the need for a unified modeling framework. To this end, we introduce the first formal stochastic, response-time-aware model for search planning toward detection and localization of TAPs. We consider the problem of maximizing expected utility of early localization and show that it is reducible to the Orienteering Problem. Building on this formulation, we develop the real-time-capable Greedy-Christofides Pathfinding (GCP) algorithm. An evaluation on 37 probability maps from LIGO demonstrates that GCP consistently achieves high solution quality and computational efficiency across diverse search scenarios. GCP achieves$\leq 0.5 \%$deviation from the ILP-computed optimal solution on tractable problem instances while running within a second, on average, for larger inputs.