Nous utilisons la théorie des gadgets de planification de mouvement (et des gizmos de planification de mouvement étroitement liés) pour étudier la complexité de divers problèmes de planification de mouvement, notamment les jeux consistant à pousser et tirer des blocs, ainsi que des automates cellulaires asynchrones.

Un gadget de planification de mouvement est un objet doté d’un ensemble de ports, d’un ensemble d’états internes et d’une table de transition. L’agent (« joueur ») peut entrer dans un gadget par un port, modifier l’état interne du gadget et sortir par un autre port, conformément à la table de transition. Plusieurs gadgets peuvent être combinés en connectant certains de leurs ports. Les gadgets sont souvent intégrés dans le plan, et les connexions entre les gadgets doivent être planaires. Le problème de décision typique est celui de l’accessibilité : étant donné un réseau de gadgets, déterminer s’il est possible de se déplacer d’un endroit à un autre. Ce problème est dans PSPACE et, pour de nombreuses classes de gadgets, il est PSPACE-complet.

L’un des gadgets les plus simples est le gadget porte, qui comporte 3 paires de ports et 2 états (« ouvert » et « fermé »). Le passage entre la première paire de ports fait basculer l’état sur « ouvert », le passage entre la deuxième paire fait basculer l’état sur « fermé », et le passage entre la troisième paire de ports ne modifie pas l’état, mais n’est autorisé que dans l’état « ouvert ». Viglietta a démontré en 2012 que la planification de mouvements avec les gadgets de porte est PSPACE-difficile, si l’on ignore la contrainte d’être planaire. Nous montrons que tout plongement plan du gadget de porte est universel, c’est-à-dire qu’il peut simuler un gadget arbitraire (et donc PSPACE-difficile, en simulant votre gadget PSPACE-difficile préféré). Nous montrons également des résultats analogues pour plusieurs autres types de gadgets, à savoir les portes à fermeture automatique et les portes symétriques à fermeture automatique.

Sokoban est un jeu vidéo classique dans lequel le joueur doit pousser des caisses dans un entrepôt, l’objectif étant de pousser toutes les caisses vers des emplacements de stockage cibles. Culberson a démontré en 1997 que ce jeu est PSPACE-complet. Push-1F est un jeu très similaire, dans lequel l’objectif est simplement d’atteindre la fin du niveau, plutôt que de pousser les caisses vers des emplacements cibles. Ce jeu a été proposé pour la première fois par O’Rourke en 1999 et est resté sans solution pendant plus de deux décennies. Nous développons une théorie des gizmos vérifiables et l’utilisons pour montrer que Push-1F et plusieurs autres jeux similaires de poussée de blocs sont tous PSPACE-complets, résolvant ainsi ce problème ouvert de longue date.

Outre les jeux de poussée de blocs, nous examinons plusieurs jeux de traction de blocs. Nous montrons que beaucoup d’entre eux sont également PSPACE-complets.

Les jeux consistant à pousser et à tirer des blocs peuvent être naturellement modélisés comme des automates cellulaires asynchrones, avec des règles de transition telles que (agent, bloc, vide) -> (vide, agent, bloc). Nous considérons une classe plus large d’automates cellulaires asynchrones qui inclut à la fois les blocs poussés et tirés, et déterminons pour chaque automate de cette classe sa complexité computationnelle (dans P, NP-complet ou PSPACE-complet).

Nous étudions également la complexité computationnelle d’une autre classe d’automates cellulaires asynchrones, appelés réseaux de réactions chimiques de surface (sCRN). Dans un sCRN, chaque règle de transition (« réaction ») implique uniquement une paire de cellules adjacentes (« molécules »). Nous utilisons le cadre gadget pour montrer que les sCRN peuvent être NP-difficiles avec seulement 3 types de molécules et 1 réaction, et PSPACE-complets avec seulement 4 types de molécules et 3 réactions.