在 Unity 中开发HTN Planner (6)

by Yimi

December 3, 2019

Categories

• Dev Log

Tags

• Log
• Unity
• AI

Table of Contents

---

本来想尝试PSP，POP（Partial-Order Planning）这一些方法的，因为PSP 是一种基于计划空间规划的算法，里面的每个节点都是某个行动，基于逆向搜索，从目标状态开始反推到起始状态。如寻找可以产生满足当前某些状态的可执行行动，然后把该行动所需条件加入需求列表，继而继续寻找可以满足该行动前提条件的行动，这样一步步向前推进，直到没有未满足条件。

而HTN分层任务网络的结构是基于任务进行规划的（前面的两个算法是基于行动进行的），任务的实现又由不同的方法来实现，形成树状分层网络。因为HTN是前向进行规划的，基于根任务开始向下分解，不像GOAP这类逆向，无需完整规划才能得到第一步该做什么。这也是HTN的一个优点，即局部计划，可以只向前推进一小部分，而不用担心执行计划过程世界状态发生变化导致计划完全作废。

另外可以借助其它算法的思路来进行优化，如A*的启发式。之前提到过，根据不同问题，它们的启发式是不一样的。选择哪个节点会更加好，在不同问题中的考虑是不一样的。对于我们用来测试的”传教士和食人族过河问题”，我们可以利用寻路的思考方式，越接近目标点（寻路中可能还要思考移动成本之类的），评分越高（评分越高表示成本越大），那么，同样道理，”传教士和食人族过河问题”的目标是使得起始点A地的人数为0，也就是，任意一个操作，给它评分的依据是，是否减少A地的人数。如果减少2个，我们给0分，减少1个给1分，添加1个给2分，添加两个给3分。

然后在选取行为是优先选取评分低的，也就是成本小的。因此，我们需要做的是，提供启发算法，来对行动结果进行评分，根据评分从低到高排列，每次添加一个行动，就对其评分，并安排到队列的合适位置，每次获取行动时优先提供低评分的行动。 因此，对于每个方法我们提供评估方法

---===============
-- Methods.lua
---===============
Methods.Load_2m0c =function(...)
	-- ...
	method.score = Substitute("if [f] == LocA then return 0 else return 3 end",env)
	return method
end

Methods.Load_1m1c =function(...)
	-- ...
	method.score = Substitute("if [f] == LocA then return 0 else return 3 end",env)
	return method
end

Methods.Load_1m0c =function(...)
	-- ...
	method.score = Substitute("if [f] == LocA then return 1 else return 2 end",env)
	return method
end

Methods.Load_0m1c =function(...)
	-- ...
	method.score = Substitute("if [f] == LocA then return 1 else return 2 end",env)
	return method
end

Methods.Load_0m2c =function(...)
	-- ...
	method.score = Substitute("if [f] == LocA then return 0 else return 3 end",env)
	return method
end
Methods.End =function(...)
	-- ...
	method.score = Substitute("return 0",env)
	return method
end

接着是启发式的计算,因为我们已经把评分公司编辑在方法中了，所以只在需要的时候进行实例化计算就可以

---===============
-- Heuristic.lua
---===============
require "HTN.Core.LocalParser"

local Heuristic = {}

 Heuristic.Calc = function (_ws,_method)
	local env = setmetatable(
		{},
		{__index = _G}
	)
	for k, v in pairs(_ws.Objects) do
		env[k] = v
	end
	local parser = NewParser("启发式评估",env)
	--print(_method.score)
	_method.score = parser(_method.score)
	--print(_method.score)
end

Heuristic.Sort = function(_src)
	--BubbleSortd
	for t = 1, #_src do
		for i = 1,#_src - t do
			if _src[i].score > _src[i+1].score then
				local temp = _src[i]
				_src[i] = _src[i+1]
				_src[i+1] = temp
			end
		end
	end
end

return Heuristic

规划器中的选取方法的地方也要跟着改动

