机器人软件与具身智能 · 专栏六:任务决策与行为组织 · 第 3 篇

状态机和行为树回答了怎样执行一组动作。本篇继续追问:动作顺序从哪里来?用一份明确的世界模型,搜索、验证并比较不同计划。

“把玩具放进收纳筐”只有目标,没有动作顺序。八界要先到货架附近,确认目标,再夹取、移动、打开收纳筐、放下。若盖子已经打开,其中一步可以省略;若玩具已在夹爪中,再执行一次夹取反而不合理。

把所有条件组合写成固定脚本,很快会出现大量分支。任务规划换了一种表达方式:描述当前事实、可用动作以及最终要满足的条件,让搜索器在这个模型里寻找一条可行的动作序列。

这里最重要的约束是“在这个模型里”。规划器不会因为动作叫 pick 就自动懂得摩擦,也不会因为计划里写了 holding 就让夹爪真的抓住物体。先把符号层讲准确,下一篇再把连续几何条件接回来。
在这里插入图片描述

图 1|目标描述最终关系,动作模型描述哪些事实允许执行、执行后哪些事实改变。

1. 世界状态不是阶段名字,而是一组同时成立的事实

上一篇的 GRASPING 是控制阶段;本篇的 at:shelf、toy:shelf、hand:empty 是世界事实。八界可以同时位于货架前、手里为空、看见玩具,这些事实没有必要被拼成一个长状态名。

示例初始状态为:

s0 = {at:home, toy:shelf, hand:empty}
goal = {toy:bin}

为了在普通电脑上清楚复算,本例只有一个机器人、一个玩具和三个已命名位置,动作均已实例化。事实使用 frozenset 保存,既不能被搜索分支就地修改,也可以作为字典键,判断是否再次到达相同状态。

在这个经典规划模型里,未列出的事实按假处理;这是一种封闭世界约定。真实八界的相机暂时没看见玩具,通常只说明未知,并不直接等价于玩具不在货架上。感知到规划状态的转换必须明确处理这种区别。否则搜索器即使完全正确,也只是在错误输入上求解。

2. 前置条件与效果怎样构成状态转移

STRIPS 风格动作可以写成 a=(Pre,Add,Del,c),分别表示前置条件、增加事实、删除事实和非负代价。动作可用当且仅当 Pre⊆s;执行预测为:

γ(s,a) = (s \ Del(a)) ∪ Add(a)

本例的 pick 要求八界已经到货架、玩具仍在货架、手为空并已获得可见目标;增加 holding:toy,删除 toy:shelf 和 hand:empty。这个删除步骤直接表达了物体从货架转到手中的关系。
在这里插入图片描述
图 2|抓取效果同时增加和删除事实,未被效果提及的事实保持不变。

对应到 Action.apply(),只有四行:

def apply(self, state):
    if not self.pre <= state:
        return None
    return (state - self.delete) | self.add

None 表示当前状态不满足动作前置条件,搜索器应跳过这条边;它不是“动作执行后没有返回内容”。返回的集合是新状态,原状态保留给其他搜索分支。delete 与 add 在构造时检查互不相交,避免模型本身对同一事实提出矛盾效果。

这段代码的短,并不代表建模简单。例如 visible:toy 在本例观察后一直保留,便于展示确定性规划;真实观察会过期,物体也会移动。时效应在执行层复核,或进入更丰富的时间、知识模型,不能指望一次符号增加永久代表可用的三维目标。

3. 搜索器怎样知道先展开哪条路

六个动作分别是 go_shelf、observe、pick、go_bin、open_bin、place,代价为 2、1、2、2、1、1。代价单位是本例设定的无量纲评分,不是八界实测秒数。

search() 使用统一代价搜索。队列元素保存累计代价、稳定排序号、当前事实集合和到达这里的计划;best[state] 记录到达同一状态已经找到的最低代价。

下面把这段搜索函数完整列出,重点看成功检查、预算与后继生成:

def search(initial, goal, actions, max_expansions=1000, unit_cost=False):
    """Uniform-cost search; unit_cost=True demonstrates shortest action count."""
    serial = count()
    queue = [(0, next(serial), initial, [])]
    best = {initial: 0}
    expanded = 0
    trace = []
    while queue:
        score, _, state, plan = heappop(queue)
        if score != best[state]:
            continue
        if goal <= state:
            costs = {a.name: a.cost for a in actions}
            return {"status": "FOUND", "plan": plan,
                    "cost": sum(costs[name] for name in plan),
                    "expanded": expanded, "trace": trace}
        if expanded >= max_expansions:
            return {"status": "BUDGET_EXHAUSTED", "expanded": expanded, "trace": trace}
        expanded += 1
        trace.append({"state": sorted(state), "score": score, "plan": plan})
        for item in actions:
            successor = item.apply(state)
            if successor is None:
                continue
            candidate = score + (1 if unit_cost else item.cost)
            if candidate < best.get(successor, float("inf")):
                best[successor] = candidate
                heappush(queue, (candidate, next(serial), successor, plan + [item.name]))
    return {"status": "NO_PLAN_IN_FINITE_MODEL", "expanded": expanded, "trace": trace}

每次取累计代价最小的未失效队列项。找到满足目标的状态时,返回动作序列;尚未到目标时,先检查本次搜索预算,再尝试所有适用动作。

candidate < best.get(...) 的严格小于有两个作用:代价更低才更新,零代价或无变化的循环不会让相同状态无休止入队。队列中的旧条目可能在更优路径出现后过时,所以前面的代码还会比较弹出值与 best[state],跳过旧条目。
在这里插入图片描述
图 3|队列按累计代价比较候选路径;同一事实集合只保留更便宜的到达方式。

本次运行得到:

go_shelf → observe → pick → go_bin → open_bin → place
动作数:6
累计代价:9
展开的非目标状态数:10

在有限状态、非负代价、搜索未被预算截断等条件下,统一代价搜索返回总代价最小的计划。本例先检查目标,再检查展开预算,因此已经从队列取出的目标不再消耗一次非目标展开额度。输出中的 expanded 也按这个定义计数,不能跨实现随意比较搜索效率。

4. “动作更少”与“代价更低”什么时候不同

单独构造一个反例:直接方案只需一步,代价 9;绕行方案需要三步,每步代价 1。如果把每条边一律记作 1,搜索会选择一步的直接方案;按原始代价搜索,则选择总代价 3 的三步方案。
在这里插入图片描述

图 4|最少动作数选择直接方案,最低总代价选择三步方案;优化目标不同,正确答案也不同。

这对八界很实际。一次“大动作”可能需要重定位和大范围运动,几个局部动作却更便宜;反过来,频繁停顿与重新观察也可能让短距离方案更慢。代价函数要反映业务真正关心的量,并交代权重。如果把时间、能耗和失败风险混合,应说明各项如何归一化,而不是只给出一个“更优评分”。

本例 unit_cost=True 只是用于复算最少动作数的对照,不宣称处理概率风险、时间并行或连续路径代价。搜索算法可以保证的是所输入目标函数下的结果,不能替建模者决定什么叫好任务。

5. 删除效果漏掉一个,规划为什么还能“成功”

把 pick 的 delete 集合改为空,预测状态会同时出现:

toy:shelf、holding:toy、hand:empty

搜索器看到的只是布尔事实,它不会自动知道这三者互相冲突。程序甚至可能继续找到包含 toy:bin 的终点,看起来任务已经完成。

因此示例增加独立的模型不变量:玩具只应位于货架、夹爪或收纳筐中的一个位置,空手与持有玩具应互斥。检查函数也很短:

def toy_invariant(state):
    locations = {"toy:shelf", "holding:toy", "toy:bin"}
    return len(state & locations) == 1 and (("hand:empty" in state) == ("holding:toy" not in state))

在这里插入图片描述

图 5|达到目标事实不自动保证所有中间状态一致,物体位置互斥需要单独检查。

这里还需要一个独立计划验证器。[3] validate() 从初始状态重放完整动作序列,逐步检查前置条件,最后检查目标。删除最后一步,得到 GOAL_MISSING;直接“到货架、抓取”而跳过观察,在第 2 个动作处返回 PRECONDITION,缺少 visible:toy;填入未知动作名则返回 UNKNOWN_ACTION。

验证器没有信任搜索器给出的成功标签,但它仍共享同一动作模型。模型有错时,两者可能一起给出错误预测。因此完整工程检查需要同时覆盖“算法是否遵守模型”和“模型是否符合任务事实”,两种检查不能互相替代。

6. PDDL 是描述语言,HTN 是另一种组织搜索的方法

随文的 domain.pddl 表达六个动作和谓词,problem.pddl 表达初始状态、目标和累计代价指标。它们与 Python 中的动作表对应;Python 示例本身不解析 PDDL,也不调用外部规划器。Unified Planning 的 PDDLReader/PDDLWriter 则提供真实语言读写入口。[1]

以 pick 为例,PDDL 文件里的前置条件和效果仍然是刚才的关系。为了让读者优先看懂语义,本例使用没有参数的已实例化动作。多个玩具、多个位置时,通常需要类型、对象和参数化动作,再由规划系统处理实例化;不应把每个物体复制成整份新代码。

HTN 的入口则不是单一目标事实,而是需要完成的任务网络。比如 collect 可以通过“直接取物”或“先观察再取物”两种方法分解。方法提供任务结构,最终仍必须落到可执行的基本动作。SHOP 系列与 GTPyhop 是这种思路的重要实现资料;GTPyhop 同时扩展了目标与任务规划能力。[2]

本例只做全序 HTN,待办任务是一张有顺序的列表。看看 htn() 的方法分支:

# ... 前文省略,仅摘录当前分支
        for name, subtasks in methods.get(task, []):
            trace.append({"method": name, "result": "TRY"})
            result = visit(state, list(subtasks) + tail, plan, depth + 1)
            if result is not None:
                return result
            trace.append({"method": name, "result": "BACKTRACK"})
        return None

    # ... 后续分支见完整脚本

选择一个方法后,把它的子任务放到剩余任务之前。若某个基本动作的前置条件不成立,递归返回失败,尝试下一方法。状态采用不可变集合,所以回溯到另一个方法时不会继承失败分支修改的对象。
在这里插入图片描述

图 6|第一种方法在 pick 前置条件处失败,第二种方法加入 observe 后完成分解。

实际输出中能看到 skip_observation → PRECONDITION_FAILED → BACKTRACK,之后 observe_then_collect 返回六个动作。这个小实现按方法声明顺序做深度优先选择,不保证代价最优,也不完整实现一般 HTN 的偏序约束、方法前置条件或递归规划能力。

方法越具体,搜索可能越快,但设计者也预先排除了某些动作组织方式。若所有方法都失败,只能说明当前方法库与预算没有得到计划,不能直接推出机器人在物理世界绝无办法。

7. 搜索失败、模型无解与执行失败要分开

示例区分两种搜索退出:展开预算为零,返回 BUDGET_EXHAUSTED;对有限模型搜索穷尽仍无法达到目标,返回 NO_PLAN_IN_FINITE_MODEL。第一个是计算过程被截断,第二个才是对当前有限符号模型的结论。

执行失败又是另一层。pick 的效果预测产生 holding:toy,但八界夹爪实际闭合后可能没有夹住。此时应由观测更新实际任务状态;下一条 place 的前置条件不能引用“计划里原本应该发生的 holding”。
在这里插入图片描述

图 7|模型效果是预测,执行后的事实需要观测确认;预测不能直接覆盖失败反馈。

以完全已知、确定性状态为前提的经典规划,有利于清楚分析动作关系。面对遮挡、失败概率和未知环境时,还可能需要重规划、条件计划或显式信念状态。本篇先把这条边界留清楚,不给简单集合搜索套上完整不确定决策的名字。

8. 从哪个函数开始读代码

完整脚本 与 运行说明 中保留八组实验。先读 ACTIONS,手算一次 pick.apply();再读 validate(),确认每个动作为什么合法;最后看 search() 的优先队列与 htn() 的方法回溯。

python3 03_task_planning.py
python3 03_task_planning.py --json

可以做三个小修改:将初始状态加入 bin:open,看计划是否省掉开盖;删除 pick 的删除效果,看不变量能否抓住问题;将搜索预算设为 0,确认输出没有把预算耗尽写成物理无解。每个修改只改变一个因素,更容易判断结果来自哪条规则。

八界收纳的候选动作顺序至此已经有了。但 pick 还缺少夹爪朝向、底盘站位、升降高度与无碰撞路径。下一篇会让任务规划与运动检查互相交换约束,看看为什么逻辑上成立的计划仍可能在几何层被推翻。

八界相关代码将逐步释放,实际开放内容以科沃斯八界 AtomGit 为准。

参考链接

  1. Unified Planning 1.2:PDDL 读写示例。用于区分领域、问题文件和真实解析接口。
  2. Dana Nau 等:GTPyhop。作者维护的目标与任务规划实现,可继续阅读方法分解和基本动作的关系。
  3. Unified Planning 1.2:基础建模、求解与计划验证。提供将模型、求解器与验证器分开的完整示例。
Logo

DAMO开发者矩阵,由阿里巴巴达摩院和中国互联网协会联合发起,致力于探讨最前沿的技术趋势与应用成果,搭建高质量的交流与分享平台,推动技术创新与产业应用链接,围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