An Anytime Algorithm for Task and Motion MDPs
Integrated task and motion planning has emerged as a challenging problem in sequential decision making, where a robot needs to compute high-level strategy and low-level motion plans for solving complex tasks. While high-level strategies require decision making over longer time-horizons and scales, their feasibility depends on low-level constraints based upon the geometries and continuous dynamics of the environment. The hybrid nature of this problem makes it difficult to scale; most existing approaches focus on deterministic, fully observable scenarios. We present a new approach where the high-level decision problem occurs in a stochastic setting and can be modeled as a Markov decision process. In contrast to prior efforts, we show that complete MDP policies, or contingent behaviors, can be computed effectively in an anytime fashion. Our algorithm continuously improves the quality of the solution and is guaranteed to be probabilistically complete. We evaluate the performance of our approach on a challenging, realistic test problem: autonomous aircraft inspection. Our results show that we can effectively compute consistent task and motion policies for the most likely execution-time outcomes using only a fraction of the computation required to develop the complete task and motion policy.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingMotion PlanningSequential Decision MakingTask and Motion PlanningSimilar Papers 제목 키워드 기반
Action Selection for MDPs: Anytime AO* vs. UCT
In the presence of non-admissible heuristics, A* and other best-first algorithms can be converted into anytime optimal algorithms over OR graphs, by simply continuing the search after the first solution is found. The sam…
Heuristic SearchAnytime-Constrained Reinforcement Learning
We introduce and study constrained Markov Decision Processes (cMDPs) with anytime constraints. An anytime constraint requires the agent to never violate its budget at any point in time, almost surely. Although Markovian …
reinforcement-learningReinforcement LearningAnytime-Competitive Reinforcement Learning with Policy Prior
This paper studies the problem of Anytime-Competitive Markov Decision Process (A-CMDP). Existing works on Constrained Markov Decision Processes (CMDPs) aim to optimize the expected reward while constraining the expected …
reinforcement-learningReinforcement LearningRobust Anytime Learning of Markov Decision Processes
Markov decision processes (MDPs) are formal models commonly used in sequential decision-making. MDPs capture the stochasticity that may arise, for instance, from imprecise actuators via probabilities in the transition fu…
Bayesian InferenceDecision MakingSequential Decision MakingAnytime Incremental $ρ$POMDP Planning in Continuous Spaces
Partially Observable Markov Decision Processes (POMDPs) provide a robust framework for decision-making under uncertainty in applications such as autonomous driving and robotic exploration. Their extension, $\rho$POMDPs, …
Autonomous DrivingDecision MakingDecision Making Under Uncertainty