人工智能中的经典规划

2025年4月1日 | 阅读9分钟

经典规划导论

在人工智能中，经典规划是指创建一系列步骤，在预定环境中，将起始状态转换为所需的目标状态。这种方法最适用于结构化和可预测的情况，因为它假定世界是明确定义的，并且所有可想象的状态、动作和后果都是已知的。在经典规划中，规划器使用通常由状态、目标、动作和转换模型组成的模型，来确定达到目标的最佳或最实际的方法。

基于启发式搜索策略（如 A* 和贪婪算法）以及 STRIPS（斯坦福研究所问题求解器）等算法至关重要，因为它们使规划器能够根据动作对目标的达成程度进行评估和选择。尽管经典规划有其优点，但它也有缺点，尤其是在处理现实世界中的不确定性或动态变化时。为了在复杂环境中解决这些困难，现代人工智能规划通常将概率方法和经典方法相结合。

经典规划在人工智能中的重要性

经典规划是人工智能的基石，它通过创建从起始状态到目标状态的动作序列，为机器提供了独立解决问题的框架和技术。其重要性在于它能够在清晰、可预测的环境中模拟复杂决策过程的能力，从而使人工智能系统能够以很少的人工干预来完成目标。在环境通常是结构化且状态和动作可以精确描述的领域，如机器人技术、物流和自动推理，这种方法已被证明是至关重要的。

STRIPS 和 A* 算法等经典规划方法使规划器能够系统地分解问题，从而确保在实现目标方面的效率和最优性。例如，在机器人技术中，经典规划通过确定达到目标位置的移动序列，实现精确的导航和操作任务。此外，经典规划原理为集成不确定性和适应性的更高级规划框架奠定了基础，从而为实际应用架起了桥梁。尽管在动态环境中存在局限性，但经典规划对于构建可靠、可解释的人工智能系统至关重要，尤其是在需要精度、安全性和可重复性的领域。

规划领域建模语言

人工智能规划中的领域建模语言，例如 PDDL（规划领域定义语言），用于表示规划问题。它们定义了初始状态、目标状态以及允许的动作或算子，这些动作或算子指导状态之间的转换。通过形式化这些组件，领域建模语言使规划器能够理解问题结构并搜索最优解。这种结构化方法使得算法能够更轻松地系统地探索动作序列，确保它们满足指定的条件并高效地实现期望的目标状态。

PDDL

人工智能规划中的领域建模语言，例如 **PDDL**（规划领域定义语言），用于表示规划问题。它们定义了初始状态、目标状态以及允许的动作或算子，这些动作或算子指导状态之间的转换。通过形式化这些组件，领域建模语言使规划器能够理解问题结构并搜索最优解。这种结构化方法使得算法能够更轻松地系统地探索动作序列，确保它们满足指定的条件并高效地实现期望的目标状态。

PDDL 等领域建模语言为描述人工智能规划问题提供了标准化的语法和结构。它们指定了环境的元素，包括初始状态和目标状态、动作以及状态转换的条件。通过这样做，它们支持各种规划系统之间的互操作性，并使规划器能够应用搜索可行或最优解的算法。这种形式化对于机器人、物流和自动控制等领域的复杂问题解决至关重要。

STRIPS

**STRIPS**（斯坦福研究所问题求解器）是经典规划中一种有影响力的领域建模语言和框架，是许多后续规划语言的基础。STRIPS 诞生于 20 世纪 70 年代，它引入了一种结构化的方法来表示规划问题，使用逻辑命题来描述状态，并使用算子来模拟改变这些状态的动作。每个状态由一组逻辑条件定义，而动作（算子）具有前提条件和效果，分别指定执行动作的要求和结果。

在 STRIPS 中，规划过程涉及选择和排序算子，以从初始状态转换到目标状态，并确保在应用动作之前满足所有前提条件。通过提供这种清晰、形式化的结构，STRIPS 实现了动作序列的系统化探索，并成为领域建模语言和人工智能规划算法后续进展的核心基础。

经典规划技术

传统人工智能规划技术的基础思想是环境是确定性的、静态的和完全可观测的。这意味着世界的潜在状态以及每个动作的结果都是完全被理解和可预测的。经典规划的目标是找到最佳的行动方案，即“计划”，以使一个代理从一个状态转移到另一个状态，同时满足所有需求和限制。

为了实现这一点，经典规划使用状态、目标和动作等形式化表示，每个都具有前提条件和效果。常用的策略包括启发式搜索方法（例如，A*、贪婪搜索）和 STRIPS（斯坦福研究所问题求解器）。例如，STRIPS 能够实现准确的动作建模和逐步的逻辑推理。对于环境变化很小或不存在的结构化情况（如解决谜题或机器人导航），这些策略非常有用，因为它们能够实现准确且可重复的解决方案。

经典规划算法通常分为状态空间搜索和规划空间搜索两种方法。状态空间搜索通过动作探索所有可能状态以达到目标，而规划空间搜索直接操作部分计划，迭代地优化它们，直到形成一个完整、满足目标的计划。

状态空间搜索

状态空间搜索是一种传统的规划方法，它通过检查环境可能存在的每种条件来寻找从初始状态到目标状态的路径。根据这种方法，每个状态都是环境的一个独特排列，动作是状态之间的变化。为了逐步接近目标并确保满足限制，规划器通过应用可用动作在该“状态空间”中移动。

状态空间搜索方法可分为前向搜索和后向搜索。前向搜索从初始状态开始，通过扩展动作来探索新状态，直到达到目标。相反，后向搜索从目标状态开始，通过识别可能导致它的动作向后工作，逐步移向初始状态。

