日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

計算複雑性arXiv:2006.01256

扉の開閉ギミックの平面配置におけるPSPACE完全性と万能性

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets

シェア:XThreadsFacebookLINEはてブBluesky

開閉扉ギミックを平面状に配置した系での到達可能性判定がPSPACE完全であることを示し、任意のギミックを平面扉系で模擬できる万能性を証明した。

著者: MIT Gadgets Group, Jeffrey Bosboom, Erik D. Demaine, Jenny Diomidova, Dylan Hendrickson, Hayashi Layers, Jayson Lynch

分類: cs.CC, cs.RO

原文アブストラクト

An open-close door gadget has two states and three tunnels that can be traversed by an agent (player, robot, etc.): the "opening" and "closing" tunnels set the gadget's state to open and closed, respectively, while the "traverse" tunnel can be traversed if and only if the door is in the open state. We prove that it is PSPACE-complete to decide whether an agent can move from one location to another through a planar system of any such door gadget, removing the traditional need for crossover gadgets and thereby simplifying past PSPACE-hardness proofs of Lemmings and Nintendo games Super Mario Bros., Legend of Zelda, and Donkey Kong Country. Even stronger, we show that any gadget in the motion-planning-through-gadgets framework can be simulated by a planar system of door gadgets: the open-close door gadget is a universal gadget. We prove that these results hold for a variety of door gadgets. In particular, the opening, closing, and traverse tunnel locations can have an arbitrary cyclic order around the door; each tunnel can be directed or undirected; and the opening tunnel can instead be an optional button (with identical entrance and exit locations). Furthermore, we show the same hardness and universality results for two simpler types of door gadgets: self-closing door gadgets and symmetric self-closing door gadgets. Again we show that any self-closing door gadget planarly simulates any gadget, and thus the reachability motion planning problem is PSPACE-complete. Then we apply this framework to prove new PSPACE-hardness results for eight different 3D Mario video games and Sokobond.

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

OZ GAMING(GPU搭載BTOゲーミングPC)

OZ GAMING(GPU搭載BTOゲーミングPC)の公式広告バナーOZ GAMINGで完成品PCを見る ↗
PR本紙発行元 EmplifAI