在 Unity 中开发HTN Planner (1)

HTN Planning（Hierarchical Task Network）

在自认为了解了HTN的基础概念后，开始着手开发起了该AI框架，忘了是谁说的话：“只有创造出某个东西，我才可以说我了解这个东西”。实践出真知嘛，在动手之后，原以为挺简单的，没想到在一些细节的地方卡关了。因此记录下来，顺便理清一下思路。

HTN Planning（Hierarchical Task Network）

所谓HTN，即分层任务网络，是基于任务设计的AI架构，其设计思路是通过寻找合适的方法不断分解任务，直到该任务无法分解，即得到一组基元任务的序列，该基元任务序列便是原始任务的一个可行解决方案，当过程中出现没有任何方式可以分解一个复合任务时，分解失败，则该任务在当前的世界状态下无法执行。

在实现过程中，需要考虑几个概念，以及它们组件的关系

定义域
任务
- primitive task:基元任务，不可分解。有直接的行动与其对应
- compound task:复合任务，可分解，不同的方法，有不同的分解方式，即会产生不同的子任务
方法(Method)
- Name:
- Precondition:
- Subtasks:
行动（Action）:直接可执行的行动
- Name:
- Paramt:参数
- Preconditions:前提条件
- Effects:效果

在实现是，发现几处的概念还是有点不明白，即

如何把传递参数给行动
条件判断有哪些判断方式

如，这一次用来测试的问题是传教士和食人族过河问题，即主要目标是把所有人平安的送到和对岸，而每次小船最多只能载两个人，求解决方案。已知初始状态

	类型	说明	初始世界状态	目标世界状态
LocA	float3	地点A	(10,0,0)	(10,0,0)
LocB	float3	地点B	(-10,0,0)	(-10,0,0)
Mnum_A	int	地点A的传教士数	3	0
Cnum_A	int	地点A的食人族数	3	0
Mnum_B	int	地点A的传教士数	0	3
Cnum_B	int	地点A的食人族数	0	3
Boat	var	小船所在位置	LocA	LocB

另外，可以知道有哪些基础行动

Load(l,m,c)，装载乘客，l为装载地点,m为传教士数量，c为食人族数量
Move(f,t)，移动，f表示起始位置，t表示目标位置
Unload(l,m,c)，卸下乘客，l为卸下地点，m为传教士数量，c为食人族数量

误区一

上面的初始状态和目标状态是因为自己的惯性思维导致，在定义域中，我们应该使用PPDL(规划域定义语言)来进行描述才对（这里还不是最简，后面会进行进一步的缩减）

定义域
- Objects 对象定义：
  - missionary {m1,m2,m3}
  - cannibal {c1,c2,c3}
  - boat {b1}
  - loaction {locA,locB}
- Predicates 谓语定义：
  - At(?m - missionay ?l - loaction)
  - BoatAt(?b - boat ?l - loaction)
  - Loaded(?m - missionary ?c - cannibal)，该关系表明有谁在船上
  - UnLoaded(?b - boat)，b 为空
- States:有两类表达，一类是使用谓语表面各个对象之间的关系，另一类是对象的属性
  - Relations
    - At(m1,locA)
    - At(m2,locA)
    - At(m3,locA)
    - At(c1,locA)
    - At(c2,locA)
    - At(c3,locA)
    - BoatAt(locA)
  - Properties
    - LocA: missionaryNum = 3,cannibalNum = 3,postion = (10,0,0)
    - LocB: missionaryNum = 0,cannibalNum = 0,postion = (-10,0,0)

另外，怎么判断双方的人数是个问题，因为，世界状态中没有明确给出该值。因此，State中，除了描述对象间的关系，还应该有对象的属性，所以

定义域
- Properties 属性定义：
  - position:float3
  - missionaryNum:int
  - cannibalNum:int

遵循最低需求原则，添加最少的东西来满足需求，上面我们只添加了三个属性，其他的无需改变。因此，在设置条件和效果时，除了可以访问到对象，谓语时，还应该可以访问到其属性。