---===============
-- Planner.lua
---===============
function Planner:ChooseMethods(_ws,_methods,_opentasks,_depth)

	local chooseList = {}

	-- 逐个方法进行尝试，某个方法失败时回溯，进行下一个方法的测试
	for i, m in ipairs(_methods) do		
		local method = self.Methods:GetMethods(m)
		local isfit,whyfail = IsFitPreconds(_ws,method.preconds)
		if isfit then
			table.insert(chooseList,method)
		else
			printf(string.rep(" ",_depth*4).."【过滤方法 %d】 %s ,不满足条件 : %s",i,method,whyfail)
		end
	end

	-- 使用启发式对方法进行排序
	for i, v in ipairs(chooseList) do
		-- 对方法进行评分
		self.Heuristic.Calc(_ws,v)
	end
	--开始排序
	self.Heuristic.Sort(chooseList)

	--逐个方法进行尝试，某个方法失败时回溯，进行下一个方法的测试
	for i, m in ipairs(chooseList) do
		--获取实例化子任务
		printf(string.rep(" ",_depth*4).."【尝试方法 %d】 %s ,条件满足",i,m)
		local subtasks = {}
		if m.subtasks ~= nil then
			for _, v in ipairs(m.subtasks) do
				local t = self.Tasks:GetTask(v)
				table.insert(subtasks,t)
			end
			--把t1替换为子任务序列，合并回原任务队列
			local plan = self:TFD(_ws,table.combine(subtasks, table.sublist(_opentasks,2,#_opentasks)),_depth + 1)
			if plan ~= nil then
				-- 方法测试成功
				return plan
			end
		else
			-- 遇到了结束方法
			print(string.rep(" ",_depth*4).."【成功得到解决方案】")
			return {}
		end
	end

	print(string.rep(" ",_depth*4).."【所有方法都不行--------------------------】")
	return nil
end

另外可以改进一下启发式。目前只考虑了对于A地的减少情况，10种操作中，有3种是减少两个的情况，2种减少一个的情况，3种增加两个的情况，2种增加一个的情况。也就是说对于相同的情况我们并没有进行划分，例如，都是减少两个，那么使用哪一个比较好呢。根据最优解的情况来看，尽可能的让食人族来开船会比较好，因此，我们增加评估依据，加上，有两个食人族0分，有一个食人族 1分，没有食人族2分。

不过对比了一下，结果并没有什么变化。也是33步

在调试的过程中曾经得到过的最少步数。不过已经忘了当初设置的启发函数是多少，还好有保存结果，找机会再调试一边看看

----当前世界状态 { BoatAt LocA ,LocA.M = 3,LocA.C = 3 ,LocB.M = 0,LocB.C = 0 }
解决方案步数	27
执行行为Load(LocA,1,1)
----当前世界状态 { BoatAt LocA ,LocA.M = 2,LocA.C = 2 ,LocB.M = 0,LocB.C = 0 }
执行行为Move(LocA,LocB)
----当前世界状态 { BoatAt LocB ,LocA.M = 2,LocA.C = 2 ,LocB.M = 0,LocB.C = 0 }
执行行为UnLoad(LocB,1,1)
----当前世界状态 { BoatAt LocB ,LocA.M = 2,LocA.C = 2 ,LocB.M = 1,LocB.C = 1 }
执行行为Load(LocB,1,0)
----当前世界状态 { BoatAt LocB ,LocA.M = 2,LocA.C = 2 ,LocB.M = 0,LocB.C = 1 }
执行行为Move(LocB,LocA)
----当前世界状态 { BoatAt LocA ,LocA.M = 2,LocA.C = 2 ,LocB.M = 0,LocB.C = 1 }
执行行为UnLoad(LocA,1,0)
----当前世界状态 { BoatAt LocA ,LocA.M = 3,LocA.C = 2 ,LocB.M = 0,LocB.C = 1 }
执行行为Load(LocA,1,1)
----当前世界状态 { BoatAt LocA ,LocA.M = 2,LocA.C = 1 ,LocB.M = 0,LocB.C = 1 }
执行行为Move(LocA,LocB)
----当前世界状态 { BoatAt LocB ,LocA.M = 2,LocA.C = 1 ,LocB.M = 0,LocB.C = 1 }
执行行为UnLoad(LocB,1,1)
----当前世界状态 { BoatAt LocB ,LocA.M = 2,LocA.C = 1 ,LocB.M = 1,LocB.C = 2 }
执行行为Load(LocB,1,0)
----当前世界状态 { BoatAt LocB ,LocA.M = 2,LocA.C = 1 ,LocB.M = 0,LocB.C = 2 }
执行行为Move(LocB,LocA)
----当前世界状态 { BoatAt LocA ,LocA.M = 2,LocA.C = 1 ,LocB.M = 0,LocB.C = 2 }
执行行为UnLoad(LocA,1,0)
----当前世界状态 { BoatAt LocA ,LocA.M = 3,LocA.C = 1 ,LocB.M = 0,LocB.C = 2 }
执行行为Load(LocA,2,0)
----当前世界状态 { BoatAt LocA ,LocA.M = 1,LocA.C = 1 ,LocB.M = 0,LocB.C = 2 }
执行行为Move(LocA,LocB)
----当前世界状态 { BoatAt LocB ,LocA.M = 1,LocA.C = 1 ,LocB.M = 0,LocB.C = 2 }
执行行为UnLoad(LocB,2,0)
----当前世界状态 { BoatAt LocB ,LocA.M = 1,LocA.C = 1 ,LocB.M = 2,LocB.C = 2 }
执行行为Load(LocB,0,1)
----当前世界状态 { BoatAt LocB ,LocA.M = 1,LocA.C = 1 ,LocB.M = 2,LocB.C = 1 }
执行行为Move(LocB,LocA)
----当前世界状态 { BoatAt LocA ,LocA.M = 1,LocA.C = 1 ,LocB.M = 2,LocB.C = 1 }
执行行为UnLoad(LocA,0,1)
----当前世界状态 { BoatAt LocA ,LocA.M = 1,LocA.C = 2 ,LocB.M = 2,LocB.C = 1 }
执行行为Load(LocA,1,1)
----当前世界状态 { BoatAt LocA ,LocA.M = 0,LocA.C = 1 ,LocB.M = 2,LocB.C = 1 }
执行行为Move(LocA,LocB)
----当前世界状态 { BoatAt LocB ,LocA.M = 0,LocA.C = 1 ,LocB.M = 2,LocB.C = 1 }
执行行为UnLoad(LocB,1,1)
----当前世界状态 { BoatAt LocB ,LocA.M = 0,LocA.C = 1 ,LocB.M = 3,LocB.C = 2 }
执行行为Load(LocB,1,0)
----当前世界状态 { BoatAt LocB ,LocA.M = 0,LocA.C = 1 ,LocB.M = 2,LocB.C = 2 }
执行行为Move(LocB,LocA)
----当前世界状态 { BoatAt LocA ,LocA.M = 0,LocA.C = 1 ,LocB.M = 2,LocB.C = 2 }
执行行为UnLoad(LocA,1,0)
----当前世界状态 { BoatAt LocA ,LocA.M = 1,LocA.C = 1 ,LocB.M = 2,LocB.C = 2 }
执行行为Load(LocA,1,1)
----当前世界状态 { BoatAt LocA ,LocA.M = 0,LocA.C = 0 ,LocB.M = 2,LocB.C = 2 }
执行行为Move(LocA,LocB)
----当前世界状态 { BoatAt LocB ,LocA.M = 0,LocA.C = 0 ,LocB.M = 2,LocB.C = 2 }
执行行为UnLoad(LocB,1,1)
----当前世界状态 { BoatAt LocB ,LocA.M = 0,LocA.C = 0 ,LocB.M = 3,LocB.C = 3 }

Share Tweet LinkedIn Reddit