经典的AI规划问题是找出最短的action序列（一个规划）将初始的世界状态转化为目标状态。
状态（state）描述多个的变量。
行动（action）由以下值定义：
- 先决条件 (precondition)：动作执行之前的状态变量的值
- 作用 (effect)：一些状态变量在执行动作后的值
在正向规划（forward planning）中，搜索受到初始状态的约束，只使用目标作为停止准则，并且作为启发式的来源。在回归规划（regression planning）中，搜索受目标约束，只使用起始状态作为停止准则，并且作为启发式的来源。但是无论是哪种方式，都可以用约束来修剪不能到达的目标。这就是将规划问题转化为约束满足问题（constraint satisfaction problem, CSP）。
对于CSP，表示动作的特征称为动作特征（action features），表示状态的特征称为状态特征（state features）。
对于一个CSP问题，有很多约束：
- State constraints
- Precondition constraints
- Effect constraints
- Action constraints
- Initial-state constraints
- Goal constraints
来源：artificial intelligence, http://artint.info/html/ArtInt_208.html#id7
发展历史
Constraint satisfaction 问题最早的发展与《Consistency in network of relations》1977年Mackworth, A. K的工作。它在AI的几乎所有领域都有很多应用。简言之，约束满足问题（CSP）由一组变量组成，每个变量与有限域相关联，并且存在变量之间的一组约束。
随着人工智能的火热，CSP问题也引起了一些学者的注意。Lopez & Bacchus (2003) 主要集中于建模状态变量的推理（结合了effect和frame的约束）。
目前，许多实际问题可以被形式化为分布式的CSPs。许多现实生活问题是自然分布的，但其他大规模问题可以人为划分，以作为分布式问题来管理。如Salido, M. A., & Barber, F. 在2006年提出论文《Distributed CSPs by graph partitioning》(DisCSP),这是一个变量和约束分布在在多个自动化代理之间的CSP问题。
约束模型必须以找到满足初始模型constraint solvers的参数。新的模型需要新型的限制，如Barták, R.在《Dynamic global constraints in backtracking based environments.》提出的open global constraints。
一般的规划和调度的集成带来了新的挑战，推理技术的约束。例如， Laborie, P., & Rogerie, J.在2008年提出《 Reasoning with conditional time-intervals》资源约束resource constraints 应该假定optional activities。
Barták (2011)将规划看作是状态变量的同步变化。利用有限状态automata来描述每个变量的演化过程。他认为规划是在automata中找到同步路径。这也是一种基于TIMELINES的描述。Zhou, N. F., Barták, R., & Dovier, A.在2015年以tabled逻辑编程进行规划。
来源：WIKI ； URL：https://link.springer.com/content/pdf/10.1007/s10601-011-9109-4.pdf
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 1981 | Mackworth, A. K.提出Constraint satisfaction问题 | Mackworth, A. K. (1981). Consistency in networks of relations. In Readings in Artificial Intelligence (pp. 69-78). |
| 2003 | Lopez & Bacchus (2003) 主要集中于建模状态变量的推理（结合了effect和frame的约束）. | Lopez, A., & Bacchus, F. (2003, August). Generalizing graphplan by formulating planning as a CSP. In IJCAI (Vol. 3, pp. 954-960). |
| 2006 | Salido, M. A., & Barber, F.解决一个变量和约束分布在在多个自动化代理之间的CSP问题 | Salido, M. A., & Barber, F. (2006). Distributed CSPs by graph partitioning. Applied Mathematics and Computation, 183(1), 491-498. |
| 2008 | Laborie, P., & Rogerie, J.提出资源约束resource constraints 应该假定optional activities。 | Laborie, P., & Rogerie, J. (2008, May). Reasoning with Conditional Time-Intervals. In FLAIRS conference (pp. 555-560). |
| 2015 | Zhou, N. F., Barták, R., & Dovier, A.在2015年以tabled逻辑编程进行规划。 | Zhou, N. F., Barták, R., & Dovier, A. (2015). Planning as tabled logic programming. Theory and Practice of Logic Programming, 15(4-5), 543-558. |
发展分析
瓶颈
有时候，我们不是获得一个解决方案或者一个满足条件约束的优化方案，而是获得能获得一定健壮性和稳定性的方案。现在，很多规划调度问题都是动态的，它们找到的方案很快就会无效。一些的技术主要集中于修复原始的方案的同时，找到一些方案能够摒弃这些变化。然而在constraint programming中，对于健壮性和稳定性的理解还存在一些误解。在许多情况下，这些特性是混淆的，因此需要声明一些定义，并开发出合适的技术来保证这些特性。
未来发展方向
- 建模：建立一个好的模型不是一个简单的问题，它需要成百上千的变量约束。所以在建模语言中，表达性和易用性是基本属性。直到约束模型的自动生成工具得到充分开发和广泛使用。
- 分布式模型：现在很多问题可以被建模成分布式的CPS问题，是值得研究的领域
- 解法：随着新的模型的出现，新的约束条件也会应运而生。除此之外，对于规划和调度问题的整合会有新的挑战：对于这些约束的推理。
URL: https://link.springer.com/content/pdf/10.1007/s10601-011-9109-4.pdf
Contributor: Ruiying Cai