经典规划

智能规划(intelligent planning)是人工智能研究的一个重要领域,它的主要任务是在给定初始状态,可执行动作和目标条件的情况下,设计相应的规划系统,使得当前初始状态通过执行合适的动作序列到达满足目标条件的状态。规划问题的描述通常采用国际通用的规划域描述语言(planning domain description language,简称PDDL),包含了用词以及对各种逻辑关系的表示方法。对智能规划问题的抽象描述予以一定限制和规范化,就得到了经典规划问题(classical planning)。

简介

智能规划(intelligent planning)是人工智能研究的一个重要领域,它的主要任务是在给定初始状态,可执行动作和目标条件的情况下,设计相应的规划系统,使得当前初始状态通过执行合适的动作序列到达满足目标条件的状态。规划问题的描述通常采用国际通用的规划域描述语言(planning domain description language,简称PDDL),包含了用词以及对各种逻辑关系的表示方法。对智能规划问题的抽象描述予以一定限制和规范化,就得到了经典规划问题(classical planning)。

一个经典规划问题P是一个3元组(I , O, G),其中,I为初始状态(initial state),O为操作集(operator),G为目标条件(goal specification)。这里,每个操作o ∈ O的前提和效果都是确定的(deterministic)。经典规划问题P的一个经典规划是从初始状态I到达某个目标状态g ∈ G的动作序列。

示例:

(经典Logistics域问题) 包裹A和B在L地, 卡车T在L地,通过装载(load),移动(move)和卸载(unload)等3个操作的有效执行, 使得包裹A和B被移动到P地。

装载(load)操作包括先决条件(precondition)和动作效果(effects),其定义如下:

load(x, y, z): precondition: at(x,z), at(y,z) effects: in(x,y), ¬at(x,z)

上述描述表示:执行load(x, y, z)操作, 需要满足包裹x和卡车y都在z地这一前提,动作执行完成后将导致包裹x不在z地,而在卡车y中。

这一经典Logistics域问题的有效动作序列为:将包裹A和B分别执行动作load(A, T, L)和load(B, T, L)将其装载到卡车T中;执行动作move(T, L, P)移动卡车到P地;执行动作unload(A, T, P)和unload(B, T, P),使得包裹卸载到P地。这5个动作就是这个问题的经典规划,也称为规划解。

