我如何确定这种启发式方法是否可接受且一致?

人工智能 搜索 证明 启发式 可接受的启发式 一致启发式
2021-10-29 20:27:18

我得到了以下要解决的问题。

给定一条圆形轨迹除以n>2段标记0n1. 一开始,代理位于段号的开头0(段之间的边缘n10) 和代理的速度 (M) 是0每分钟段数。

在每分钟开始时,代理会采取以下三个动作之一:

  • speed up:代理的速度增加1每分钟段。
  • 减速:代理的速度降低1每分钟段。
  • 保持相同的速度:保持相同的速度。

如果当前速度0每分钟段数。

每个动作的代价是1.

智能体的目标是在小道上行驶 k 次(1k) 然后停在起点处(当然速度为 0)。代理需要以最少的动作做到这一点。

给出的启发式是:如果代理在段中z然后:nz如果z0或者0如果z=0.

我需要确定给定的启发式是否可接受(或完整)且一致。

我认为:

  • 关于一致性:如果它的估计总是从任何给定的邻居顶点到目标的估计距离加上达到目标的成本。因此,在给定的问题中,它是一致的,因为 (n>2),因此启发式函数定义明确,并且由于循环轨迹除以n价格不变的细分市场1对于每个动作,给定的一致性定义成立,因为从任何给定的邻居顶点到目标的估计距离可以看作是段之间的差异,直到达到目标,并且它是一致的,因为函数再次被明确定义。

  • 关于可接纳性:可接纳启发式是达到目标的成本永远不会超过从当前点到达到目标的最低可能成本。我不确定给定的启发式是否可以接受,因为知道轨迹大小(n= 段大小)和当前位置。但它不会产生缺陷,因此它可能是可以接受的。我不确定这是一个证据。

我的想法正确吗?我怎么能把它写成证据呢?

1个回答

欢迎来到 AI.SE @hpr16!

您对启发式何时可接受的理解是正确的,但您的启发式是不可接受的。可接受的启发式算法必须始终低估从给定状态转移到目标状态的成本。

请注意,搜索中的状态问题中圆圈上的位置不同。状态需要捕获有关代理所在当前环境的所有信息。在您的问题中,代理具有速度和位置。因此,一个国家必须同时包含这两者。

看看为什么你的启发式是不可接受的,因为代理可以以小于 nz 的步长移动 (nz) 段:它可以加速,并以例如 (nz)/2 步的速度移动,以速度 2 移动。