状态空间搜索的常用算法包括广度优先搜索 (BFS)、深度优先搜索 (DFS)、A* 和贪婪搜索。这些算法在探索状态的方法上有所不同（例如，优先考虑最短路径或估计成本）。状态空间搜索在明确定义的确定性环境中非常有效，但由于可能的状态数量众多，它在复杂空间中可能计算量很大。

规划空间搜索

规划空间搜索是一种经典规划技术，它专注于通过直接操作部分计划来制定解决方案，而不是在环境中逐个状态导航。与探索所有可能状态的状态空间搜索不同，规划空间搜索从一个不完整或骨架化的计划开始，并对其进行迭代优化，添加或调整动作，直到完全满足目标要求。

在规划空间搜索中，规划器从一个高层次的计划大纲开始，指定了初始状态和目标状态，但中间动作未定义。通过一个称为*计划优化*的过程，规划器识别部分计划中的差距（未满足的子目标或条件），并引入动作来解决它们。这种方法通常遵循最小承诺策略，这意味着规划器仅在绝对必要时才添加动作，从而允许更大的灵活性和更少的约束。

常用技术包括偏序规划 (POP)，它允许动作在可能的情况下保持无序，从而减少依赖并实现并行化。规划空间搜索在具有众多可能状态的复杂环境中特别有用，因为它减少了穷举搜索的需要，并允许更灵活、更高效的计划生成。

示例

from collections import deque

def bfs(graph, start, goal):
    # Queue for BFS, starting with the starting node
    queue = deque([[start]])
    # Set to keep track of visited nodes
    visited = set()

    while queue:
        # Get the current path from the queue
        path = queue.popleft()
        # Get the last node in the path
        node = path[-1]

        # Check if the node has been visited
        if node in visited:
            continue

        # Mark the node as visited
        visited.add(node)

        # Check if the goal is reached
        if node == goal:
            return path

        # Add neighboring nodes to the queue
        for neighbor in graph.get(node, []):
            # Create a new path with the neighbor and add to the queue
            new_path = list(path)
            new_path.append(neighbor)
            queue.append(new_path)

    # If the goal is not reachable, return None
    return None

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Example usage
start_node = 'A'
goal_node = 'F'
path = bfs(graph, start_node, goal_node)
print("Path from {} to {}: {}".format(start_node, goal_node, path))   

输出

 
Path from A to F: ['A', 'C', 'F']

说明

这段 BFS 代码使用队列和图的邻接表表示来查找非加权图中的最短路径。`bfs` 函数接受三个参数：`graph`（一个字典，其中键是节点，值是邻居节点列表）、`start`（起始节点）和 `goal`（我们要到达的目标节点）。

**初始化：** 我们开始时初始化一个队列，其中包含以 `start` 节点开头的路径，并使用一个空集来跟踪已访问的节点。
**BFS 循环：** 算法遍历队列中的路径。对于每条路径，它会检查最后一个节点。如果节点已被访问，则跳到下一个。否则，将其标记为已访问。
**目标检查：** 如果路径中的最后一个节点与 `goal` 匹配，则将该路径作为结果返回。
**队列更新：** 对于当前节点的每个邻居，算法通过扩展当前路径创建一个新路径，并将其添加到队列中。

由于其逐层探索的特性，这种 BFS 方法确保在非加权图中找到最短路径。

归约到其他问题

经典规划可以有效地归约到已充分研究的计算机科学领域，如可满足性 (SAT) 和约束满足问题 (CSP)，并利用这些领域开发的先进求解器来实现高效规划。

例如，SatPlan 方法将规划问题转换为命题公式，然后使用 SAT 求解器进行求解。如果存在解决方案，则代表一个可行的计划。这种方法允许将最先进的 SAT 求解器创新应用于规划，从而提高性能和解决方案的质量。

类似地，经典规划可以被构建为约束满足问题 (CSP)，其中约束包括动作前提条件、效果和目标条件。CSP 求解器然后致力于满足这些约束，从而产生规划问题的解决方案。通过将规划归约到 SAT 和 CSP，经典规划利用了成熟的问题解决方法，实现了高效且可扩展的解决方案。

经典规划的应用

机器人学： 研究机器人运动和运动规划，以完成操作、装配和导航等活动。传统和现代规划技术都可以生成动作序列，使机器人能够在遵循预定的几何和时间结构的同时完成当前的任务。
制造业： 组织工厂和车间的工人和生产流程的流动。为了优化生产速度和资源利用率，经典规划用于制定更有效的任务分配、资源分配和工作流同步计划。
物流： 组织材料和产品的移动和交付。此外，在物流中，使用传统规划算法来确定物流运营的最佳路线、时间表和资源分配，这些算法考虑了时间、负载能力和交付需求等各种参数。
太空探索： 例如，创建任务时间表以及为漫游车和宇宙飞船订购。对于需要执行科学任务并遵守特定要求的航天器和漫游车（如电力、数据传输和地形导航），创建事件序列对于经典规划的目的至关重要。

结论

人工智能中的经典规划使用 STRIPS 和 PDDL 等结构化领域建模语言来形式化初始状态、目标状态和允许的动作，从而创建系统化规划的框架。状态空间搜索和规划空间搜索等技术提供了在可预测环境中探索动作和实现目标的方法。归约到其他已充分研究的领域，如可满足性 (SAT) 和约束满足问题 (CSP)，通过允许使用高效的 SAT 和 CSP 求解器，进一步增强了经典规划。SatPlan 和基于 CSP 的方法等技术利用了这些领域的进步，为复杂的规划任务提供了更强大的解决方案。总而言之，经典规划在领域建模以及归约到 SAT 和 CSP 的支持下，在人工智能中仍然是基础性的，它将结构化问题解决方法与强大的计算工具相结合。

下一主题土木工程中的人工智能

人工智能中的经典规划

经典规划导论

经典规划在人工智能中的重要性

规划领域建模语言