Online Planning in POMDPs with State-Requests
This addresses efficient planning for agents in domains with partial observability and expensive state requests, such as robotics or human-in-the-loop systems, though it is an incremental improvement over existing algorithms.
The paper tackles the problem of planning in partially observable Markov decision processes (POMDPs) where full state information is costly to obtain, proposing AEMS-SR, an online planning algorithm that uses a graph representation to avoid exponential search growth. Empirical results show its effectiveness compared to state-of-the-art methods like AEMS and POMCP.
In key real-world problems, full state information is sometimes available but only at a high cost, like activating precise yet energy-intensive sensors or consulting humans, thereby compelling the agent to operate under partial observability. For this scenario, we propose AEMS-SR (Anytime Error Minimization Search with State Requests), a principled online planning algorithm tailored for POMDPs with state requests. By representing the search space as a graph instead of a tree, AEMS-SR avoids the exponential growth of the search space originating from state requests. Theoretical analysis demonstrates AEMS-SR's $\varepsilon$-optimality, ensuring solution quality, while empirical evaluations illustrate its effectiveness compared with AEMS and POMCP, two SOTA online planning algorithms. AEMS-SR enables efficient planning in domains characterized by partial observability and costly state requests offering practical benefits across various applications.