Admissible Abstractions for Near-optimal Task and Motion Planning
We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous state. We extract upper and lower bounds on the cost of concrete motion plans using local metric and topological properties of the problem domain. These bounds guide the search for a plan while maintaining performance guarantees. We show that abstraction can dramatically reduce the complexity of search relative to a direct motion planner. Using our abstractions, we find near-optimal motion plans in planning problems involving $10^{13}$ states without using a separate task planner.
Code (0)
등록된 구현이 없습니다.
Tasks
Motion PlanningTask and Motion PlanningSimilar Papers 제목 키워드 기반
LLM-Evolved Pattern Generators for Optimal Classical Planning
Learned heuristics have recently become a competitive alternative to traditional domain-independent heuristics for satisficing planning. Existing approaches, however, focus on improving search guidance rather than guaran…
Learning Admissible Heuristics for A*: Theory and Practice
Heuristic functions are central to the performance of search algorithms such as A-star, where admissibility - the property of never overestimating the true shortest-path cost - guarantees solution optimality. Recent deep…
Reasoning with shapes: profiting cognitive susceptibilities to infer linear mapping transformations between shapes
Visual information plays an indispensable role in our daily interactions with environment. Such information is manipulated for a wide range of purposes spanning from basic object and material perception to complex gestur…
Scene UnderstandingNear Optimal Behavior via Approximate State Abstraction
The combinatorial explosion that plagues planning and reinforcement learning (RL) algorithms can be moderated using state abstraction. Prohibitively large task representations can be condensed such that essential informa…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)State Abstractions for Lifelong Reinforcement Learning
In lifelong reinforcement learning, agents must effectively transfer knowledge across tasks while simultaneously addressing exploration, credit assignment, and generalization. State abstraction can help overcome the…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)