带动态约束的运动规划算法 - 混合 A* 算法（附程序实现和详细说明）
前言（推荐读一下）
本文主要介绍动力学约束下的运动规划算法中非常经典的Hybrid A*算法，大致分为三部分，第一部分是在传统A * 算法的基础上，对Hybrid A * 算法的原理、流程进行理论介绍。第二部分是详细分析 MotionPlanning运动规划库中Hybrid A * 算法的源码，进一步深入对Hybrid A * 算法的具体细节 进行理解。 第三部分是结合前面第一部分的理论和第二部分的详细源码，对Hybrid A * 算法的流程进行综合的概括总结。
另外，本文介绍的源码来源于zhm_real/MotionPlanning运动规划库，我进行了简单的修改，并 Hybrid A * 算法涉及到的源码从该运动规划库中独立摘出来，我会将其以绑定资源的形式绑定在博客中，有需要的可自行免费下载。
一、Hybrid A*算法 理论介绍
Hybrid A* 算法结合了传统的A*算法和连续状态空间中的运动规划方法。它旨在在具有非完整约束（如车辆的转弯半径）的车辆等机器人中进行高效的路径规划。
传统的A * 算法是在栅格地图中进行搜索，可行路径中的点，都是栅格地图的中心点，如下面的第一幅图所示，lattice planner算法是先构建一个用于搜索的lattice图，如下面的第二幅图所示，Hybrid A* 算法结合了A * 算法和lattice planner算法的思想，将栅格地图的路径搜索与lattice图结合起来，在搜索过程中选取不同的控制量预演一段轨迹，且保持在每个栅格中仅保留一个可行的状态，如下面的第三幅图所示
与传统的A * 相比，Hybrid A算法的g(n)和h(n)函数更加复杂；传统的A * 算法在拓展的时候会搜索当前节点周围所有的邻居节点，而Hybrid A算法是在不同的控制输入的驱动下演化出一系列状态点，作为其要拓展的邻居，若当前节点n找出的某个邻居m所在的栅格之前是没有被探索过的，即该栅格中没有记录状态点，则把状态点m记录在该栅格中，若当前节点n找出的某个邻居m所在的栅格中已经记录了状态点，此时需要进行判断，若当前节点n拓展出的状态点m的累计代价更小，则将该栅格中的记录的状态点更改为m，否则不更改。
如何合理的设置Hybrid A*算法的启发式函数呢？
选择1是采用二维的欧式距离作为启发式函数，如下面的a图所示；选择2是采用考虑动力学但不考虑障碍物的启发式函数，如下面的b图所示，但在障碍物较多的环境，该启发式函数效率会变得很低，如下面的c图所示，选择3是采用考虑动力学但不考虑障碍物与不考虑动力学但考虑障碍物的一个最短路径相结合的启发式函数，如下面的d图所示
Hybrid A * 算法中作者还提出了一种Analytic Expansions的思想，即在搜索树生长的过程中，在添加了一个新的节点后，会以一定的概率去直接解从该新节点到目标点的理论上的最优可行路径，如果这一段路径恰好满足动力学约束，且不与障碍物相碰，则我们成功找到了一条可行路径（由Hybrid A * 算法搜索生成的从起点到该新的拓展节点的路径+该新的扩展节点到目标点生成的理论最优路径 两段构成），提前结束规划。
但频繁的使用该方法，在障碍物较多的环境下，往往会降低效率，所以，常常按一定的频率去使用，比如每扩展20个节点，尝试一次。随着新的节点距离目标点越来越近，通过该方式获得可行路径的概率也会增加，所以这个尝试频率，可以随着新的拓展节点距离目标点距离的接近而增大。
下图给出了一些Hybrid A*算法的应用示例
Hybrid A* 算法的优点在于它在离散状态空间和连续状态空间之间进行了平衡，兼顾了路径的最短性和机器人的动力学特性。然而，这也使得算法比传统的A算法更为复杂，并且需要更多的计算资源来处理连续状态空间中的运动规划。总的来说，Hybrid A 算法是一种强大的路径规划算法，特别适用于需要考虑机器人动力学约束的情况，如自动驾驶车辆、无人机等。
二、Hybrid A*算法python程序解读
zhm_real/MotionPlanning运动规划库中Hybrid A * 算法的主要程序在hybrid_astar.py中，经过上面的介绍我们知道在Hybrid A*算法运行过程中会掉传统的A * 算法以及Reeds sheep算法，所以在hybrid_astar.py中分别调用了astar.py、reeds_shepp.py、以及可视化绘图所需的draw.py。
涉及到的astar.py和reeds_shepp.py这两个文件中的源码在之前的文章中已经详细介绍过了，链接如下，请大家自行前往查看，所以这里仅放一下这两个文件的源码，方便大家使用，不再作详细介绍
zhm_real/MotionPlanning运动规划库中A*算法源码详细解读（点击可跳转）
reeds_sheep运动规划算法Python源码分析（点击可跳转）
astar.py源码如下：
import heapq
import math
import numpy as np
import matplotlib.pyplot as plt
class Node:
def __init__(self, x, y, cost, pind):
self.x = x # x position of node
self.y = y # y position of node
self.cost = cost # g cost of node
self.pind = pind # parent index of node
class Para:
def __init__(self, minx, miny, maxx, maxy, xw, yw, reso, motion):
self.minx = minx
self.miny = miny
self.maxx = maxx
self.maxy = maxy
self.xw = xw
self.yw = yw
self.reso = reso # resolution of grid world
self.motion = motion # motion set
def astar_planning(sx, sy, gx, gy, ox, oy, reso, rr):
"""
return path of A*.
:param sx: starting node x [m]
:param sy: starting node y [m]
:param gx: goal node x [m]
:param gy: goal node y [m]
:param ox: obstacles x positions [m]
:param oy: obstacles y positions [m]
:param reso: xy grid resolution
:param rr: robot radius
:return: path
"""
n_start = Node(round(sx / reso), round(sy / reso), 0.0, -1)
n_goal = Node(round(gx / reso), round(gy / reso), 0.0, -1)
ox = [x / reso for x in ox]
oy = [y / reso for y in oy]
P, obsmap = calc_parameters(ox, oy, rr, reso)
open_set, closed_set = dict(), dict()
open_set[calc_index(n_start, P)] = n_start
q_priority = []
heapq.heappush(q_priority,
(fvalue(n_start, n_goal), calc_index(n_start, P)))
while True:
if not open_set:
break
_, ind = heapq.heappop(q_priority)
n_curr = open_set[ind]
closed_set[ind] = n_curr
open_set.pop(ind)
for i in range(len(P.motion)):
node = Node(n_curr.x + P.motion[i][0],
n_curr.y + P.motion[i][1],
n_curr.cost + u_cost(P.motion[i]), ind)
if not check_node(node, P, obsmap):
continue
n_ind = calc_index(node, P)
if n_ind not in closed_set:
if n_ind in open_set:
if open_set[n_ind].cost > node.cost:
open_set[n_ind].cost = node.cost
open_set[n_ind].pind = ind
else:
open_set[n_ind] = node
heapq.heappush(q_priority,
(fvalue(node, n_goal), calc_index(node, P)))
pathx, pathy = extract_path(closed_set, n_start, n_goal, P)
return pathx, pathy
def calc_holonomic_heuristic_with_obstacle(node, ox, oy, reso, rr):
n_goal = Node(round(node.x[-1] / reso), round(node.y[-1] / reso), 0.0, -1)
ox = [x / reso for x in ox]
oy = [y / reso for y in oy]
P, obsmap = calc_parameters(ox, oy, reso, rr)
open_set, closed_set = dict(), dict()
open_set[calc_index(n_goal, P)] = n_goal
q_priority = []
heapq.heappush(q_priority, (n_goal.cost, calc_index(n_goal, P)))
while True:
if not open_set:
break
_, ind = heapq.heappop(q_priority)
n_curr = open_set[ind]
closed_set[ind] = n_curr
open_set.pop(ind)
for i in range(len(P.motion)):
node = Node(n_curr.x + P.motion[i][0],
n_curr.y + P.motion[i][1],
n_curr.cost + u_cost(P.motion[i]), ind)
if not check_node(node, P, obsmap):
continue
n_ind = calc_index(node, P)
if n_ind not in closed_set:
if n_ind in open_set:
if open_set[n_ind].cost > node.cost:
open_set[n_ind].cost = node.cost
open_set[n_ind].pind = ind
else:
open_set[n_ind] = node
heapq.heappush(q_priority, (node.cost, calc_index(node, P)))
hmap = [[np.inf for _ in range(P.yw)] for _ in range(P.xw)]
for n in closed_set.values():
hmap[n.x - P.minx][n.y - P.miny] = n.cost
return hmap
def check_node(node, P, obsmap):
if node.x <= P.minx or node.x >= P.maxx or \
node.y <= P.miny or node.y >= P.maxy:
return False
if obsmap[node.x - P.minx][node.y - P.miny]:
return False
return True
def u_cost(u):
return math.hypot(u[0], u[1])
def fvalue(node, n_goal):
return node.cost + h(node, n_goal)
def h(node, n_goal):
return math.hypot(node.x - n_goal.x, node.y - n_goal.y)
def calc_index(node, P):
return (node.y - P.miny) * P.xw + (node.x - P.minx)
def calc_parameters(ox, oy, rr, reso):
minx, miny = round(min(ox)), round(min(oy))
maxx, maxy = round(max(ox)), round(max(oy))
xw, yw = maxx - minx, maxy - miny
motion = get_motion()
P = Para(minx, miny, maxx, maxy, xw, yw, reso, motion)
obsmap = calc_obsmap(ox, oy, rr, P)
return P, obsmap
def calc_obsmap(ox, oy, rr, P):
obsmap = [[False for _ in range(P.yw)] for _ in range(P.xw)]
for x in range(P.xw):
xx = x + P.minx
for y in range(P.yw):
yy = y + P.miny
for oxx, oyy in zip(ox, oy):
if math.hypot(oxx - xx, oyy - yy) <= rr / P.reso:
obsmap[x][y] = True
break
return obsmap
def extract_path(closed_set, n_start, n_goal, P):
pathx, pathy = [n_goal.x], [n_goal.y]
n_ind = calc_index(n_goal, P)
while True:
node = closed_set[n_ind]
pathx.append(node.x)
pathy.append(node.y)
n_ind = node.pind
if node == n_start:
break
pathx = [x * P.reso for x in reversed(pathx)]
pathy = [y * P.reso for y in reversed(pathy)]
return pathx, pathy
def get_motion():
motion = [[-1, 0], [-1, 1], [0, 1], [1, 1],
[1, 0], [1, -1], [0, -1], [-1, -1]]
return motion
def get_env():
ox, oy = [], []
for i in range(60):
ox.append(i)
oy.append(0.0)
for i in range(60):
ox.append(60.0)
oy.append(i)
for i in range(61):
ox.append(i)
oy.append(60.0)
for i in range(61):
ox.append(0.0)
oy.append(i)
for i in range(40):
ox.append(20.0)
oy.append(i)
for i in range(40):
ox.append(40.0)
oy.append(60.0 - i)
return ox, oy
def main():
sx = 10.0 # [m]
sy = 10.0 # [m]
gx = 50.0 # [m]
gy = 50.0 # [m]
robot_radius = 2.0
grid_resolution = 1.0
ox, oy = get_env()
pathx, pathy = astar_planning(sx, sy, gx, gy, ox, oy, grid_resolution, robot_radius)
plt.plot(ox, oy, 'sk')
plt.plot(pathx, pathy, '-r')
plt.plot(sx, sy, 'sg')
plt.plot(gx, gy, 'sb')
plt.axis("equal")
plt.show()
if __name__ == '__main__':
main()
reeds_shepp.py源码如下：
import time
import math
import numpy as np
# parameters initiation
STEP_SIZE = 0.2
MAX_LENGTH = 1000.0
PI = math.pi
# class for PATH element
class PATH:
def __init__(self, lengths, ctypes, L, x, y, yaw, directions):
self.lengths = lengths # lengths of each part of path (+: forward, -: backward) [float]
self.ctypes = ctypes # type of each part of the path [string]
self.L = L # total path length [float]
self.x = x # final x positions [m]
self.y = y # final y positions [m]
self.yaw = yaw # final yaw angles [rad]
self.directions = directions # forward: 1, backward:-1
def calc_optimal_path(sx, sy, syaw, gx, gy, gyaw, maxc, step_size=STEP_SIZE):
paths = calc_all_paths(sx, sy, syaw, gx, gy, gyaw, maxc, step_size=step_size)
minL = paths[0].L
mini = 0
for i in range(len(paths)):
if paths[i].L <= minL:
minL, mini = paths[i].L, i
return paths[mini]
def calc_all_paths(sx, sy, syaw, gx, gy, gyaw, maxc, step_size=STEP_SIZE):
q0 = [sx, sy, syaw]
q1 = [gx, gy, gyaw]
paths = generate_path(q0, q1, maxc)
for path in paths:
x, y, yaw, directions = \
generate_local_course(path.L, path.lengths,
path.ctypes, maxc, step_size * maxc)
# convert global coordinate
path.x = [math.cos(-q0[2]) * ix + math.sin(-q0[2]) * iy + q0[0] for (ix, iy) in zip(x, y)]
path.y = [-math.sin(-q0[2]) * ix + math.cos(-q0
上一篇：
地址簿实现（静态版本、动态版本、文件版本）（含完整源代码） - I. 静态版本
下一篇：
[数据结构] 八排序（二）