TSP问题中Effect表达式正确使用方法

偷偷努力，悄无声息地变强，然后惊艳所有人！哈哈，小伙伴们又来学习啦~今天我将给大家介绍《Python PDDL构建TSP：Effect表达式正确用法》，这篇文章主要会讲到等等知识点，不知道大家对其都有多少了解，下面我们就一起来看一吧！当然，非常希望大家能多多评论，给出合理的建议，我们一起学习，一起进步！

本文旨在指导用户在使用`pddl` Python框架构建旅行商问题（TSP）时，如何正确处理PDDL动作的`effect`表达式。通过分析常见的`RecursionError`，揭示了将PDDL逻辑表达式误用字符串拼接的错误，并提供了使用框架内置逻辑运算符（如`&`和`~`）来组合谓词的正确方法，以确保生成的PDDL领域和问题文件能够被Fast-Downward规划器正确解析。

引言：Python PDDL框架与旅行商问题

在人工智能规划领域，PDDL（Planning Domain Definition Language）是一种广泛使用的领域描述语言。pddl Python框架为开发者提供了一种便捷的方式，通过Python代码定义PDDL领域和问题，并将其转换为标准的PDDL文件，进而利用如Fast-Downward等规划器求解。旅行商问题（Travelling Salesman Problem, TSP）是经典的组合优化问题，其目标是找到访问一系列城市并返回起点的最短路径，每个城市只访问一次。将TSP建模为PDDL问题是展示该框架能力的一个良好用例。

问题描述与常见错误

在使用pddl Python框架实现TSP时，开发者可能会遇到一个常见的RecursionError，尤其是在定义动作（Action）的effect（效果）部分时。该错误通常发生在框架尝试验证PDDL结构的一致性时，表明某个PDDL表达式的构建方式不符合预期。

以下是导致该错误的典型代码片段，位于tsp_basic.py文件的create_actions方法中：

# 错误的Effect表达式构建方式
move = Action(
    "move",
    parameters=[self.start, self.finish],
    precondition=self.at(self.start) &
                 self.connected(self.start, self.finish) &
                 ~self.visited(self.finish),
    effect="&".join([
        str(self.at(self.finish)),
        str(self.visited(self.finish)),
        "~" + str(self.at(self.start))
    ])
)

当执行这段代码时，会抛出RecursionError: maximum recursion depth exceeded while calling a Python object。

错误根源分析

RecursionError的根本原因在于对PDDL表达式的误解和错误使用。pddl Python框架中的Predicate对象以及由它们组合而成的逻辑表达式（如self.at(self.finish)）本身就是Python对象，它们重载了逻辑运算符（如&用于AND，|用于OR，~用于NOT），使得可以直接在Python中以类似PDDL语法的方式构建复杂的逻辑结构。

然而，在上述错误示例中，effect参数被赋值为一个通过字符串拼接生成的字符串。例如，str(self.at(self.finish))会将Predicate对象转换为其字符串表示形式，然后通过"&".join(...)将这些字符串连接起来。框架期望effect是一个PDDL逻辑表达式对象（或其组合），而不是一个简单的字符串。当框架内部的类型检查器尝试解析这个字符串时，它无法将其识别为有效的PDDL逻辑结构，从而导致验证失败，并最终触发深度递归错误。

正确构建PDDL Effect表达式

要正确地构建PDDL动作的effect表达式，必须使用pddl框架提供的逻辑运算符来组合Predicate对象。这意味着我们应该直接使用&运算符来表示逻辑AND，~运算符来表示逻辑NOT。

以下是tsp_basic.py中create_actions方法effect部分的正确实现：

# 正确的Effect表达式构建方式
move = Action(
    "move",
    parameters=[self.start, self.finish],
    precondition=self.at(self.start) &
                 self.connected(self.start, self.finish) &
                 ~self.visited(self.finish),
    effect=self.at(self.finish) & self.visited(self.finish) & ~self.at(self.start)
)

通过这种方式，effect参数被赋予了一个由pddl.logic模块中的Predicate对象通过逻辑运算符组合而成的复合逻辑表达式对象。框架能够正确解析并将其转换为PDDL语法，例如：

(and (at ?finish) (visited ?finish) (not (at ?start)))

推广与注意事项

1. 一致性原则：这个原则不仅适用于effect，也适用于PDDL动作的precondition（前提条件）以及问题的goal（目标）状态。所有这些部分都应该使用pddl框架提供的Predicate对象和逻辑运算符来构建，而不是通过字符串拼接。

   例如，在create_problem方法中，构建goal状态时也存在类似的问题：

   # 错误的Goal状态构建方式
   goal_conditions = [self.visited(city) for city in self.cities if city.name != self.start_city]
   goal_conditions.append(self.at(variables(self.start_city, types=["position"])[0]))
   goal = "&".join(goal_conditions) # 错误：字符串拼接

   应改为：

   # 正确的Goal状态构建方式
   goal_conditions = [self.visited(city) for city in self.cities if city.name != self.start_city]
   goal_conditions.append(self.at(variables(self.start_city, types=["position"])[0]))
   # 使用pddl.logic.And来组合多个条件
   from pddl.logic import And
   goal = And(*goal_conditions) # 正确：使用And对象

   或者，如果所有条件都是PDDL逻辑表达式，可以直接使用&运算符链式连接（对于多个条件，使用And更清晰）。

2. PDDL要求（Requirements）：确保你的领域和问题文件声明了所有必要的PDDL要求。例如，如果使用了负面前提条件（~），则需要Requirements.NEG_PRECONDITION。如果使用了类型（types），则需要Requirements.TYPING。