实际上，我们也并不关心到具体某个传教士和食人族，因此，Objects中的missionary，和 cannibal 也可以删除，boat 只有一个，且没有特别需要记录的属性，因此也可以删除，所以可以将定义域简化为

Objects 对象定义：
- loaction {locA,locB}
Predicates 谓语定义：
- BoatAt(?l - loaction)
- Loaded(?m - missionaryNum ?c - cannibalNum)
States:世界状态
- Relations
  - BoatAt(locA)
- Properties
  - LocA: missionaryNum = 3,cannibalNum = 3,postion = (10,0,0)
  - LocB: missionaryNum = 0,cannibalNum = 0,postion = (-10,0,0)

扩展：这里我们还只是考虑属性是一个简单属性，当属性是一个结构时，应该可以访问该结构的其它变量，甚至是嵌套结构。（为了简单的实现，暂不考虑递归嵌套的情况，应该说，避免该情况）结构的出现是为了封装一个通用的属性集，方便同类对象使用，如：

当这些对象都有 Hp，Mp,Attack,Defend,MoveSpeed这些属性时，如果对象比较多时，每一个都这样设置显得不太高效，因此，用一个结构封装起来会比较方便。

条件判断

有了这些之后，我们的条件判断可以有

? Op ? ：对世界状态中对象的属性进行判断，进行值的比较
- Op 是判断操作符，包括 > ,< ,>= ,<=, ==, !=
- ? 可以是常量，或者是世界状态中的变量属性，也可以是当前行动的参数（局部变量）,如
- LocA.missionaryNum > LocA.cannibalNum
- LocA.missionaryNum > 0
谓语判断：对世界中的对象关系进行判断，判断是否存在该关系
- At(m1,locA) ，单纯的判断世界状态中是否存在该关系
- 或¬At(m1,locA)，判断世界状态中不存在该关系（如果存在，返回false，不存在返回true）

使用谓语关系判断感觉有点消耗，因为需要遍历完所有命题才能得出结果，因此，可以给它们进行分组归类以加快查询，把所有谓语相同的放在一起。

作用效果

同样，作用效果也分为两类，一个是运算类，另一个是关系类

运算类：对应于世界状态中的对象属性，对属性进行运算修改
- LocB.missionaryNum += 2 ,加上一个常量
- LocA.missionaryNum -= LocB.missionaryNum ，减去另一个世界状态属性
- LocA.missionaryNum -= p ，减去一个变量
- LocA.missionaryNum -= p + LocB.missionaryNum ，减去多个数
关系类：对应世界状态中的关系，对关系进行添加或删除
- At(m1,locA) ，直接添加该关系（注意避免重复添加）
- ¬At(m1,locA) ，从世界状态中删除关系At(m1,locA)

如何选择方法

复合任务具有多种方法来实现，基元任务就算对应这个同一个行动也会因为参数的不同而不同。就拿基元任务来说

Load(l,m,c)的变体就有许多种
- load(LocA,2,0)
- load(LocA,1,1)
- load(LocA,1,0)
- …

首先，一个基础的Load行动的基本前提条件和效果如下 Load(l,m,c)

precond:
- l.missionaryNum >= m
- l.cannibalNum >= c
effects:
- l.missionaryNum -= m
- l.cannibalNum -= c

但是，什么时候使用load(LocA,2,0)，什么时候使用load(LocA,1,0)呢？这里看起来就复杂多了，首先我们分析一下情况，在初始状态下，我们可以采取哪些操作，不可以采取哪些操作，依据是什么。我们列出所有可能的操作：

load(LocA,2,0)
- 不可以，因为一旦进行这个操作之后，传教士的人数(1)<食人族的人数 (3)
load(LocA,1,1)
- 可以，执行操作之后，传教士的人数(2)<食人族的人数 (2)
- 注意，过道对岸后，需要选一个人撑船回来，选择食人族撑船回来会导致下船后，食人族的数量大于传教士的数量。选择传教士回来，然后继续下去，最后会发现，要么是重复的世界状态，要么是没有解决方案。
load(LocA,0,2)
- 可以，执行操作之后，传教士的人数(3)<食人族的人数 (1)
load(LocA,1,0)
- 不可以，因为一旦进行这个操作之后，传教士的人数(2)<食人族的人数 (3)
load(LocA,0,1)
- 可以，执行操作之后，传教士的人数(3)<食人族的人数 (2)
- 但是注意，这个操作是没有意义的，因为它到对岸后，又要撑船回来，变回原始状态，所以没有意义。

