论文阅读记录.md · qiaodl/Ship-Collision-Avoidance

[TOC]

# ~Path Planning Technologies for Autonomous Underwater Vehicles-A Review

## 1 Model-Building Methods for Path Planning（用于路径规划的模型生成方法）

### A. Regular Grid Terrain Model（规则网格地理模型）

#### 1) Grid Model（网格模型）

#### 2) Cell Tree Model（细胞树模型）

### B. Irregular Grid Terrain Model（不规则网格地理模型）

#### 1）Voronoi Diagram Model（泰森多边形法图模型、维诺图模型）

#### 2）Delaunay Triangulation Model（ Delaunay三角剖分模型）

#### 3）Visibility Graph Space Model (C-Space Model)

## 2 Path Search Algorithm for Path Planning（用于路径规划的路径搜索算法）

### A. Algorithm Based on the Geometric Model Search

#### 1）Dijkstra's Algorithm

Dijkstra算法利用贪心策略，通过广度优先搜索解决单一源最短路径问题（关于加权有向图或无向图问题）。

[AUVs水下环境全局路径搜索](S. Arinaga, S. Nakajima, H. Okabe, A. Ono, andY. Kanayama, ``Amotion planning method for an AUV,'' in Proc. Symp. Auton. Underwater Vehicle Technol., Monterey, Monterey, CA, USA, Jun. 1996, pp. 477484.)：避免一系列的障碍并到达终点；缺点：实验只停留在模拟阶段没有考虑实际环境影响。[pdf](./reference/Dijkstra's algorithm/Arinaga-A-motion-planning-method-for-an-auv.pdf)

[AUVs有向权重图单源最短路径问题](M. Eichhorn, ``A new concept for an obstacle avoidance system for the AUV `SLOCUM glider' operation under ice,'' in Proc. Oceans, Bremen, Germany, May 2009, pp. 572579.)：基于传统Dijkstra算法将时空环境作为额外的维度生成确切的结果。

[一种类似Dijkstra算法的滑动波前展开法（sliding wavefront expansion method）](M. Soulignac, P. Taillibert, and M. Rueher, ``Adapting the wavefront expansion in presence of strong currents,'' in Proc. IEEE Int. Conf. Robot. Automat., Pasadena, CA, USA, May 2008, pp. 13521358.//M. Soulignac, ``Feasible and optimal path planning in strong current elds,'' IEEE Trans. Robot., vol. 27, no. 2, pp. 8998, Feb. 2011.)：结合有效的损失函数和连续的运动模型达到良好的全局优化结果。

[改进的Dijkstra算法用于解决AUV动态避障问题](A. Kirsanov, S. G. Anavatti, and T. Ray, ``Path planning for the autonomous underwater vehicle,'' in Proc. 4th Int. Conf. Swarm, Evol., Memetic Comput. (SEMCCO), Chennai, India, Dec. 2013, pp. 476486.)：针对二维空间进行路径规划，考虑当前元素适当修改路径。

Dijkstera算法的不足：要求遍历所有结点，算法效率低，难以应用于大尺度复杂路径拓扑网络中。

#### 2）A* Algorithm（A*算法）

A*算法是基于Dijkstra算法改进而来，通过进一步计算当前结点于目标结点之间的估计损失来优化最终路径。如果A\*算法的估值为零，那么这两个算法是等价的。另外，A\*算法是解决静态路网最短路径规划问题的最优方法，此算法可以进一步理解成以下函数$f(n)=g(n)+h(n)$，等式左边$f(n)$代表从初始状态经过状态$n$到目标状态的代价估计；等式右边$g(n)$代表从初始状态到状态$n$的实际代价，$h(n)$代表从状态$n$到目标状态最佳路径的估计代价。

利用A*算法完成水下路径规划的文献有以下几组：

- A. R. Anwary, ``Comparison of fuzzy BK-product and A* search algorithm for optimal path nding in unsupervised underwater environment,'' in Proc. 8th Int. Conf. Appl. Electromagn., Wireless Opt. Commun., Houston, TX, USA, Apr./May 2009, pp. 5763.

文章中论证了A*算法在水下复杂环境中完成路径搜索任务的有效性和优点。

- B. Garau, A. Alvarez, and G. Oliver, ``Path planning of autonomous underwater vehicles in current elds with complex spatial variability: An A* approach,'' in Proc. IEEE Int. Conf. Robot. Automat., Barcelona, Spain, Apr. 2005, pp. 194198.

J.-H. Li, M.-J. Lee, S.-H. Park, and J.-G. Kim, Real time path planning for a class of torpedo-type AUVs in unknown environment,'' in Proc. IEEE/OES Auton. Underwater Vehicles, Southampton, U.K., Sep. 2012, pp. 16.

文章中考虑了海洋环境因素影响，通过模拟和仿真实现A*路径搜索。

- 以及其他针对A*的优化算法

#### 3）D* Algorithm（D*算法）

D*算法是美国火星探测器核心路径算法，在动态环境中表现得更加高效。事实上，D\*算法是一个动态A\*算法，其利用初始规划信息进行路径不完全重规划。结合最优和实时原则，将全局路径和局部信息融合、离线规划和在线规划融合。

- P. Miotto, J. Wilde, and A. Menozzi, ``UUV on-board path planning a dynamic environment for manta test vehicle,'' in Proc. MTS/IEEE Conf. Celebrating PastTeaming Toward Future, San Diego, CA, USA, Sep. 2003, pp. 24542461.

文章中作者将D*算法、B-spline曲线生成器和模型预测控制算法三者结合应用于导航控制路径规划系统，模拟实验有效证明这种方法可以达到动态避障。

#### 4）D* Lite Algorithm

D*算法是基于Dijkstra算法演变而来，解决起点随时间变化，目标点固定问题，并且主要面向路径搜索算法优化。

#### 5）Fast Marching Algorithm（FM）

类似Dijkstra算法，利用非线性偏微分方程更新结点状态。[Yu and Wang](H. Yu and Y. Wang, ``Multi-objective AUV path planning in large complex battleeld environments,'' in Proc. 7th Int. Symp. Comput. Intell. Design (ISCID), Hangzhou, China, Dec. 2014, pp. 345348.)考虑了水下自主航行器的机动约束，例如改向角、安全深度和避碰危险度等因素，结合FM算法在三维环境中解决了航行器目标丢失后自主路径搜索问题。

- H. Yu, A. Shen, and Y. Su, ``Continuous motion planning in complex and dynamic underwater environments,'' Int. J. Robot. Automat., vol. 30,
  no. 2, pp. 192204, 2015.

**HSMF**加入多重约束和决策标准的前提下，减小路径长度和缩短计算时间。

#### 6）Level Set Method（LSM）

利用a backtrack isometric contour获得最优路径，高效得生成动态过程。

#### 7）Boustrophedon Decomposition Algorithm（布氏分解算法）

一种简单的覆盖路径搜索方法，该算法需要将整个环境划分为子区域，然后用一个简单的“梳状”倒数来覆盖它们。

#### 8）Internal Spiral Algorithm（ISA）

#### 9）Other

- J. Cao and C. Sun, ``A mission planning system for an autonomous underwater vehicle,'' in Proc. 7th World Congr. Intell. Control Automat., Chongqing, China, Jun. 2008, pp. 39153919.

### B. Probabilistic Sampling-based algorithm

#### 1）Probabilistic Roadmap Method（ 随机路径图法 ）

随机路径图法的核心是采样和建立路径网，并在生成路径网中查询最优结果。可有效避免障碍物的同时模拟姿态空间。参见<u>J. McMahon and E. Plaku, ``Mission and motion planning for autonomous underwater vehicles operating in spatially and temporally complex environments,'' IEEE J. Ocean. Eng., vol. 41, no. 4, pp. 893912, Oct. 2016.</u>

#### 2）Rapidly Exploring Random Tree（ 快速搜索随机树 ）

具有强大的空间搜索能力，

### C. Artificial Potential Field Type Algorithm

#### 1）Artificial Potential Field（APF）

该算法最初是应用于机械臂操作空间的路径搜索问题，并且广泛利用于机器人路径规划领域。算法前提是构建一个势场函数，障碍物产生一个斥力，目标点产生一个引力，船只在这个人工势场所受合力即为其运动大小和方向。不足之处是APF在动态环境中难以满足简单、安全、快速和易于实施等特点。

参见：

[133] F. J. Solari, A. F. Rozenfeld, V. A. Sebastián, and G. G. Acosta, ''Articial potential elds for the obstacles avoidance system of an AUV using a mechanical scanning sonar,'' in Proc. IEEE/OES South Amer. Int. Symp. Ocean. Eng., Buenos Aires, Argentina, Jun. 2017, pp. 16.

[134] S. Subramanian, T. George, and A. Thondiyath, ``Obstacle avoidance using multi-point potential eld approach for an underactuated at-sh type AUV in dynamic environment,'' in Proc. 1st Int. Conf. Intell. Robot., Automat. Manuf. (IRAM), Nov. 2012, pp. 2027.

改进的APF：

- 速度合成算法【135】

- APF和PSO（粒子群优化）结合【136】
- LOS和APF结合【137】

- 克隆选择机制的优化算法用于路径搜索，APF用于动态避障【138】
- mmpf【140】

#### 2）BUG Algorithm

### C. Intelligence Algorithm

![1571406575728](.\附件\1571406575728.png)

# ~COLREGS-Constrained Real-time Path Planning for Autonomous Ships Using Modified Artificial Potential Fields

引言部分详细介绍了USV（Unmanned Surface Vehicles，水面无人船只（艇））在国际海上避碰规则约束下的相关研究。列表叙述几种典型方法的比较，包括国际海上避碰规则依赖程度、静态及动态障碍物数量和形状、目标船舶的运动特征（航向和航速的变化）、动态属性、本船在避障动作中的速度变化和紧急避障措施、解决措施的计算时间和可重复性。 有些需求是基于已定义标准的实现(表中是)或未实现(表中不是)来评估的。

## Path planning problem

本文主要针对动力驱动船舶在复杂环境模型中解决路径规划问题，环境模型包含静态约束和动态目标船舶。

### Environment

环境数据由助航设备采集，包括AIS、Radar、DGPS，额外信息可以由ECDIS提供。从所输入的数据中应当能够提取到静态障碍物和动态障碍物（目标船舶）的实时位置、速度和航向信息。静态障碍物的碰撞形状可简化为圆形目标，并且按照速度为零的目标船只处理，所以作者没有考虑目标物的非常规形状。但是作者解释说圆形障碍物更加简单和容易扩展到其他形状，相关文献指出使用离散障碍点作为海岸线和多边形陆地，近似于圆形。

### Requirement

船舶路径规划需要以下5点需求：

- 避免所有移动或静止的障碍物的能力
- 国际海上避障规则约束行为和良好的船艺
- 几乎是实时的在线避碰操作或路径规划
- 考虑目标船只航向变化，甚至是不协调的航行行为
- 在一个解决方案中考虑本船动态特性

### The Proposed Strategy

#### 碰撞危险评估（包含两因素）

- CC：碰撞危险决策
- CR：碰撞危险距离

#### 改进APF决策

### Model of the Ship's Motion

![1571818649442](.\附件\1571818649442.png)

# ~A Path Planning Approach Based on Multi-direction A* Algorithm for Ships Navigatiing within Wind Farm Waters

## 主要内容

离岸风电场区域工作船舶的航迹规划对保障航行安全和提高航行效率有着显著意义。文中作者着重解决全局航线规划问题，采用一种全局多方向A*算法，并从三个方面详细介绍了改进内容。1）APF用标量形式表示，以避免工作船从两个过近障碍物之间穿过；2）每一步的移动距离都是根据复杂的周围环境进行调整，改进传统A\*算法中方向判断不足，在复杂度和效率之间谋求平衡；3）根据水下管道线路提出判决模式，作为较为重要的模块，保障工作船仅穿越管道一次。作者通过仿真实验论证了20-方向的A\*算法的有效性，并且比较实际航迹，在保障安全航行的前提下，航迹长度减少了5000m。

## Modelling of obstacles（障碍物建模）

### - 网格尺寸

障碍物抽象成一系列网格，网格大小是影响算法性能的关键，关系船舶实际航行的安全性和经济性。<u>In the original version of the A* algorithm, the size of the grid is supposed to be the same as that for a moving robot (Shukla et al., 2008).</u>文中指出传统A*算法中所采用的网格大小是根据移动对象（本船）大小设定的，即，占满一个单元格。

### - 危险区域识别

危险区域包含：浅水区、固定障碍物以及其他船只。单纯依靠传统两状态的A*算法，难以解决边界问题，因而本文作者将APF的概念引入反映目标物危险程度，将离散状态连续化，其值控制在（0，1）。

![1571821715447](.\附件\1571821715447.png)

作者提出传统APF斥力函数是一个矢量，在两个对称的障碍物的中垂线上，斥力最小，但是不满足实际作业安全需求。标量形式如下：

![1571822128039](.\附件\1571822128039.png)

## Path generation（路径生成）

![1571830770290](.\附件\1571830770290.png)

### - 多邻近结点生成

由于传统A*算法是限制了可用方向，比方说两点之间没有障碍物情况下生成的轨迹可能都不是直线。因为两点不在网格的水平或竖直方向上，这样增加了船舶在实际航行过程中的操作负担，并且较大的转向角从船舶操纵角度而言就是难以实现的（最大转舵角）。

采用更多结点的方式解决上述问题：

### - 结点去除

### - 路径规划流程

![image-20191024154006017](.\附件\image-20191024154006017.png)

![image-20191024154024952](.\附件\image-20191024154024952.png)

![image-20191024154043745](.\附件\image-20191024154043745.png)

# ~基于A*算法和人工势场法的移动机器人路径规划

## 主要内容

针对复杂非结构化环境下移动机器人的路径规划问题，提出了将全**局与局部规划算法相融合**的路劲规划方法。

### 重点问题：环境建模和路径规划

## 1 A*全局路径规划算法

### 1.1 环境模型描述

将被控目标看作在二维平台上移动的点状物体。利用栅格法将每一块分割的单元区分为4种状态（起始点、无障碍点、障碍点、终点）

栅格大小和目标物半径和机器人半径相关，并且目标与机器人之间留有一定安全距离：

$l=\sqrt{2}(r+R)+\delta$

### 1.2 A*全局路径规划算法

$f(n)=g(n)+h(n)$中$g(n)$为从起点到当前结点的实际代价值，$h(n)$是当前点到终点的代价估计值，本文作者将后者用两点之间的欧氏距离作为定义。利用传统A*算法对目标进行全局路径规划，进一步利用二次A\*算法优化目标路径长度，具体是通过优化路径点序列和平滑处理路径来达到目的。

## 2 改进人工势场局部路径规划算法

### 2.1 虚拟子目标增设

障碍物和目标点对机器人产生的排斥力和吸引力相等时，机器人会陷入局部最小值陷阱中。本文作者提出使用增设虚拟子目标法，借助虚拟外力是机器人摆脱外力。

### 2.2 自适应步长调节

略

# ~Ship Collision Avoidance and COLREGS Complaiance Using Simulation-Based Control Behavior Selection With Predictive Hazard Assessment

## 主要内容

本文主要叙述一个基于模型预测控制技术的船舶避碰系统

# ~水运湖交流内容——基于加权统计/分布式卡尔曼的目标船Ais和Radar航迹信息融合方法

## 1.1 信息融合的必要性

**GPS解析：**获取本船位置

**AIS解析：**获取周围船舶动/静态信息，也可以通过甚高频（VHF）将本船信息广播至周围船舶或岸基站。AIS船舶定位是由差分全球导航定位系统（GNSS）提供保障，其精度普遍满足海上航行需求，所以默认所接收并解析的AIS数据中关于其他船舶的经纬度信息，能够作为当前时刻船舶位置。AIS不足之处在于，与船只航行状态相关的信息更新速率较慢。一般情况下，船只以正常速度（14-23节）航行，每6秒广播一次动态信息。本船所绘制的关于目标船舶的航迹点，每次更新即产生平均60米（$20*1.852 km / h * 6 s * 1000 m$）的距离差。

**雷达数据解析：**获取ARPA雷达捕获、跟踪的目标信息，其中包含周围船只、漂浮物等动态目标信息，也包括雷达观测半径内的陆地、岛屿等静态信息，并且伴随海浪、大雾等杂波干扰，导致出现虚假目标影响雷达探测精度。

整个**融合过程**包含以下几个步骤：

1. 数据**采集**
2. 数据**解析**
3. **时空统一**
4. 航迹**关联**
5. 数据**融合**

## 1.2 船舶航迹预处理

### 1.2.1 坐标转换

#### 1）ARPA雷达位置信息转换

#### 2）AIS位置信息转换——墨卡托投影

### 1.2.2 时间匹配——以雷达信息的采样时间间隔为基准

## 1.3 船舶航迹关联

**基于时间-距离的粗关联**和上述基础上的**基于模糊因素评判的双门限细关联**

## 1.4 船舶航迹融合

### 1）对判定为固定关联的目标进行加权统计融合

### 2）基于分布式卡尔曼信息融合算法——陈鹏

# ~贺益熊——规则量化解析下船舶自动避碰模型与仿真研究

## 第一章 绪论

### 1.1 研究背景与课题来源

在“人-船-环境”组成的船舶操作系统中，海上自然环境是难以改变的，且考虑到航海职业发展、良好船艺船员减少的特点，只有从技术上提高船舶自动化程度才是解决船舶航行安全的根本方法。

### 1.2 研究范围、目的与意义

几个关键的环节尚需攻克：

1. 交通环境信息的实时获取、接口技术与信息处理
2. 船舶自动避碰和路径规划研究
3. 风浪流条件下的数字船舶模型系统辨识研究
4. 基于系统控制的船舶自动避碰方案实船操纵实现

在良好天气条件下的开阔水域中率先实现船舶自动避障，能有效缓解船员日常工作强度、减小因长时间值班状态下的人为操作失误，降低船舶运行成本。

开阔水域环境条件下的船舶自动避碰，是实现更为复杂地理环境模型的前提。同时考虑全局最优路径规划，提出相关模型、仿真以及验证。

本文研究主要考虑以下两方面：

1. **船舶操作性能**，考虑**航海实践**
2. 严格遵守**《避碰规则》**，符合**船员操作习惯**（规则第二条用语，近似良好船艺，前者注重某种情况下通常应采取的措施，后者更注重这些措施的具体实施技能）

- 研究目的

将船舶路径规划相关研究分为以下**两类**：

- **船舶避碰：**关于避碰，航海实践中人们主要把避碰系统分为两个方面，避碰系统（船舶间碰撞）和避礁系统（搁浅触礁）。本文所研究的自动避碰是指通过船舶的自动避碰决策系统为防止本船与目标的碰撞而自动生成由多个操作行为组成的方案并予以执行的过程。
  - **路径规划：**根据已知地理环境信息，通过一定寻优算法寻找一条从给定初始位置到达目标位置的无碰撞路径，并且要求航行路径能满足一定的约定约束条件（遵守规则）和一定的优化准则（符合规则的前提下转向幅度最小且路径最短）。

- 研究内容的前提

- 本船是一艘普通的机动船，场景为天气良好的开阔水域，周围由多艘机动船和多个其他目标（特殊目标）
  - 不考虑减速避让和协调避让
  - 目标位置、速度矢量已知，且抽样间隔中速度不变

最终完成在船舶避碰基础上的路径规划。

#### 1.2.3 研究意义

- 宏观层面

1. 减少人为因素造成的船舶碰撞事故
2. 减轻船舶驾驶人员劳动强度
3. 降低船舶运营成本

- 技术操作层面

1. 弥补以往船舶自动避障与路径规划研究工作的不足
2. 为后续研究人员搭建一个可行平台

### 1.3 研究线路和结构

## 第二章 自动避碰与路径规划研究现状

### 2.3 理论研究基础

#### 2.3.1 船舶领域理论

FUJII于1971年基于日本沿海水域的交通调查和统计方法提出，主要适用于狭窄水域的椭圆形船舶领域。

Goodwin于1975年提出由三个不等扇区组成的船舶领域。

DAVIS提出边界连续的偏心圆船舶领域模型和超级船舶（动界）模型。

COLDWELL于1983年建立基于交通情景的限制水域船舶领域模型，对遇局面船舶领域模型为半椭圆形，目标船向左偏移，追越局面与FUJII模型基本相同。

PIETRZYKOWSKI于2009年基于不同来船方向的经验统计和船舶碰撞分析模型，提出了适用于开阔水域的多边形船舶领域模型。

#### 2.3.2 船舶运动模型

MMG（Mathematical Model Group），一种基于分离思想的船舶运动数学模型，利用此模型仿真船舶转向中的运动过程。

- K-T指数模型：将船舶看作一个动态系统，利用操纵运动响应模型，计算船舶在操舵后的运动参数。
- 基本运动方程模型：通过确定方程中所包含的水动力系数，然后基于初始条件求解方程。
  - 整体式水动力模型：将船体、螺旋桨和舵作为一个整体，不考虑互相干扰。
  - 分离式水动力模型（MMG学派）：将船体、螺旋桨和舵所受水动力分开考虑，充分考虑他们之间互相影响的基础上进行叠加。

#### 2.3.3 碰撞危险度模型

碰撞危险度（Collision Risk Index，CRI）是指微观危险度，由空间碰撞危险度（SCRI）—时间碰撞危险度（TCRI）构成，用于评价船舶会遇中的碰撞风险评价。

#### 2.3.4 速度障碍

速度障碍是指如果目标和障碍物保持当前运动状态，所有可能导致目标船与障碍物发生碰撞的速度集合。

#### 2.3.5 规则

Rule 8：

## 第三章 船舶避碰态势判断模型

qiaodl/Ship-Collision-Avoidance

简介

发行版

贡献者

近期动态

qiaodl/Ship-Collision-Avoidance .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

近期动态

搜索帮助

qiaodl/Ship-Collision-Avoidance