认真聊AI | 规划技术

原创内容

No.768

认真聊AI | 规划技术

AI系列内容进度13/15，完结在即

图片由夸克AI绘制

规划技术是人工智能领域中一个非常重要的分支，主要研究如何合理地选取行动或行动序列来完成具体任务。

规划技术通常有两大任务：①问题描述，如何方便地表示规划问题；②问题求解，如何高效地求解规划问题。在网络服务、智能机器人、自动驾驶等领域规划问题都有着非常广泛的应用。其中最为普及的地方则是地图的路径搜索规划，市面上所有的导航APP基本都是用到了规划技术。

规划方法一般可以分为三类：

①领域限定：针对具体领域专门设计的特定规划方法，通常利用领域特性设计更高效的算法。

②领域无关：不针对具体领域的通用规划方法，通常是对规划方法共性的研究。

③可配置：在领域无关方法的基础上，针对具体问题可以增加控制信息，从而利用问题领域特征使规划更高效。

人工智能的研究领域一般更加关注领域无关和可配置这两种方法。对于这两种方法来说，一般涉及两个问题：①问题描述，即定义描述语言，从而统一、便捷地表示各类领域无关的规划问题；②问题求解，即定义求解算法，高效求解所欲可以由描述语言刻画的规划问题。

规划问题非常复杂，为了简化问题，我们提出了一个经典规划基本假设：

A0有限系统：问题值涉及有限的状态、行动、事件等；

A1完全可观察：永远知道系统当前所在的状态；

A2确定性：每个行动只会导致一种确定的影响；

A3静态性：不存在外部行动，环境所有的改变都来自控制者的行动；

A4状态目标：目标是一些需要达到的目标状态；

A5序列规划：规划结果是一个线性行动序列；

A6隐含事件：不考虑时间持续性；

A7离线规划：规划求解器不考虑执行时状态。

虽然经典规划假设简化了现实中的问题，但依然比较复杂，并且现实中不可避免地具有不确定性，比如信息的不完全，外部事件不可预测，行动本身也是不确定的，这就要求了规划算法能够高效地分析各种动作各种可能的执行结果。

经典规划就是满足上面A0-A7所有假设的规划问题。

对于经典规划问题，我们通常会用一种通用的方法来紧凑地刻画系统状态和行动，并且用于搜索求解，比如有限合集和一阶逻辑符号的方法。

从求解上来说，经典规划的求解方法可以分为状态空间的求解和规划空间的求解。状态空间搜索是在状态转移图中搜索从初始状态到目标状态的一条路径，一般分为：

向前搜索

向后搜索

启发式搜索

面对现实中的问题，主体对于环境特征的把握常常是不完整的，正式由于这种只是的缺失，造成了不确定性，马尔可夫决策模型可以处理这类问题。

马尔可夫决策过程最基本的问题是一个由状态、行动、状态转移函数和报酬函数组成的四元组。其中状态集合表示所有问题所有可能世界状态的集合；行动集合表示问题所有可能行动的集合；状态转移函数表示在某个状态执行某个动作，而状态转移到另一个状态的概率；报酬函数表示在某个状态执行某个动作所能得到的立即报酬。

在马尔可夫决策模型下，系统与问题对应的环境进行交互，即系统在环境中执行一个行动，获知环境所有的新的当前状态，同时获得此次行动的立即收益。概率规划问题求解一般有两种方法，反向迭代类求解和前向搜索类求解两种。