规划

Planning

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)和 logistics 规划。

来源:机器之心
简介

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(Classical Planning)、分层任务网络(HTN)规划和logistics 规划。

规划的目的是综合一系列有组织的行动来开展一些活动,比如说通过一系列预测步骤来达成目的。如下图所示,规划可以表示为预测步骤和搜索机制的组合。该过程通过将预测步骤和在备选行动中的搜索过程结合起来,来达到理想状态。

规划问题因要规划的行动种类、所需的预测模型种类以及理想计划而异。对于某些类型的问题,针对其量身定制的规划方法已经开发出来。例如,运动规划(motion planning)合成用于移动系统(例如卡车,机器人或虚拟角色)的几何和运动学轨迹; 感知规划(perception planning)综合了一组有组织的感知和解释行为来识别一个物体或建立一个场景的三维模型; 基础设施规划(infrastructure planning)通过规划来分配和组织设施(如公共交通基础设施),以优化其使用或满足社区需求。

然而,许多形式的规划有共同之处。域独立(Domain-independent)的规划试图在抽象层次上把握这些共性,在这个层次中,动作是通用的状态转换操作符,作为对象间关系的一种广泛适用的状态表示。

域独立和域特定(domain-specific)的规划相辅相成。在分层组织的参与者中,计划发生在结构的多个层次上。在高层次上,可以使用与领域无关的规划技术来解决问题的抽象描述。在下图所示的例子中,每个实心的红色箭头将抽象行为细化为更具体的行为,每个虚线的蓝色箭头将任务映射为行动计划。可以看到,我们可能需要一个路径规划器(用于移动到位置),一个操纵规划器(来完成图中开关门等行为)和一个在层次结构高层的独立于领域的规划器。

[图片及描述来源:Ghallab, M.; Nau, D.; and Traverso, P.(2016).Automated Planning and Acting. Cambridge University Press, ISBN: 9781107037274.]

发展历史

规划(planning)研究最早起源于知识表示与推理(knowledge representation and reasoning),在20世纪90年代之前一直采用逻辑演绎的方法予以求解,主要侧重于经典逻辑下的各种推理技术的利用。1971年,斯坦福研究所SRI International的Richard和Nils 开发了一种新的方法来应用定理证明来解决问题。该模型试图在一个世界模型的空间中找到一个操作序列,将初始的世界模型转化为一个目标状态存在的模型。它将世界建模为一组一阶谓词公式,并设计用于与包含大量公式的模型一起工作,这就是所谓的STRIPS。在STRIPS(Stanford Research Institute Problem Solver),problem solver的任务是找到一个算子序列,将给定的初始问题转化为满足目标条件的问题。操作符是构建解决方案的基本元素。每个操作符对应一个动作例程,其执行导致代理执行某些操作。定理证明和搜索的过程通过一个世界模型的空间被分开。Earl D Sacerdoti于1975年提出的NOAH(Nets Of Action Hierarchies)系统是HTN规划的第一个实现,HTN规划随后受到了广泛的研究和应用,2003年Dana Nau等学者提出的SHOP2规划系统获得了2002年国际规划竞赛中杰出表现的奖项之一,可以使用高度表达性的域表示,是重要的独立于域的HTN规划系统。

1992年,Kautz等人提出将规划问题转换为命题可满足(propositional satisfiablility,简称SAT)问题予以求解的规划方法。1996年,Kautz等人又设计了SATPLAN规划系统,这使得并发规划问题得以解决。1997年,Blum等人设计的Graphplan规划系统很好地解决了知识表示过程中的指数级空间爆炸问题,使得智能规划领域逐步得到相关研究者的重视。1998年,首届国际规划竞赛(International Planning Competition,简称IPC)举办,之后这一比赛使得智能规划技术得到了长足的发展。

年份

事件

相关论文/Reference

1971

Richard 和 Nils 开发出了STRIPS (一种自动规划器),这应该是第一个重要的规划系统 [6]

Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. Artificial intelligence, 2(3-4), 189-208.

1975

Earl Sacerdoti 在NOAH 系统中开发了偏序规划(Partial-order Planning)

Sacerdoti, E. D.(1975). A Structure for Plans and Behavior. Ph.D. dissertation, Standfor University, AI Center. aAI7605794.

1992

Kautz等人提出将规划问题转换为命题可满足(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.

1994

Cross 和 Walker 为交通调度应用开发了动态分析和重新规划工具(Dynamic Analysis and Replanning Tool /DART)

Cross, S. E.; Walker, E. (1994). Zweben, Monte; Fox, Mark S., eds.Intelligent Scheduling. University of Michigan: Morgan Kaufmann. pp. 711–729.

1996

1996年,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).

1997

