文献

J-GLOBAL ID：202202273499640715   整理番号：22A1088730

高密度時間上の行動ベース時間計画の決定可能性と複雑性【JST・京大機械翻訳】

Decidability and complexity of action-based temporal planning over dense time

著者 (4件)： Gigante Nicola (Free University of Bozen-Bolzano, Italy) ,  Micheli Andrea (Fondazione Bruno Kessler, Trento, Italy) ,  Montanari Angelo (University of Udine, Italy) ,  Scala Enrico (University of Brescia, Italy)
資料名： Artificial Intelligence  (Artificial Intelligence)
巻： 307  ページ： Null  発行年： 2022年 
JST資料番号： E0180C  ISSN： 0004-3702  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 本論文では,高密度時間にわたって解釈された行動ベース時間計画の計算複雑性を研究した。時間が離散的であると仮定すると,問題はEXPSPACE完全であることが知られている。しかし,公式PDDL2.1意味論と多くの実装は,高密度ドメインとして時間を解釈する。本研究は,問題の複雑さについていくつかの結果を提供し,いくつかの特に興味深い事例,すなわち,非ゼロに単純に要求される分離とは対照的に,相互排他的事象間の分離の最小量εが与えられるかどうか,また,その行動がそれ自身の既に実行している事例をオーバーラップするかどうかについて,いくつかの結果を提供した。著者らは,自己重複が禁止されたとき,PSPACE完全であると証明し,一方,それが許されるとき,それは,ε分離によってEXPSPACE完全になり,非ゼロ分離で不可解である。これらの結果は,PDDL2.1意味論のコアにおける定義における異なる選択の計算結果を明らかにし,これはこれまであいまいであった。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 時間 ,  *意味論 ,  計画 ,  行動 ,  *可能性 ,  計算量 ,  曖昧さ
準シソーラス用語： *決定可能性 ,  高密度 ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (4件)： 時間計画 ,  計算の複雑さ ,  時間付きオートマトン ,  タイリング問題

分類 (2件)： 人工知能  (JE08000Z) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 行動 ,  計画 ,  決定可能性 ,  複雑性