Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

规划

人工智能领域的「规划」通常是指智能体执行的任务/动作的自动规划和调度,其目的是进行资源的优化。常见的规划方法包括经典规划(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 

简介