Period/Dynamic Planning Problem: Formal Representation and Complexity Analysis

被引：0

作者：

Chen, Aixiang ^{[1
,2
]}

Chen, Qingliang

机构：

[1] Jinan Univ, Dept Comp Sci, Guangzhou 510632, Guangdong, Peoples R China

[2] Guangdong Univ Business Studies, Dept Informat & Comp Sci, Guangzhou 510320, Guangdong, Peoples R China

来源：

ICICTA: 2009 SECOND INTERNATIONAL CONFERENCE ON INTELLIGENT COMPUTATION TECHNOLOGY AND AUTOMATION, VOL IV, PROCEEDINGS | 2009年

关键词：

Period/Dynamic Planning; Transportation Planning; Computational Complexity;

D O I：

10.1109/ICICTA.2009.770

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Transportation planning and path planning are hot research topics which can be evidenced by their frequent and repeated presence in the benchmark test in International Planning Competition. However, most of the benchmark test examples only consider the static planning problems, whose state transitions are only caused by the actions of the planners. In this paper, we will discuss the dynamic version and introduce the formalization of the Period/Dynamic planning problem. Then, we will prove that the computational complexity is EXPSPACE-Complete.

引用

页码：227 / +

页数：2

共 6 条

[1] THE COMPUTATIONAL-COMPLEXITY OF PROPOSITIONAL STRIPS PLANNING
BYLANDER, T
[J]. ARTIFICIAL INTELLIGENCE, 1994, 69 (1-2) : 165 - 204
[2] EDELKAMP S, 2004, 195 A LUDW U I INF
[3] PDDL2.1: An extension to PDDL for expressing temporal planning domains
Fox, M
Long, D
[J]. JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2003, 20 : 61 - 124
[4] GEREVINI A, RT20050807 U BRESC D
[5] Helmert M, 2008, LECT NOTES COMPUT SC, V4929, P3
[6] Rintanen Jussi, 2007, P 17 INT C AUT PLANN, P280, DOI DOI 10.5555/3037176.3037213

← 1 →