Search papers, labs, and topics across Lattice.
This paper addresses the challenge of when a robot should replan in non-stationary environments by formulating the problem within the framework of time-varying Markov decision processes (TVMDPs). The authors introduce a skip-update scheme that leverages maximum likelihood estimation for transition kernels and dynamically allocates computational resources based on a regret-guided update rule. Their evaluation in simulated Mars-rover navigation and quadrotor tasks demonstrates that adaptive budget allocation significantly outperforms traditional methods, providing a practical solution to the replanning dilemma in robotics.
Adaptive budget allocation for robot replanning can significantly enhance performance in dynamic environments, outperforming traditional methods.
Robots operating in non-stationary environments must continually adapt their policies as the dynamics drift, but onboard energy and compute budgets cap how often a full state estimation and re-planning step can be performed. This raises a question: \emph{when}, along a horizon, should a robot spend its limited budget? We formulate this problem in time-varying Markov decision processes (TVMDPs) with a known bound on the rate of transition drift. We model execution as a \emph{skip-update} scheme in which, at chosen update times, the agent estimates the transition kernel by maximum likelihood and computes a finite-horizon policy, and between updates reuses this policy under a propagated state estimate. We analyze the dynamic regret of this scheme and show how it grows during skip intervals in terms of the properties of the TVMDP and the skip lengths; the resulting bound answers the opening question via an online, regret-guided update rule that allocates the budget adaptively. We evaluate the rule in a simulated Mars-rover navigation task with time-varying slip dynamics and on a Crazyflie quadrotor in indoor obstacle fields. Adaptive allocation outperforms other budgeted baselines.
