Multistage Mobile Anchor Redeployment in an Indoor Positioning System Using Hierarchical State Lagrangian Cut-Augmented Stochastic Dual Dynamic Integer Programming

Abstract

Technological advances enable mobile anchors to assist indoor localization services and lower system setup and maintenance costs. This research investigates the strategy for mobile anchor redeployment in light of dynamic target movements among areas of interest (AOIs), signal degradation, and obstacles leading to non-line-of-sight (NLOS) connections. By representing the realizations of target numbers in AOIs using a scenario tree, we formulate a multistage stochastic optimization model for the mobile anchor-assisted indoor positioning system (IPS) to minimize anchor movement cost, signal path loss, and NLOS penalties. The solution developed is based on the stochastic dual dynamic integer programming (SDDiP) framework using binary variables to indicate deployment states. To speed up solving large-scale instances, we propose the hierarchical state Lagrangian cut (HSLC), which extends the Lagrangian cut to approximate the value function based on both exact states and group binary-state variables that aggregate deployment states over location clusters. To tightly approximate cost-to-go functions, HSLC incorporates additional linear terms that model the transition costs from each exact state to an expected deployment state derived from solving the dual subproblem associated with the cut. We further incorporate a dynamic coefficient update scheme to progressively control the scale of transition costs, achieving asymptotic convergence while avoiding overestimation. Comparative experiments conducted on simulation instances with reference to an IPS project for exhibition halls demonstrate that the proposed algorithms can achieve the best cost performance compared with previous anchor deployment strategies. Under the same computational time for large-scale instances, the gap between the lower and upper bounds is reduced by over 95% compared with the SDDiP with previous benchmark cuts. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. Funding: The work presented in this article is supported by the Centre for Advances in Reliability and Safety admitted under the Air@InnoHK Research Cluster. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.0969 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.0969 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .