Detecting Unsolvability Based on Separating Functions

Christen, Remo and Eriksson, Salomé and Pommerening, Florian and Helmert, Malte. (2022) Detecting Unsolvability Based on Separating Functions. In: Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022). Palo Alto, California USA, pp. 44-52.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/93362/

Downloads: Statistics Overview


While the unsolvability IPC sparked a multitude of planners proficient in detecting unsolvable planning tasks, there are gaps where concise unsolvability arguments are known but no existing planner can capture them without prohibitive computational effort. One such example is the sliding tiles puzzle, where solvability can be decided in polynomial time with a parity argument. We introduce separating functions, which can prove that one state is unreachable from another, and show under what conditions a potential function over any nonzero ring is a separating function. We prove that we can compactly encode these conditions for potential functions over features that are pairs, and show in which cases we can efficiently synthesize functions satisfying these conditions. We experimentally evaluate a domain-independent algorithm that successfully synthesizes such separating functions from PDDL representations of the sliding tiles puzzle, the Lights Out puzzle, and Peg Solitaire.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Christen, Remo and Eriksson, Salomé and Pommerening, Florian and Helmert, Malte
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Identification Number:
edoc DOI:
Last Modified:09 Feb 2023 13:53
Deposited On:08 Feb 2023 14:44

Repository Staff Only: item control page