在 Unity 中开发HTN Planner (4)

规划器（Planner）
其他小问题

规划器（Planner）

这里比较重要的是规划器（Planner）,它负责算法的实现，分析世界状态，使用合适的方法分解任务，最终生成一个解决方案，即一个行动列表。另外，为了进行规划分析，它需要得到一份世界状态的副本，以便用来模拟每个行动的后果。

目前的实现是使用TFD（Total-Order Forward Decomposition，全序正向分解）算法，再看一下它的伪代码

function Ground-TFD(s,<t₁,…,t_k>,O,M)
- if k = 0 return <>
- if t₁.isPrimitive() then
  - actions = {(a,σ) | a = σ(t₁ and a applicable in s)}
  - if actions.isEmpty() then return failure
  - (a,σ) = actions.chooseOne()
  - plan ← Ground-TFD(γ(s,a),σ(<t₂,…,t_k>) ,O,M)
  - if plan = failure then return failure
  - else renturn <a> · plan
- else
  - methods = {(m,σ) | m is relevant for σ(t₁) and m is applicable in s }
  - if methods.isEmpty() then retun failure
  - (m,σ) = methods.chooseOne()
  - plan ← subtasks(m) · σ(<t₂,…,t_k>)
  - return Ground-TFD(s,plan,O,M)

然后是lua代码实现

--==========================
--Total-Order Forward Decomposition
--==========================
function Planner:TFD(_ws,_opentasks,_depth)
	if #_opentasks == 0 then return {} end
	if _depth >= 200 then
		print("深度过大")
		return nil
	end
	--为了不干扰世界状态，进行深拷贝
	local ws = table.deepcopy(_ws)
	local t1 = _opentasks[1]
	printf(string.rep(" ",_depth*4).."开始分析任务 %s",t1.taskDecl)

	if t1.IsPrimitive then
		return self:ChooseAction(_ws,t1,_opentasks,_depth)				
	else
		local methods = t1.Methods
		if methods == nil then
			return nil
		else
			return self:ChooseMethods(ws,methods,_opentasks,_depth)
		end
	end
end

