自动规划和调度（Automated planning and scheduling），有时简称AI规划（AI Planning），是人工智能的一个分支，涉及战略或动作序列的实现，通常由智能代理，自动机器人和无人驾驶车辆执行。 与经典控制和分类问题不同，解决方案很复杂，必须在多维空间中发现和优化。 规划也与决策理论有关。
在具有可用模型的已知环境中，可以离线完成计划。 可以在执行之前找到并评估解决方案。 在动态未知的环境中，策略通常需要在线修改。 必须调整模型和政策。 解决方案通常采用人工智能中常见的迭代试验和错误过程。 这些包括动态编程，强化学习和组合优化。 用于描述计划和日程安排的语言通常称为动作语言。
概观
给出对世界可能的初始状态的描述，对期望目标的描述，以及对一组可能的动作的描述，规划问题是综合保证的计划（当应用于任何初始状态时）生成包含所需目标的状态（这种状态称为目标状态）。
规划的难度取决于所采用的简化假设。 可以根据问题在多个维度中具有的属性来识别几类规划问题。
这些行动是确定的还是不确定的？ 对于非确定性操作，相关概率是否可用？
状态变量是离散的还是连续的？ 如果它们是离散的，它们是否只有有限数量的可能值？
可以毫无疑问地观察当前的状态吗？ 可以有完全可观察性和部分可观察性。
有多少初始状态，有限或任意多？
行动有持续时间吗？
是否可以同时采取多项措施，或者一次只能采取一项措施？
计划的目标是达到指定的目标状态，还是最大化奖励功能？
是否只有一个代理商或有几个代理商？ 代理人是合作的还是自私的？ 是否所有代理商都单独构建自己的计划，还是为所有代理商集中构建计划？
最简单的规划问题，称为经典规划问题，由以下因素决定：
一个独特的已知初始状态，
持续时间的行动，
确定性行动，
一次只能一个，
和一个代理人。
由于初始状态是明确已知的，并且所有动作都是确定性的，因此可以准确地预测任何一系列动作之后的世界状态，并且可观察性问题与经典规划无关。
此外，计划可以被定义为动作序列，因为事先总是知道需要哪些动作。
使用非确定性操作或代理控制之外的其他事件，可能的执行形成树，并且计划必须为树的每个节点确定适当的操作。
离散时间马尔可夫决策过程（MDP）正在计划以下问题：
持续时间的行动，
具有概率的不确定行为，
完全可观察性，
最大化奖励功能，
和一个代理人。
当完全可观察性被部分可观察性取代时，计划对应于部分可观察的马尔可夫决策过程（POMDP）。
如果有多个代理，我们有多代理规划，这与博弈论密切相关。
领域独立计划
在AI Planning中，规划人员通常输入域模型（对域建模的一组可能操作的描述）以及由初始状态和目标指定的特定问题，而不是那些没有的域模型。输入域指定。 这些规划者被称为“领域独立”，以强调他们可以解决来自广泛领域的规划问题。 域的典型示例是块堆叠，物流，工作流管理和机器人任务规划。 因此，单个域独立规划器可用于解决所有这些不同域中的规划问题。 另一方面，路线规划器是特定于域的规划器的典型。
规划域建模语言
用于表示规划域和特定规划问题的最常用语言（如STRIPS和经典规划的PDDL）基于状态变量。 世界的每个可能状态都是对状态变量的值的赋值，并且动作确定在采取该动作时状态变量的值如何变化。 由于一组状态变量会引起一个状态空间，该状态空间的大小在集合中具有指数，因此，与许多其他计算问题类似，计划受到维数灾难和组合爆炸的影响。
用于描述规划问题的替代语言是分层任务网络，其中给出了一组任务，并且每个任务可以通过原始动作实现或者分解成一组其他任务。 这不一定涉及状态变量，尽管在更现实的应用中，状态变量简化了任务网络的描述。
规划算法
经典规划
前向链状态空间搜索，可能通过启发式增强
反向链接搜索，可能通过使用状态约束来增强（参见STRIPS，graphplan）
偏序规划
经典策划
传统规划基于两个假设：
行动的决定论。 例如，“将多维数据集放在桌面上”的操作是确定性的。 通过执行它，我们从一个州移动到另一个州。 相反，“滚动骰子”是不确定的，因为有可能的值。 “掷骰子”行动不属于传统规划的范畴。
完美的观察。 代理人（机器人，程序等）完全了解世界的状况。
经典计划，这是一个寻找一系列行动的问题（例如，“拿一个锅”，“放水”，“放意大利面”，“点燃火”，“达到”，“推出火”）。 A *算法是经典规划算法的典型示例，由于其简单性，常用于入门课程。 以下是经典规划师使用的一些算法技术：
状态空间中的前向搜索：启发式搜索规划（HSP）算法，快进算法（FF），
在州空间中搜索，
之前在计划空间中的搜索，graphplan
放松规划问题：计算一个放松的问题，如果有一个计划可以帮助解决最初的问题，那么更容易知道
转化为命题逻辑公式的可满足性问题。
Bylander在1994年证明了传统的规划是PSPACE完成的。
减少其他问题
减少命题可满足性问题（satplan）。
简化为模型检查 – 两者本质上是遍历状态空间的问题，而经典规划问题对应于模型检查问题的子类。
时间规划
时间规划可以用类似于经典规划的方法来解决。 主要区别在于，由于可能存在多个时间上重叠的动作并且持续时间同时进行，因此状态的定义必须包括关于当前绝对时间的信息以及每个活动动作的执行进行了多远。 此外，在理性或实时规划中，状态空间可能是无限的，与经典规划或整数时间规划不同。 时间规划与调度问题密切相关。 时间规划也可以用定时自动机来理解。
概率规划
当状态空间足够小时，可以使用迭代方法（例如值迭代和策略迭代）来解决概率规划。 在部分可观察性的情况下，概率规划同样用迭代方法求解，但使用为信念空间而不是状态定义的值函数的表示。
基于偏好的计划
在基于偏好的计划中，目标不仅是制定计划，还要满足用户指定的偏好。 与更常见的基于奖励的计划的差异，例如对应于MDP，偏好不一定具有精确的数值。
有条件的计划
STRIPS规划系统引入了确定性规划，该系统是一个分层规划器。 动作名称按顺序排序，这是机器人的计划。 可以将分层规划与自动生成的行为树进行比较。 缺点是，正常行为树不像计算机程序那样具有表现力。 这意味着，行为图的表示法包含动作命令，但没有循环或if-then-statements。 条件规划克服了瓶颈，并引入了一个类似于控制流程的详细记法，从Pascal等其他编程语言中可以看出。 它与程序合成非常相似，这意味着计划程序生成可由解释程序执行的源代码。
有条件的计划者的早期例子是在20世纪70年代中期引入的“Warplan-C”。 到目前为止，问题还没有解决正常序列和包含if-then-statements的复杂计划之间的区别。 它与计划运行时的不确定性有关。 这个想法是，计划可以对计划者未知的传感器信号做出反应。 计划者提前生成两个选择。 例如，如果检测到对象，则执行动作A，如果缺少对象，则执行动作B. 条件计划的一个主要优点是能够处理部分计划。 代理不会被迫从头到尾计划一切，但可以将问题分成块。 这有助于减少状态空间并解决更复杂的问题。
规划系统的部署
哈勃太空望远镜使用一种称为SPSS的短期系统和一种名为Spike的长期规划系统。
其他类型的规划
在实践中，它只检查很少的经典计划假设。 这就是出现许多扩展的原因。
符合规划
我们谈论系统处于不确定状态的符合规划（符合时间表），但不能进行观察。 然后代理人对现实世界抱有信念。 这些问题通过类似于传统规划的技术来解决，但是由于当前状态的不确定性，状态空间在问题的大小上是指数级的。 符合计划问题的解决方案是一系列动作。
应急计划
可通过传感器观察环境的应急计划（或有计划），这可能是错误的。 对于偶然计划问题，计划不再是一系列行动而是决策树，因为计划的每个阶段都由一组状态表示，而不是像经典计划那样单一的完全可观察状态。
Rintanen在2004年证明，如果增加分支（或有计划），规划问题就变成了EXPTIME -complete。 连续计划的一个特例是问题FOND – “完全可观察和非确定性”。 如果在LTLf（有限迹线上的线性时间逻辑）中指定目标，那么对于LDLf中的目的规范，问题始终是EXPTIME-complete 16和2EXPTIME-complete。
此外，如果增加传统规划（即合规规划）的不确定性，则变为EXPSPACE -complete。 如果我们同时添加分支和不确定性（规划兼容和偶然），它将成为2EXPTIME完成。
概率规划
Kushmerick等人。 介绍了概率规划。 在他们的工作中，动作的效果用概率论者描述。 他给出了以下方式描述的“机器人采取阻挡”动作的例子：如果机器人的抓手是干的，那么机器人以0.95的概率保持该块; 如果夹子是湿的，则机器人以0.5的概率保持块。
这导致马尔可夫决策过程（MDP）或（在一般情况下）部分可观察马尔可夫决策过程（POMDP）的策略生成（或策略）问题。
非线性规划
经典计划以给定顺序解决子目标。 问题是它有时会导致破坏已经建成的东西。 这种现象被称为Sussman异常。
假设赤脚的个人应该穿着他的右鞋，左鞋，右袜子和左袜子。 如果他试图按照话语的顺序实现目标，他就会失败。
为了解决这类问题，可以转向部分有序的计划，其中行动之间的顺序仅在必要时才得以确定（最新承诺或承诺最少的承诺）。
在前面的例子中，左脚袜应该在放下袜子后完成。 右边也一样。 另一方面，左侧计划的执行与权利的执行无关。 因此整体计划部分订购。
能够处理这类问题的计划者被称为部分订单（POP，NOAH等）。
分层规划
通常，在计划时，可以具有关于动作的分层信息，即关于如何分解复杂动作的描述。 例如，像“提供咖啡”这样的复杂动作可以分解为“制作咖啡”然后“带来咖啡”的两个复杂动作的顺序。 因此，有一些规划者，如ABSTRIPS，除了对动作的描述之外，还将动作的层次描述作为输入。 例如，可以开始在高级别进行计划，然后在必要时进入细节（例如ABSTRIPS）。 然后使用分层任务网络（HTN）描述目标。
时间规划
时间计划允许您表达行动时间，开始，结束和行动期间的条件，以及行动开始和结束时的效果。 PDDL 2.1包括时间规划。 TLP-GP 1方法构造图形，然后使用SMT求解器求解时间约束。 在出现不一致的情况下进行一次反击。 Rintanen已经证明并发时间规划（可能是同一并行动作的多个实例）是EXPSPACE完成的。 另一方面，如果我们放松这些条件，我们可以将自己简化为常规规划，因此使用这些限制的时间规划将成为PSPACE完成。
总体规划
总体规划包括制定适用于多个起始环境的计划。
多代理规划
多代理调度研究多个代理（例如，多个机器人）完成任务。 然后，计划的生成及其执行通常是分布式/分散式的。 计划的一个重要方面是代理商之间的合作。 还有一种集中式调度算法，它依赖于将STRIPS概括为多代理框架，称为MA-STRIPS。 然后使用分布式求解器CSP对该算法进行分布式渲染，以管理代理之间的协调。 作者Nissim，Brafman和Domshlak已经通过实验验证，当代理彼此之间几乎没有交互时，他们的算法优于集中式调度。
多智能体规划的一个主要困难是所有动作的组合爆炸，这是代理数量的指数。 2011年，Jonsson和Rovatsos提供了一个解决这个问题的解决方案，减少了经典的单一代理规划。 还有一种更新的使用并行化技术，用于规划算法以进行扩展。
认识规划
认知规划问题是在描述状态和行动时考虑代理人的知识。 通常，目标是认知模态逻辑的公式，例如“代理知道块C在块A上的代理b”，并且动作用逻辑动态认知的动作模型表示。 规划问题的一般性是不可判定的。
目标：
高于（A，B）Λ高于（B，C）
初始状态：
[以上（A，表）Λ以上（B，表）Λ以上（C，A）Λ锁（A）Λ锁（B）Λ锁（C）Λ公开（B）Λ公开（C）]
可用操作：
移动（b，x，y）
预处理：上方（b，x）Λ未覆盖（b）Λ未覆盖（y）Λ块（b）Λ块（y）Λ（b≠x）Λ（b≠y）Λ（x≠y）
附加：上方（b，y）Λ发现（x）
取消：上方（b，x）Λ发现（y）
Move_tool（b，x）
预设：上方（b，x）Λ未覆盖（b）Λ未覆盖（y）Λ区块（b）Λ（b≠x）
附加：上方（b，表）Λ发现（x）
取消：上面（b，x）
例
计划的非正式例子。
目标
在冰箱里放一些水果和蔬菜
初始状态
[空冰箱，在家里，拖鞋]
可用操作（无序列表）
出门回家
穿鞋，
拿车钥匙，
开车到达商店，
步行到达商店，
回家吧
将购买物放入冰箱，
进入商店，
吃水果，
拿蔬菜，
支付。
可能的解决方案（有序列表
[1-穿鞋，2-取车钥匙，3-出门，4-开车到店，5-进店，6-取水果，7-取蔬菜，8-付， 9-回到家里，在冰箱里购买10个地方]
另一种可能的解决方案（有序列表）
[1-穿鞋，2-出门，3-步行到商店，4-进入商店，5-吃蔬菜，6 – 吃水果，7-付费，8-回家，9-位购买在冰箱里]
结论
从示例中我们可以看到：
解决方案可以是多个，
可能存在必须执行的动作，不可避免地，在其他人之后（如果我之前没有拿到钥匙，我无法驾车到达商店），
可能存在可逆行为（采取水果和蔬菜），
最终计划不必包含多个动作或可互换动作序列（步行或乘车到达商店）的所有动作。