所以，上面可以的方案有三个，我们按照优先顺序逐个尝试

首先判断是否满足前提条件
接着判断应用效果后是否满足大前提（各岸传教士数始终 >= 各岸食人族数）
最后是，结果状态是否已经出现过，如果出现过，可能会造成死循环，所以也不满足

如何把传递参数给行动

参数，我们的行动具有参数，任务具有参数，方法也具有参数，它们之间的关系是

行动的参数 ⊆ 任务的参数 ⊆ 方法的参数

因为任务如果是复合任务，那么其参数的数量大于各个行动的参数数量，而方法因为可能有些额外的判断需要参数，所以也会大于任务的参数数量。

这里的一个关键概念是σ, 方法有方法名和参数组成,形如 name(x1,x2,x3,...xn) ，任务也是由任务名和参数组成，假设我们有一个任务为装载乘客 Load-People(LocA,1,1)，且该任务是一个基元任务 Load(l,m,c), 则方法的替换式σ = { l = locA,m = 1,c = 1 }。

因此，我们需要有一种定义σ的功能，来把生成的最终任务替换成实例行动（在最终计划中，保存的是基元任务的实例，其实就是action的实例，每个action都具有实例参数）

当我们生成最终计划时，应该是<Load(LocA,2,0),Move(LocA,LocB),UnLoad(LocB,2,0),…>这个样子。

假设我们定义了一个任务 MoveAllPeopleA2B(locA,locB,3,3,0,0),它有多个方法

Move_2M0C(f,t,x,y)
- precond:
  - BoatAt(f)
  - f.missionaryNum >= x
  - f.missionaryNum - x >= f.cannibalNum //移动后A地的情况
  - t.missionaryNum + x >= t.cannibalNum //移动后B地的情况
- subtasks:
  - Load(f,m,c),Move(f,t),Unload(t,m,c)， MoveAllPeopleA2B(t,f,f.missionaryNum - 2,f.cannibalNum,t.missionaryNum + 2,t.cannibalNum)
- σ = {m = 2,c = 0,f = LocA,t = LocB,x = 2,y = 0 }
Move_1M1C(f,t,x,y)
Move_0M2C(f,t,x,y)
Move_1M0C(f,t,x,y)
Move_1M0C(f,t,x,y)
NoMove()
- 空任务，表示结束

上面这些方法，除了NoMove外，只需要修改一下它们的σ就好,难点在于如何实现替换功能首先要求可以找出所有能够替换的标识符，它可以在prcond中，也可以在subtasks中，甚至可以在σ中，如

subtasks:
- Load(f,m,c),Move(f,t),Unload(t,m,c)，MoveAllPeopleA2B(t,f,m1,c1,m2,c2)
σ = {m = 2,c = 0,f = LocA,t = LocB,x = 2,y = 0 , m1 = f.missionaryNum - 2, c1 = f.cannibalNum, m2 = t.missionaryNum + 2, c2 = t.cannibalNum }

问题就是，允许这种自我嵌套解释会不会有隐患或者性能问题，也许只是自己多心了。

保险起见，就约束只替换precond，和subtasks中的变量
决定这种表单形式的数据和lua的适性比较高，可以考虑结合lua进行实现

而STN的初始规划网络w = <MoveAllPeopleA2B(LocA,LocB,3,3,0,0)>，最后通过不断选择合适的方法进行分解得到一组行动序列。

在 Unity 中开发HTN Planner (1)

Categories

Tags

Table of Contents

HTN Planning（Hierarchical Task Network）

误区一

条件判断

作用效果

如何选择方法

如何把传递参数给行动