Probabilistic Response-Time-Aware Search For Transient Astrophysical Phenomena

Abstract

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 real-time 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 ≤ 0.5% deviation from the ILP-computed optimal solution on tractable problem instances while running within a second, on average, for larger inputs.

Department(s)

Computer Science

Comments

National Science Foundation, Grant CNS-2141256

International Standard Serial Number (ISSN)

1052-8725

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2026 Institute of Electrical and Electronics Engineers (IEEE), All rights reserved.

Publication Date

01 Jan 2025

Link to Full Text

Share

 
COinS