宾夕法尼亚大学Coursera运动规划公开课学习有感
元宵节已过, 新学期正式开始啦.
Introduction to Computational Motion Planning
阐述路径规划的概念是什么？以下是一些英文术语：G/V/E: 一个图G（Graph）由顶点集合V（Vertices）和边集合E（Edges）组成。边将所有顶点连接在一起。边通常赋予数值权重w_{ij}以表示相关的量例如距离或消耗成本。一般来说，在路径规划问题中，目标是从起点到终点找到路径长度最短的路线。
Grassfire Algorithm
这个算法，可以从目标开始，绕着相邻的格子标数字。伪代码如图:
从任何一个格子开始，在其周围数字中找到最小的那个目标单元格并移动过去即可完成任务。例如下图所示的一圈全是9的情况，在这种特殊情况下无论选择哪个起始点都能满足条件
在进行格子标注时，若初始点尚未被标注为数字号码，则标注流程将提前终止。这表明初始点与目标点之间缺乏连通性。
该算法在计算效率方面表现欠佳。该算法的规模与其所处理的空间维度呈线性关系。当空间维度极大时，该算法所需的空间将呈现急剧增长趋势。(网格单元数量)与(空间维度)呈指数级增长关系。
Dijkstra算法（此处指适用于2D的算法)
以图的形式展示伪代码，在每个节点中包含两个属性：分别是父节点和距离。通过遍历所有相邻节点并比较其标记的距离值，在这些值中找到最小的那个点作为下一个目标节点；然后重复这一过程直到完成所有迭代步骤。
算法效率：在介绍一种高效的数据结构时提到了一个聪明的数据结构叫做priority queue（优先级队列），它能够使算法的计算效率在维数增加时不会急剧下降。这个优先级队列priority queue看起来像是数据结构领域中的一个重要概念？这可能属于数据结构的知识范畴？是否如此还有待于向计算机专业的同学求证。
A*算法:(此处指适用于2D的算法)
除了之前提到的那些方法外，它们的效率相对较低的原因在于采用了基于全向搜索的方法。相比之下，A*算法表现更为出色是因为它利用启发式信息逐步聚焦于目标区域而不是在所有方向上进行探索。
以下是伪代码实现：
以下是伪代码实现...。
g代表的是current节点与起点之间的距离，
而f值则由该节点的g值及其启发式成本组成。
根据上一节所述，
在目标处启发式成本函数值为0，
并且对于任意相邻的两个节点x和y来说，
必须满足h(x) ≤ h(y)。
和dijkstra算法相比，快了很多呢。
附录: 源自维基百科的A*伪代码
function A*(start, goal)
// The set of nodes already evaluated.
closedSet := {}
// The set of currently discovered nodes still to be evaluated.
// Initially, only the start node is known.
openSet := {start}
// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
cameFrom := the empty map
// For each node, the cost of getting from the start node to that node.
gScore := map with default value of Infinity
// The cost of going from start to start is zero.
gScore[start] := 0
// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
fScore := map with default value of Infinity
// For the first node, that value is completely heuristic.
fScore[start] := heuristic_cost_estimate(start, goal)
while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
closedSet.Add(current)
for each neighbor of current
if neighbor in closedSet
continue // Ignore the neighbor which is already evaluated.
// The distance from start to a neighbor
tentative_gScore := gScore[current] + dist_between(current, neighbor)
if neighbor not in openSet // Discover a new node
openSet.Add(neighbor)
else if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
// This path is the best until now. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
return failure
function reconstruct_path(cameFrom, current)
total_path := [current]
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.append(current)
return total_path