AI 中的分层任务网络 (HTN)
Hierarchical Task Network (HTN) in AI
我无法理解 HTN 是什么。我相信的是,我们想把一个计划的所有小动作分解成一个更高层次的计划。
例如:
"Take bus" is an HLA of i.e. "go to bus", "buy ticket", "sit down" etc.
我错了吗?希望有一个简单的解释。
首先,分层任务网络是给定计划的解析器。在示例中,计划:
1 takebus
1.1 gotobus
1.2 buyticket
1.3 sitdown
可以针对 HTN-network 进行测试,它将回答请求:“计划有效”和“执行需要 30 分钟”。另一个计划稍微修改一下,也可以针对 HTN-network.
执行
围绕 ICAPS 会议的规划社区正在研究如何构建分层任务网络。他们经常使用 Prolog-dialect、PDDL 来创建复杂的行为树。例如,解析有关码头工人机器人问题的计划或解析来自 blocks world 域的计划。
其次,如果目标是为给定域找到最佳计划,则也使用术语分层任务网络计划。这里我们已经有了 PDDL 描述,我们有兴趣找到最短的计划。这在 control-tasks 中很有用,主要是为了自治 game-playing。
总的来说,分层任务网络是每个认知架构的基本构建块,这样说是正确的。它结合了游戏 AI 编程、知识工程和启发式规划等学科。
我知道这是一个旧的 post,但是我用头撞了很久,希望我学到的东西能节省别人的时间。
概括地说,HTN 使用以抽象和备选方案为中心的非常人性化的规划方法来解决问题。
备选方案:让我们使用著名的 SHOP HTN Planner (http://www.cs.umd.edu/projects/shop/description.html) 中的旅行示例。想象一下,你问我如何从市中心到公园。我可能会说,“好吧,它有 2 公里远,但如果外面天气好,我会步行过去。但是,如果下雨而且你有出租车费,我会坐出租车。否则,如果你有公交车费,就坐公交车吧。”你完成的一件抽象的事情,比如“从一个地方旅行到另一个地方”,在 HTN 中被称为“任务”。我给出的实现它的 3 个备选方案在 HTN 中被称为“方法”。请注意,每种方法都有一个与之相伴的“条件”:如果天气好就步行,如果有车费就坐出租车,等等
抽象:请注意,这 3 种方法处于相当高的抽象级别。您可能会进一步问我如何完成“TakeABus”方法。我会说类似的话,“好吧,在‘市区’公交车站等 1 路公交车,支付 driver 1 美元,然后乘车到‘公园’车站。”这三个任务在 HTN 中被称为“TakeABus”方法的“子任务”。在 HTN 中,方法通过分解为子任务来完成它们的工作。现在,这对人类来说是一个非常完整的答案,但如果我们与机器人交谈,则可能不是。在那种情况下,我们可能需要将“PayTheDriver$1”的任务进一步分解为“把手伸进口袋,拿一张 1 美元的钞票,交给 driver”。每一个都可以进一步分解,直到我们最终拥有机器人可以做的事情。 HTN 的最后一步,即实际完成的部分,称为“操作员”。在完成(并拥有 Operator)之前需要了解多详细取决于您正在构建的系统类型。设计 HTN 模型的很大一部分是了解正确的抽象是什么。
因此,HTN 具有以下部分:
世界现状:你在市中心。出租车费用为 2 美元。巴士票价为 1 美元。市区到公园距离为2Km。
任务:世界上可以抽象地完成什么(可能有几种方法!): 从 A 旅行到 B。从 A 步行到 B。支付 Driver X$。在B站等公交车A.
Operators:如何在无需进一步解释的情况下“完成”抽象任务。他们实际上改变了世界状况。如果你是人类,这些可能是操作员:支付 driver 1 美元,乘坐 #1 巴士到 'Park' 站。如果你是机器人,这些可能是:将步进电机向前移动 100 步,打开聚光灯
方法:当涉及多个步骤或更详细的计划时,如何完成抽象任务。他们有一个关于何时可以使用它们的条件和一组关于如何完成它们的子任务:方法:"Travel from A to B" 条件:天气不好,你有公共汽车票价,子任务:在公共汽车站等公共汽车, 付钱 driver, 骑车到站
算法本身非常简单。你从一个任务或目标列表开始,比如从市中心到公园和一个空的计划列表:
- 删除并从目标列表中的第一个目标开始
- 看看有没有Operator知道怎么做。如果是这样,将操作员添加到计划列表的末尾(因为操作员可以“完成”)并在 #1
处继续
- 看看有没有方法知道怎么做。如果是这样,将他们的子任务添加到我们的目标列表的前面,并继续 #1 如果有多种方法,请独立地复制当前世界状态和 运行 算法。每个成功完成的将是一个不同的解决方案
- 重复直到目标列表为空
- 完成后,计划列表中的内容就是解决方案
我有一个博客系列,非常详细地介绍了这一点,包括源代码和更多示例,如果您需要更多详细信息:https://blog.inductorsoftware.com/blog/htnoverview
我无法理解 HTN 是什么。我相信的是,我们想把一个计划的所有小动作分解成一个更高层次的计划。
例如:
"Take bus" is an HLA of i.e. "go to bus", "buy ticket", "sit down" etc.
我错了吗?希望有一个简单的解释。
首先,分层任务网络是给定计划的解析器。在示例中,计划:
1 takebus
1.1 gotobus
1.2 buyticket
1.3 sitdown
可以针对 HTN-network 进行测试,它将回答请求:“计划有效”和“执行需要 30 分钟”。另一个计划稍微修改一下,也可以针对 HTN-network.
执行围绕 ICAPS 会议的规划社区正在研究如何构建分层任务网络。他们经常使用 Prolog-dialect、PDDL 来创建复杂的行为树。例如,解析有关码头工人机器人问题的计划或解析来自 blocks world 域的计划。
其次,如果目标是为给定域找到最佳计划,则也使用术语分层任务网络计划。这里我们已经有了 PDDL 描述,我们有兴趣找到最短的计划。这在 control-tasks 中很有用,主要是为了自治 game-playing。
总的来说,分层任务网络是每个认知架构的基本构建块,这样说是正确的。它结合了游戏 AI 编程、知识工程和启发式规划等学科。
我知道这是一个旧的 post,但是我用头撞了很久,希望我学到的东西能节省别人的时间。
概括地说,HTN 使用以抽象和备选方案为中心的非常人性化的规划方法来解决问题。
备选方案:让我们使用著名的 SHOP HTN Planner (http://www.cs.umd.edu/projects/shop/description.html) 中的旅行示例。想象一下,你问我如何从市中心到公园。我可能会说,“好吧,它有 2 公里远,但如果外面天气好,我会步行过去。但是,如果下雨而且你有出租车费,我会坐出租车。否则,如果你有公交车费,就坐公交车吧。”你完成的一件抽象的事情,比如“从一个地方旅行到另一个地方”,在 HTN 中被称为“任务”。我给出的实现它的 3 个备选方案在 HTN 中被称为“方法”。请注意,每种方法都有一个与之相伴的“条件”:如果天气好就步行,如果有车费就坐出租车,等等
抽象:请注意,这 3 种方法处于相当高的抽象级别。您可能会进一步问我如何完成“TakeABus”方法。我会说类似的话,“好吧,在‘市区’公交车站等 1 路公交车,支付 driver 1 美元,然后乘车到‘公园’车站。”这三个任务在 HTN 中被称为“TakeABus”方法的“子任务”。在 HTN 中,方法通过分解为子任务来完成它们的工作。现在,这对人类来说是一个非常完整的答案,但如果我们与机器人交谈,则可能不是。在那种情况下,我们可能需要将“PayTheDriver$1”的任务进一步分解为“把手伸进口袋,拿一张 1 美元的钞票,交给 driver”。每一个都可以进一步分解,直到我们最终拥有机器人可以做的事情。 HTN 的最后一步,即实际完成的部分,称为“操作员”。在完成(并拥有 Operator)之前需要了解多详细取决于您正在构建的系统类型。设计 HTN 模型的很大一部分是了解正确的抽象是什么。
因此,HTN 具有以下部分:
世界现状:你在市中心。出租车费用为 2 美元。巴士票价为 1 美元。市区到公园距离为2Km。 任务:世界上可以抽象地完成什么(可能有几种方法!): 从 A 旅行到 B。从 A 步行到 B。支付 Driver X$。在B站等公交车A.
Operators:如何在无需进一步解释的情况下“完成”抽象任务。他们实际上改变了世界状况。如果你是人类,这些可能是操作员:支付 driver 1 美元,乘坐 #1 巴士到 'Park' 站。如果你是机器人,这些可能是:将步进电机向前移动 100 步,打开聚光灯
方法:当涉及多个步骤或更详细的计划时,如何完成抽象任务。他们有一个关于何时可以使用它们的条件和一组关于如何完成它们的子任务:方法:"Travel from A to B" 条件:天气不好,你有公共汽车票价,子任务:在公共汽车站等公共汽车, 付钱 driver, 骑车到站
算法本身非常简单。你从一个任务或目标列表开始,比如从市中心到公园和一个空的计划列表:
- 删除并从目标列表中的第一个目标开始
- 看看有没有Operator知道怎么做。如果是这样,将操作员添加到计划列表的末尾(因为操作员可以“完成”)并在 #1 处继续
- 看看有没有方法知道怎么做。如果是这样,将他们的子任务添加到我们的目标列表的前面,并继续 #1 如果有多种方法,请独立地复制当前世界状态和 运行 算法。每个成功完成的将是一个不同的解决方案
- 重复直到目标列表为空
- 完成后,计划列表中的内容就是解决方案
我有一个博客系列,非常详细地介绍了这一点,包括源代码和更多示例,如果您需要更多详细信息:https://blog.inductorsoftware.com/blog/htnoverview