Portal de Periódicos da CAPES

Heuristic Search for Physics-Based Problems: Angry Birds in PDDL+ [Extended Abstract]

2023; Volume: 16; Issue: 1 Linguagem: Inglês

10.1609/socs.v16i1.27303

2832-9171

Wiktor Piotrowski, Yoni Sher, Sachin Grover, Roni Stern, Shiwali Mohan,

AI-based Problem Solving and Planning

Angry Birds is a very popular game that requires reasoning about sequential actions in a continuous world with discrete exogenous events. Different versions of the game are hard computationally, and the reigning world champion is still a human despite a long-running yearly competition in IJCAI conferences. In this work, we present the Hydra, the first successful game-playing agent for Angry Birds that uses a domain-independent planner and combinatorial search techniques. Hydra models the game using PDDL+, a rich planning language designed for mixed discrete/continuous domains. To reason about continuous aspects of the domain, Hydra employs time discretization techniques that raise a combinatorial search challenge. To meet this challenge, we propose domain-specific heuristics and a novel "preferred states" mechanism similar to the preferred operators mechanism from classical planning. We compared Hydra with state-of-the-art Angry Birds agents. The results show Hydra can solve a greater diversity of Angry Birds levels compared to other agents and highlight its current limitations.