Period/Dynamic Planning Problem: Formal Representation and Complexity Analysis

摘要：

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.

关键词： Period/Dynamic Manning Transportation Planning Computational Complexity

作者: Aixiang Chen Qingliang Chen

作者单位: Department of Information and Computing Science Guangdong University of Business Studies Guangzhou 5 Department of Computer Science Jinan University Guangzhou 510632, P.R.China

会议类型: 国际会议

会议名称: 2009 Second International Conference on Intelligent Computation Technology and Automation(2009 第二届IEEE智能计算与自动化国际会议 ICICTA 2009)

会议地点: 长沙

会议语种:英文

页码: 3206-3209

在线出版日期: 2009-10-10（万方平台首次上网日期，不代表论文的发表时间）