# BS-AStar

**Repository Path**: openharmony-sig-ib/bs-astar

## Basic Information

- **Project Name**: BS-AStar
- **Description**: BS-A双向搜索路径规划是一种结合了双向搜索策略的改进A算法。它从起点和终点同时开始搜索，当两个搜索路径相遇时，即找到了最短路径。
- **Primary Language**: Unknown
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2025-04-10
- **Last Updated**: 2025-06-10

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# BS-AStar

### 一、介绍
BS-A*双向搜索路径规划是一种结合了双向搜索策略的改进A星算法。它从起点和终点同时开始搜索，当两个搜索路径相遇时，即找到了最短路径。

#### （1）A*算法
一种启发式搜索算法，使用优先队列，每次扩展 **f(n)=g(n)+h(n)** 最小的节点，其中 **g(n)** 是起点到 **n** 的实际代价， **h(n)** 是 **n** 到终点的估计代价。A*算法流程图如图所示。

![A*算法流程图](image/AStar.jpg)

#### （2）双向搜索策略
BS-A* 算法采用正向和反向两个方向同时进行搜索，正向搜索从起点向终点扩展，反向搜索从终点向起点扩展。在搜索过程中，两个方向的搜索路径不断扩展，直到它们相遇，从而找到一条从起点到终点的完整路径。BS-A* 算法搜索过程示意图如图所示。

![BS-A*算法搜索过程示意图](image/schematic.jpg)

#### （3）启发式函数
为了提高搜索效率，BS-A*算法引入了启发式函数来估计从当前节点到目标节点的路径成本。常见的启发式函数包括欧几里得距离和曼哈顿距离。通过动态调整启发式函数的权重，可以进一步优化算法的性能。欧几里得距离公式为
![欧几里得距离公式](image/function2.jpg)

曼哈顿距离（Manhattan Distance）是几何学中的一种距离度量方式，用于计算两个点在网格路径上的距离。是两点在标准坐标系上的绝对轴距之和。对于二维空间中的两个点 **A(x1,y1)** 和 **B(x2,y2)** ，曼哈顿距离的计算公式为
![曼哈顿距离公式](image/function3.jpg)

#### （4）动态权重调整
在搜索过程中，BS-A*算法会根据当前的搜索状态动态调整启发式函数的权重。这种动态调整机制可以更好地平衡算法的探索能力和开发能力，从而在保证路径最优性的同时，提高搜索效率。

#### （5）栅格地图
栅格法是目前使用和研究较广泛的路径规划环境建模方法，它将自由空间划分为无重叠的栅格单元，每一格单独记录该栅格点的地形信息，网格被设置为空闲网格和已占用网格，空闲网格表示可以移动的位置，已占用网格表示此处有障碍物，则不能移动到此位置，使用栅格法建立的环境地图被称为栅格地图，二维栅格地图如图所示。

![二维栅格地图](image/grid_map.jpg)

二维栅格地图只能描述二维平面环境。数字高程地图是通过 **x** 和 **y** 描述坐标位置，用z表示坐标高度。对数字高程地图进行栅格化，将高程地图的信息赋予栅格点建立静态地图模型，栅格图中
每个栅格的具体位置用 **(x,y,z)** 表示。在高程栅格地图中，障碍物 **(Obstacles)** 用蓝色圆柱体表示，红色五角星表示起点 **(Start point)** 、绿色圆圈表示目标点 **(Goal point)** ，如图所示。

![高程栅格地图](image/elevation_grid_map.jpg)

### 二、算法流程
1.  **开始** 
初始化正向和反向的开放列表、关闭列表。
将起点加入正向开放列表，终点加入反向开放列表。
初始化 **g-score** 和 **h-score** 。
2.  **主循环** 
条件判断：如果正向或反向开放列表为空，跳转到 终止条件。
选择节点：
从正向开放列表中选择 **f-score** 最低的节点。
从反向开放列表中选择 **f-score** 最低的节点。
3.  **检查相遇** 
条件判断：
如果正向节点在反向关闭列表中，跳转到 路径重建。
如果反向节点在正向关闭列表中，跳转到 路径重建。
4.  **处理节点** 
扩展邻居节点：
对正向节点的邻居进行处理：
计算新 **g-score** ，更新邻居的 **g-score** 和 **f-score** 。
如果邻居不在开放列表中，将其加入。
对反向节点的邻居进行处理（类似正向）。
更新列表：
将正向节点从开放列表移除，加入关闭列表。
将反向节点从开放列表移除，加入关闭列表。
5.  **返回主循环** 
跳转到 主循环。
6.  **路径重建** 
从相遇节点开始，回溯父节点，重建路径。
返回完整路径。
7.  **终止条件** 
条件判断：
如果找到路径，返回路径。
如果未找到路径，返回空路径。

![BS-A*算法流程图](image/BS-AStar.jpg)

### 三、价值场景
-  **移动机器人路径规划：** 在移动机器人领域，BS-A*算法被广泛应用于路径规划。通过从起点和终点同时进行搜索，机器人能够快速找到一条最优路径，从而提高导航效率。
-  **无人机路径规划：** 在无人机的三维路径规划中，BS-A*算法结合三维栅格地图和障碍物信息，能够有效规划出安全、可靠的飞行路径，满足低空复杂环境下的飞行需求。
-  **游戏开发：** 在游戏地图中，角色需要快速找到最短路径，BS-A*算法能够显著提升游戏性能。
-  **物流规划：** 在物流配送中，路径规划的效率直接影响配送时间和成本，BS-A*算法能够优化配送路径，提高物流效率。
-  **自动驾驶：** 自动驾驶车辆需要实时计算最优路径，BS-A*算法的高效性使其成为理想选择。