智能规划问题相变规律研究

The project mainly exploits the phase transitions of artificial intelligent (AI) planning problems with higher computational complexity, which focuses on the phase transitions of the STRIPS planning with parallel actions, the propositional planning with action costs, and the conformant planning problem. We study the essence of the computational complexity of the AI planning problems, discuss the relationship between the phase transitions and the hardness of the AI planning problems, and design the efficient solving algorithms of the three AI planning problems. We aim at establishing the AI planning theory and method with our own characteristic in the international area. The research has not only important theory system in artificial intelligent area, but also widely application prospects, such as robot control system, emergency system, and intelligent schedule system.

本项目主要考虑计算复杂度更高的智能规划问题的相变现象,研究并行STRIPS规划问题、带动作代价的规划问题和一致性规划问题的相变现象，探讨上述规划问题计算复杂性的本质成因以及问题相变现象和求解难度的关系，有针对性的设计智能规划的高效求解算法，开发相应的智能规划求解系统，最终建立国际上有我们自己特色的、成体系的智能规划理论和方法。本项目的研究不仅在人工智能领域有着重要的理论研究价值，在机器人控制系统、应急系统、智能调度系统等许多领域也都有着十分广泛的应用前景。

本项目旨在研究智能规划问题的相变现象，探讨计算复杂性的本质成因以及问题相变现象和求解难度的关系，有针对性的设计智能规划的高效求解算法。项目组在智能规划问题建模和复杂性刻画、相变规律研究以及规划问题的求解方面开展了研究工作，研究了在初始状态未知，动作具有不确定性的情况下智能规划问题的相变现象，从理论上证明了这类问题相变现象与求解难度的关系，探讨了多尺度规划问题的建模，从侧面研究了并行STRIPS 规划问题的复杂性，设计了相关问题的求解算法。在国内外期刊发表或录用论文5篇，其中SCI期刊3篇，出版专著1本，获得吉林省科学技术奖（二等）1项、吉林省自然科学学术成果奖（二等）1项。我们取得的成果有望在人工智能、机器人控制领域得到应用。