function Planner:ChooseAction(_ws,_task,_opentasks,_depth)
	local res ,whyfail = IsFitPreconds(_ws,_task.preconds)
	if res then
		printf(string.rep(" ",_depth*4).."行动%s 条件满足，添加行动实例 ",_task.taskDecl)
		local a = self.Actions:GetAction(_task.taskDecl)
		ApplyActionEffects(_ws,a)--应用行动效果
		local plan = self:TFD(_ws,table.sublist(_opentasks,2,#_opentasks),_depth + 1)
		if plan == nil then
			return nil
		else
			return table.combine({a},plan)
		end
	else
		printf(string.rep(" ",_depth*4).."行动%s 条件不满足 : %s ",_task.taskDecl,whyfail)
		return nil
	end
end

function Planner:ChooseMethods(_ws,_methods,_opentasks,_depth)
	-- 逐个方法进行尝试，某个方法失败时回溯，进行下一个方法的测试
	for _, m in ipairs(_methods) do

		local method = self.Methods:GetMethods(m)
		local isfit,whyfail = IsFitPreconds(_ws,method.preconds)
		if isfit then
			--获取实例化子任务
			printf(string.rep(" ",_depth*4).."【尝试方法】 %s ,条件满足",m)
			local subtasks = {}
			for _, v in ipairs(method.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
			printf(string.rep(" ",_depth*4).."【尝试方法】 %s ,不满足条件 : %s",m,whyfail)
		end
	end
	print(string.rep(" ",_depth*4).."【所有方法都不行 X】")
	return nil
end

调试的过程中，发现陷入了无限循环的递归深渊，想了下发现问题所在，就是对于重复状态的检测。当我们应用行动时得到的新的世界状态，而这个新的世界状态已经出现过，那么说明这个方案是失败的（会造成无限循环），应该尝试下一个方案。

那么，如何记录这个世界状态是否已经出现过，简单暴力的方法是，创建一个列表用来保存已经出现过的世界状态列表，然后将新的状态和列表中的所有状态进行对比，已存在则返回插入失败，不存在才插入成功，类似的容器如C#中的Hash Set

直觉上，我偏向于计算出每个世界状态的哈希值，并用这个哈希值作为键插入世界状态列表中，当得到一个新的世界状态时，计算一下它的哈希值，然后到世界状态列表中查看是否有该值。

因此，需要一个有效的哈希值计算方法。

找来了两个辅助脚本第一个是我们之前的打印表格的脚本，他会返回表格的字符串表示，两个内容相同的表格返回的字符串内容也是一样的

local LogUtil = {}

table.print = function(t,tableName)
 if t == nil then

   error((tableName or "input t").." == nil",1)

 else
   print((tableName or "unknown").." = "..LogUtil.FormatTable(t))
 end
end


function LogUtil.FormatTable(t, prefix, tableList)
 prefix = prefix or "";
 tableList = tableList or {};

 if tableList[t] then
   return "[ReFormat:"..tostring(t).."]";
 end

 tableList[t] = true;

 local str = "{\n"

 for k, v in pairs(t) do
   str = str..LogUtil.FormatField(k, v, prefix.."\t", tableList).."\n";
 end

 str = str..prefix.."}";

 return str;
end

function LogUtil.FormatField(key, value, prefix, tableList)
 return prefix..LogUtil.FormatKey(key, prefix, tableList) .." = "..LogUtil.FormatValue(value, prefix, tableList)..";";
end

function LogUtil.FormatKey(key, prefix, tableList)
 local keyType = type(key);
 if keyType == "string" then
   return key;
 elseif keyType == "number" then
   return "["..key.."]";
 end

 return "["..tostring(key).."]";
end

function LogUtil.FormatValue(value, prefix, tableList)
 local valueType = type(value);
 if valueType == "string" then
   return "\""..value.."\"";
 elseif valueType == "number" or valueType == "boolean" then
   return tostring(value)
 elseif valueType == "table" then
   return LogUtil.FormatTable(value, prefix, tableList);
 end

 return "["..tostring(value).."]";
end

return LogUtil

第二个是hash加密文件，将输入的文本转成一串比较短的秘钥，相同文本得到的秘钥肯定一样，因此，我们就用这个秘钥当做键值传入表格

MODULESsha1.lua

其他小问题

成功解决无限循环的问题后，其他问题也开始暴露了出来。不过这是条件描述的问题。目前的测试问题是”传教士与食人族过河问题”，在下船的时候，下船地点的食人族数一定要小于传教士的数量，但是这也是有前提的，如果传教士的数量为零，则无视该条件。因此，条件语句应该改为

-- 原来的错误的条件描述
-- ' [l].missionaryNum + [m] >= [l].cannibalNum + [c]'

--正确的描述
[l].missionaryNum + [m] == 0 or [l].missionaryNum + [m] >= [l].cannibalNum + [c]

上船的时候也有同样的状况，即传教士上船后，岸上只留下食人族，这样的情况也是可以的。

-- 原来的错误的条件描述
-- '[l].missionaryNum >= [m]'

--正确的描述
[l].missionaryNum + [m] == 0 or [l].missionaryNum + [m] >= [l].cannibalNum + [c]

然后比较迷惑的是，条件应该方法层级就进行判断，或者是任务层级，还是在行动层级进行判断。

个人偏向在方法层级就把条件判断完毕，这样就不用展开到行为层级再判断，减少计算。行动层级的条件主要是运行时的判断，来即时相应世界状态的变化。在任务层级进行设置的目的是为了减少设置操作，当一个任务在很多方法都出现时，在每个方法中都设置一遍显得有点麻烦，因此，在任务层级进行设置就可以实现复用，弊端就是，只有将方法展开到任务时才能判断条件是否满足。

引出来的问题就是，如果子任务很多，前面的子任务都通过检测，突然发现一个不满足条件的，前面的计算就全都浪费了。因此，考虑这种情况，要不要把条件提升到方法层级。

最后是一直无法得到解决方案的问题，原因是自己忘记设置了终止条件，终止方法End

Tasks.Transport =function (...)
	local input = {...}
	local env = setmetatable(
		{
			f = input[1],
			t = input[2]
		},
		{__index = _G}
	)
	local task = {}
	task.IsPrimitive = false
	task.preconds = {
		valuelimits = {
			Substitute("LocA.missionaryNum + LocA.cannibalNum ~= 0",env)
		}
	}
	task.Methods = {
		Substitute("Load_2m0c([f],[t],2,0)",env),
		Substitute("Load_1m1c([f],[t],1,1)",env),
		Substitute("Load_1m0c([f],[t],1,0)",env),
		Substitute("Load_0m1c([f],[t],0,1)",env),
		Substitute("Load_0m2c([f],[t],0,2)",env),
		Substitute("End()",env),
	}
	return task
end

End方法的定义

Methods.End =function(...)
	--local input = {...}
	local env = setmetatable(
		{},
		{__index = _G}
	)
	local method = {}
	method.preconds = {
		relations = {
			positive = {Substitute("BoatAt(LocB)",env)}
		},
		valuelimits = {
			Substitute("LocA.missionaryNum + LocA.cannibalNum == 0",env)
		}
	}
	return method
end

最后，终于成功得到解决方案。

这是不是就可以了呢？接下来，就实现计划执行器进行验证，看看得到的解决方案是不是可以完成目标任务。

源码

在 Unity 中开发HTN Planner (4)

Categories

Tags

Table of Contents

规划器（Planner）

其他小问题