3. 调试技巧：当遇到类似的错误时，检查涉及PDDL表达式构建的代码行。确认你正在传递PDDL逻辑对象而不是它们的字符串表示。可以使用type()函数来检查变量的类型，确保它们是pddl.logic模块中的相应对象。

完整的tsp_basic.py修正示例

# travelling salesman domain and problem basic case

from pddl.logic import Predicate, variables, And
from pddl.core import Domain, Problem
from pddl.action import Action
from pddl.formatter import domain_to_string, problem_to_string
from pddl.requirements import Requirements


class TSPBasic:
    def __init__(self, connections, start_city):
        self.connections = connections  # List of tuples representing connections between cities
        self.start_city = start_city  # Starting city from the TSP

        # Extracting unique cities from connections
        unique_cities = set()
        for start, end in connections:
            unique_cities.update([start, end])

        # 将城市名称转换为PDDL变量，并指定类型
        # 注意：variables函数返回一个列表，即使只有一个变量
        # 这里需要确保每个城市都作为一个PDDL常量或变量被正确定义
        # 为了简化，我们假设这些城市是问题中的对象，而不是动作参数中的变量
        # 因此，这里应该创建PDDL常量，而不是通用的变量
        self.city_objects = {city_name: variables(city_name, types=["position"])[0] for city_name in unique_cities}

        # Single city variables for actions (for parameters)
        self.start_param = variables("start", types=["position"])[0]  # Extract single city variable
        self.finish_param = variables("finish", types=["position"])[0]  # Extract single city variable

        # Predicates
        self.at = Predicate("at", self.start_param)
        self.connected = Predicate("connected", self.start_param, self.finish_param)
        self.visited = Predicate("visited", self.finish_param)

        self.domain = self.create_domain()
        self.problem = self.create_problem()

    def create_actions(self):
        move = Action(
            "move",
            parameters=[self.start_param, self.finish_param], # 使用动作参数变量
            precondition=self.at(self.start_param) &
                         self.connected(self.start_param, self.finish_param) &
                         ~self.visited(self.finish_param),
            # 修正：直接使用逻辑运算符组合谓词对象
            effect=self.at(self.finish_param) & self.visited(self.finish_param) & ~self.at(self.start_param)
        )
        return [move]

    def create_domain(self):
        requirements = [Requirements.STRIPS, Requirements.TYPING, Requirements.NEG_PRECONDITION]

        domain = Domain(
            "tsp_basic_domain",
            requirements=requirements,
            types={"position": None},
            # 在领域中声明所有可能的城市作为常量，或者在问题中作为对象
            # 这里我们选择在问题中作为对象，所以domain constants为空
            constants=[], 
            predicates=[self.at, self.connected, self.visited],
            actions=self.create_actions()
        )

        return domain

    def create_problem(self):
        requirements = [Requirements.STRIPS, Requirements.TYPING]

        # Define objects based on unique cities
        # 修正：直接使用 city_objects 中的 PDDL 变量作为问题对象
        objects = list(self.city_objects.values())

        # Initial state
        # 修正：使用 city_objects 中的 PDDL 变量来构建初始状态
        init = [self.at(self.city_objects[self.start_city])]
        for start, finish in self.connections:
            init.append(self.connected(self.city_objects[start],
                                       self.city_objects[finish]))

        # Goal state: all cities must be visited and return to start
        # 修正：使用And操作符组合所有目标条件
        goal_conditions = [self.visited(city_obj) 
                           for city_name, city_obj in self.city_objects.items() 
                           if city_name != self.start_city]
        goal_conditions.append(self.at(self.city_objects[self.start_city]))
        goal = And(*goal_conditions) # 正确：使用And对象组合

        problem = Problem(
            "tsp_basic_problem",
            domain=self.domain,
            requirements=requirements,
            objects=objects,
            init=init,
            goal=goal
        )

        return problem

    def get_domain(self):
        return domain_to_string(self.domain)

    def get_problem(self):
        return problem_to_string(self.problem)

对tsp_basic.py的其他修正说明：

1. 城市对象的处理：在原始代码中，self.cities被定义为variables(" ".join(unique_cities), types=["position"])，这会将所有城市名视为一个整体的变量列表。但在PDDL问题中，城市通常是作为具体的object存在的。为了更清晰和正确地处理，我修改为self.city_objects字典，将每个城市名称映射到其对应的PDDL变量对象。这样，在init和goal中引用具体城市时，可以直接通过self.city_objects[city_name]获取正确的PDDL对象。
2. 动作参数变量的区分：self.start和self.finish被重命名为self.start_param和self.finish_param，以明确它们是动作定义中的通用参数变量，而不是指代特定的城市对象。在create_actions中，parameters应使用这些通用变量。
3. Goal状态的修正：与effect类似，goal状态的构建也从字符串拼接改为了使用pddl.logic.And对象来组合多个谓词条件。

总结

在使用pddl Python框架时，理解其内部如何处理PDDL逻辑表达式至关重要。避免将PDDL逻辑表达式转换为字符串再进行拼接，而是直接利用框架提供的Predicate对象和重载的逻辑运算符（&, |, ~）来构建复杂的PDDL结构。遵循这一原则，可以有效避免RecursionError等类型错误，确保生成的PDDL领域和问题文件能够被Fast-Downward等规划器正确解析，从而顺利实现基于PDDL的规划任务。

到这里，我们也就讲完了《TSP问题中Effect表达式正确使用方法》的内容了。个人认为，基础知识的学习和巩固，是为了更好的将其运用到项目中，欢迎关注golang学习网公众号，带你了解更多关于的知识点！