Blum等人设计的Graphplan规划系统很好地解决了知识表示过程中的指数级空间爆炸问题

Blum, A. L., & Furst, M. L. (1997). Fast planning through planning graph analysis. Artificial intelligence, 90(1), 281-300.

2003

Dana Nau等学者对SHOP2进行了描述

Nau, D. S.; Ilghami, O.; Kuter, U.; Murdock, J. W.; Wu, D. and Yaman, F. (2003). SHOP2: An HTN Planning System. Journal of Artificial Intelligence Research. 20(1): 379–404.

2004

NASA 的火星探测器使用MAPGEN 规划日常运作

Ai-Chang, M. et al. (2004). MAPGEN: mixed-initiative planning and scheduling for the Mars Exploration Rover mission.IEEE Intelligent Systems. 19(1): 8-12.

2007

MEXAR2 为欧洲航天局(ESA)的火星快车任务执行logistic 规划和科学规划

Cesta, A. et al.(2007). Mexar2: AI Solves Mission Planner Problems.IEEE Intelligent Systems. 22(4): 12-19.

发展分析

瓶颈

规划的天生之敌是不确定性,这个问题有可能摧毁通过规划设计的整个流程。

未来发展方向

目前规划的主要应用领域是游戏,并且十分流行。规划的未来发展方向可能是智能风险管理领域,另外也可以预见规划在医学和机器人领域的应用。

Contributor:Yuanyuan Li, Mos Zhang 

相关机构
  • University of Maryland - College Park - PLUS group
  • Lehigh University - InSyTe Lab
  • Stanford - Artificial Intelligence Laboratory
  • Principles of Knowledge Representation and Reasoning, Incorporated (KR, Inc.)
  • Edinburgh Centre for Robotics
  • Copernican Group
相关人物
亨利·考茨
亨利·考茨
计算机科学家,美国国家科学基金会信息和智能系统部门主任,罗切斯特大学教授、数据科学研究所创始主任,AAAI、AAAS会士。研究兴趣:知识表示、人工智能、数据科学和普适计算。
戴纳·S·诺
戴纳·S·诺
AAAI、ACM Fellow,马里兰大学帕克分校计算机科学系教授、系统研究所教授、高级计算研究所Affiliate Professor,主要从事自动化规划与调度、博弈论、认知科学和计算机辅助工程方面的研究。他有许多博士生,包括1989年毕业的杨强。
厄尔·萨瑟多蒂
厄尔·萨瑟多蒂
企业家,管理顾问,高管教练,专注于早期软件风险投资的投资者。他有30多年的一般管理和研究、开发与工程管理经验。Sacerdoti是Symantec的创始人,他用18年时间运营Copernican Group,该集团是管理和技术顾问公司,致力于使先进软件技术投入现实应用。1970年代,Sacerdoti在斯坦福国际咨询研究所(SRI)人工智能中心担任研究数学家和副主任。曾在SoftTouch Systems、苹果等公司任职。 他还是美国人工智能学会(AAAI)联合创始人之一, Cognitive Science、Robotics World、AI Expert的前编辑部成员,著有大量有关前沿软件技术的论文和文章。
菲利普·沃尔夫
菲利普·沃尔夫
Philip Starr“Phil”Wolfe(菲利普·沃尔夫)(1927年8月11日 - 2016年12月29日)是美国数学家,也是凸优化理论和数学规划的创始人之一。1992年,他与Alan Hoffman一起获得了John von Neumann Theory奖。沃尔夫于1957年加入兰德公司,在那里他与乔治·丹齐格合作,开发了现在众所周知的Dantzig-Wolfe分解方法。
理查德·菲克斯
理查德·菲克斯
计算机科学家,斯坦福大学计算机科学系名誉退休教授。他于1991年至2006年期间领导斯坦福大学知识系统实验室,并曾在加州大学伯克利分校、卡内基梅隆大学,普华永道技术中心,施乐帕克研究中心(Xerox PARC)和SRI国际任职。他致力于开发在计算机系统中高效表示和使用知识的技术。他参与开发了STRIPS自动规划系统、Ontolingua本体表示语言和基于web的本体开发环境、用于访问知识服务器的OKBC API,以及IntelliCorp的KEE系统。
尼尔斯·约翰·尼尔森
尼尔斯·约翰·尼尔森
尼尔斯约翰尼尔森是美国计算机科学家。他是人工智能学科的创始人之一。他是斯坦福大学计算机科学工程专业的第一任Kumagai教授,自从1990年到1995年成立后担任主席。他因其在搜索,规划,知识表示和机器人方面的贡献而出名。 他的研究主要基于智力基于必须明确表示的知识的前提
简介
相关机构
相关人物