[描述来源:Fox, M., & Long, D. (2003). PDDL2. 1: An extension to PDDL for expressing temporal planning domains. Journal of artificial intelligence research.

URL:http://www.aaai.org/Papers/JAIR/Vol20/JAIR-2002.pdf

描述来源:Shuai, L., Lei, L., Lian, S., & Ying, L. (2009). Artificial intelligence planning methods based on automated reasoning techniques. Journal of Software, 20(5), 1226-1240.

URL:http://www.cnki.com.cn/Article/CJFDTOTAL-RJXB200905018.htm]

发展历史

规划(planning)研究最早起源于知识表示与推理(knowledge representation and reasoning),在20世纪90年代之前一直采用逻辑演绎的方法予以求解,主要侧重于经典逻辑下的各种推理技术的利用。1992年,Kautz等人提出将规划问题转换为命题可满足(propositional satisfiablility,简称SAT)问题予以求解的规划方法。1996年,Kautz等人又设计了SATPLAN规划系统,这使得使并发规划问题得以解决。1997年,Blum等人设计的Graphplan规划系统很好地解决了知识表示过程中的指数级空间爆炸问题,使得智能规划领域逐步得到相关研究者的重视。1998 年,首届国际规划竞赛(International Planning Competition,简称IPC)举办,之后这一比赛使得智能规划技术得到了长足的发展。

海湾战争中美军配备的动态分析和重规划工具DART被用于自动后勤规划和运输调度中,从而使得过去需要几个星期才能完成的调度工作在几个小时内就可以完成,为此,美国国防部高级研究计划局称,“仅智能规划的这一项应用成果就足以补偿其在人工智能研究方面的近30年的投资”。智能规划技术在生产流水线调度领域以及火星漫步者号、哈勃太空望远镜等航空领域上的应用也展现了其巨大的应用前景。

2005 年,Benedetti等人提出了一种基于可满足性的分布式规划方法,使得对于分布式规划问题,可以将其转换为分布式可满足性问题,通过求解子问题合成规划解。该方法给出了具体的转换方法和规划解合成技术,使得多个智能体之间的协作成为可能。智能规划技术已广泛应用于航空航天、机器人控制、后勤调度、游戏角色设计和系统建模中,带来的成果是有目共睹的。

主要事件

年份事件相关论文
1992Kautz等人提出将规划问题转换为命题可满足(propositional satisfiablility,简称SAT)问题予以求解的基于可满足性的规划方法Kautz H, Selman B. (1992) Planning as satisfiability. In: Neumann B, ed. Proc. of the 10th European Conf. on Artificial Intelligence. Vienna: John Wiley&Sons, 359−363.
19961996年,Kautz等人通过公理的组合和规划图结构设计了SATPLAN规划系统,使并发规划问题得以解决Kautz, H., & Selman, B. (1996, August). Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the National Conference on Artificial Intelligence (pp. 1194-1201).
1997Blum等人设计的Graphplan规划系统很好地解决了知识表示过程中的指数级空间爆炸问题Blum, A. L., & Furst, M. L. (1997). Fast planning through planning graph analysis. Artificial intelligence, 90(1), 281-300.
1998Baioletti 等人在1998 年提出了规划约束描述语言(planning constraints definition language,简称PCDL)和结合SATPLAN 与PCDL 描述的规划系统C-SATPLANBaioletti, M., Marcugini, S., & Milani, A. (1998). Encoding planning constraints into partial order planning domains. In PRINCIPLES OF KNOWLEDGE REPRESENTATION AND REASONING-INTERNATIONAL CONFERENCE- (pp. 608-616). MORGAN KAUFMANN PUBLISHERS.
20052005 年,Benedetti等人提出了一种基于可满足性的分布式规划方法,该方法给出了具体的转换方法和规划解合成技术,使得多个智能体之间的协作成为可能。Benedetti, M., & Aiello, L. C. (2005). SAT-Based Cooperative Planning: A Proposal. Mechanizing Mathematical Reasoning, 2605, 494-513.
2006Kautz等人设计了SATPLAN2006。随后参加了IPC-5,并获得了Optimal Planning的冠军。Kautz, H., & Selman, B. (2006). SATPLAN04: Planning as satisfiability. Working Notes on the Fifth International Planning Competition (IPC-2006), 45-46.

发展分析

瓶颈

规划问题表示方法在某些应用下表现出描述能力不足的缺点,此外部分场景下的描述远离人的自然理解

未来发展方向

针对现实世界问题改进规划问题表示方法:

1) 设计更优的描述语法,而不仅仅局限于PDDL;

2) 设计(可能不实际的)抽象的规划问题表示,使得规划问题的刻画将更接近人的自然理解;

3) 研究规划问题的逻辑特性,设计符合该逻辑特性的专用的规划系统的推理模块,充分发挥不同类型推理模块的性能优势;

Contributor: Keyu Qi

相关人物
Fausto Giunchiglia
Fausto Giunchiglia
巴特·塞尔曼
巴特·塞尔曼
AAAI、AAAS、ACM会士。康奈尔大学计算机科学教授,曾就职于贝尔实验室。1983年获得物理学硕士学位,分别于1985年和1991年在多伦多大学获得计算机科学硕士和博士学位。主要研究tractable inference、知识表示、随机搜索方法、规划,以及计算机科学和统计物理之间的联系,即相变现象。
Marco Baioletti
Marco Baioletti
亨利·考茨
亨利·考茨
计算机科学家,美国国家科学基金会信息和智能系统部门主任,罗切斯特大学教授、数据科学研究所创始主任,AAAI、AAAS会士。研究兴趣:知识表示、人工智能、数据科学和普适计算。
Jussi Rintanen
Jussi Rintanen
简介
相关人物