Heuristic Search For Physics-Based Problems: Angry Birds in PDDL+
本论文研究了如何使用跨域规划器和组合搜索来玩著名的人工智能挑战问题——Angry Birds。为了建模游戏，我们使用了PDDL+，这是一种适用于离散和连续 domains的混合规划语言，支持定期过程和外部事件。论文描述了模型并确定了减少问题复杂度的关键设计决策。此外，我们提出了几个域特定的增强措施，包括启发式和类似于偏好操作的一种搜索技术。它们一起可以减轻组合搜索的复杂性。我们通过在Angry Birds级别上与专门的域特定求解器进行比较来评估我们的算法。结果表明，我们在大多数级别上的表现与这些域特定的方法相当，即使我们没有使用域特定的搜索增强措施。
This paper studies how a domain-independent planner and combinatorial search can be employed to play Angry Birds, a well established AI challenge problem. To model the game, we use PDDL+, a planning language for mixed discrete/continuous domains that supports durative processes and exogenous events. The paper describes the model and identifies key design decisions that reduce the problem complexity. In addition, we propose several domain-specific enhancements including heuristics and a search technique similar to preferred operators. Together, they alleviate the complexity of combinatorial search. We evaluate our approach by comparing its performance with dedicated domain-specific solvers on a range of Angry Birds levels. The results show that our performance is on par with these domain-specific approaches in most levels, even without using our domain-specific search enhancements.
https://arxiv.org/abs/2303.16967
https://arxiv.org/pdf/2303.16967