Zhu H, Cao C, Xia Y, et al. DSVP: Dual-stage viewpoint planner for rapid exploration by dynamic expansion[C]//2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2021: 7623-7630. [PDF](http://www.hongbiaoz.com/files/paper7.pdf)





## 1. 概述

该论文提出了一种有效地探索高度复杂的环境的方法。该方法包括**两个规划阶段：**

- 探索阶段：在环境的自由空间中开发一个局部快速探索随机树（RRT），负责地图边界的扩展
- 重新定位阶段：通过映射环境维护一个全局图，将机器人转移到环境中不同子区域
- 机器人在两个阶段中来回切换，探索环境中的所有区域

![image-20230312134957471](https://store.southyang.cn/project/docs/image-20230312134957471.png)

灰色区域：未知空间；黄色点：局部边界点；紫色点：全局边界点；蓝色方块：机器人；红色点线：全局地图；蓝色点线、箭头：局部树；黄色线：探索路径；紫色线：重定位路径

**对RRT框架的扩展：**

- 动态扩展：在RRT上被遮挡或超出规划范围的节点将被修剪。然后，在自由空间中采样新的节点。
- 混合边界：在与RRT节点相关的传感器范围以及机器人周围提取的边界。

## 2. 方法

在探索阶段，机器人视场内的边界以及RRT节点被提取为局部边界。

在重新定位阶段，全局边界由最新更新被清除的局部边界组成，帮助机器人从全局图中所有剩余的视点中选择最好的一个。

### 2.1 探索阶段

![image-20230312140426196](https://store.southyang.cn/project/docs/image-20230312140426196.png)

(a)为在前一次迭代中获得的RRT和局部边界。黄色圆圈是局部边界点。绿色方形表示规划范围。

(b)是当前迭代中生成的新RRT。蓝点代表来自上一次迭代RRT中的有用视点，橙色的点是新的采样视点。$F_{LS1}$和$F_{LS2}$、$F_{LS3}$是三个选定的局部边界，用于指导局部树的扩展。黄色的空心圆圈是所选边界的传感器范围。

该阶段通过使用动态扩展的RRT，在每次迭代中生成机器人周围的视点。通过动态展开，每次迭代中只重新生成一小部分节点，与完全构建新树相比，计算量更少。在每次迭代开始时从所有局部边界中选择$F_{LS}$。然后，在$F_{LS}$的指导下，对前的树进行修剪重建后，对新的视点进行采样。

<img src="https://store.southyang.cn/project/docs/image-20230312141657036.png" width=50% />

选择最佳分支进行下一步探索

<img src="https://store.southyang.cn/project/docs/image-20230312141756926.png" width=50%/>

动态扩展RRT

### 2.2 重定位阶段

当在探索范围内没有局部边界时，算法将从探索阶段切换到重定位阶段。

重定位阶段涉及到全局图和全局边界：

- 全局图的主要用途是记录在探索阶段采样的所有有价值的视点，并寻找两个视点之间的最短路径。因此在探索阶段的每次迭代中，会将具有正增益分支中的视点作为顶点添加到全局图中。

- 全局边界$F_G$是由探索阶段被遗漏的局部边界组成的。可以通过全局图中的至少一个视点来观察到。每次更新局部边界时，它们都会被添加到$F_G$中。

<img src="https://store.southyang.cn/project/docs/image-20230312144321715.png" width=50%/>

4-14行：从距离机器人的最近位置选取全局边界点，并记录观测到该边界点的第一个视点$v_s$

15-23行：选择距离该边界点最近的视点，更新$v_s$

寻找到$v_s$后，机器人沿着重定位路径移动至该视点，切换到探索阶段

24行：如果不存在全局边界点，则结束探索

![image-20230312144818157](https://store.southyang.cn/project/docs/image-20230312144818157.png)

## 3. 实验

实验环境：cmu的室内、校园、车库环境

对比实验：NBVP、GBP、MBP

![image-20230312145118582](https://store.southyang.cn/project/docs/image-20230312145118582.png)

## 4. 总结

动态扩展降低构建RRT的运算量

混合边界点确保对环境的完全覆盖

DSVP: Dual-Stage Viewpoint Planner for Rapid Exploration by Dynamic Expansion

> 由于在学习配置时，网上的教程比较杂乱，用时很久才做好一些基础配置，把流程记录一下方便和我一样的小白学习
>
> 本文写于2023.2.25，如果间隔太久，下述内容可能会失效，请另寻教程



### 1. 安装

1. 下载 Node.js 安装程序。可以从 Node.js 官网下载适用于 Windows 的 Node.js LTS安装程序（https://nodejs.org/en/download/）。

2. 运行 Node.js 安装程序并按照提示安装 Node.js。（一直下一步）

3. 安装完成后，打开命令提示符或 PowerShell 终端窗口（按下 Win+R，键入 "cmd" 或 "powershell" 并按 Enter 键）。

4. 在终端窗口中输入以下命令以确认是否已安装 npm：

   ```shell
   npm -v
   # v18.14.2
   ```

   如果已成功安装 npm，则将显示 npm 的版本号。

   如果未安装 npm，则需要安装。可以使用以下命令在命令提示符或 PowerShell 终端窗口中安装 npm：

   ```shell
   npm install npm@latest -g
   ```

   此命令将在全局范围内安装最新版本的 npm。

5. 等待安装完成后，可以在命令提示符或 PowerShell 终端窗口中输入以下命令来验证 npm 是否已成功安装：

   ```shell
   npm -v
   # 9.5.0
   ```

   如果 npm 成功安装，则将显示 npm 的版本号。

现在已经成功安装了 npm。请注意，如果使用的是 Windows 10 的某些版本，则可能需要在安装 npm 时使用管理员权限。

### 2. 配置

npm的两个配置文件夹`node_cache`和`node_global`默认存放在C盘，可以手动进行更改

1. 在想要的位置新建两个文件夹，命名为`node_cache`和`node_global`，例如我存放在`D:\Software\Develop Tool\Nodejs\configuration`中

2. 打开cmd，配置路径

   ```sh
   npm config set prefix "D:\Software\Develop Tool\Nodejs\configuration\node_global"
   npm config set cache "D:\Software\Develop Tool\Nodejs\configuration\node_cache"
   ```

   ```shell
   # 部分config命令
   npm config ls # 查看简单的配置项
   npm config ls -l  #　查看所有配置项
   npm config get cache  # 查看缓存配置，get后面可以跟任意配置项
   npm config edit  # 直接编辑config文件，这个会打开文本
   npm info underscore # 检测镜像源
   ```

3. 配置环境变量

   系统变量：新建变量名：NODE_PATH 变量值：node_global文件夹下的node_modules文件夹。我的是：D:\Software\Develop Tool\Nodejs\configuration\node_global\node_modules

   用户变量：将Path变量中默认的npm路径修改为新建的node_global路径：D:\Software\Develop Tool\Nodejs\configuration\node_global

4. 测试并配置淘宝源

```shell
npm config set registry https://registry.npm.taobao.org # 全局切换淘宝源
npm config set registry https://registry.npmjs.org/ # 全局切换官方源
```

Win10安装配置Nodejs和npm

Zhou, Boyu, et al. "Fuel: Fast uav exploration using incremental frontier structure and hierarchical planning." *IEEE Robotics and Automation Letters* 6.2 (2021): 779-786. [PDF](https://arxiv.org/pdf/2010.11561.pdf)



## 1. 概述

**存在的问题：** 缺乏最优性考虑，进行保守的运动计划和较低的决策频率，导致整体探索效率偏低

**贡献点：**

- 提出一个逐步更新的FIS（边界信息结构），捕获整个探索空间的基本信息，并进行高频率的探索规划；
- 提出一种分层规划方法，生成有效的全局覆盖路径，进行安全快速的局部运动。

![image-20230208205713211](https://store.southyang.cn/project/docs/image-20230208205713211.png)

## 2. 方法

**大体流程：** 每当使用传感器的测量值更新地图时，都会检查是否有边界集群受到影响。受影响集群的FIS被删除，同时提取新的边界和FIS。随后进行探索规划，先确定全局覆盖路径，再细化局部视点，并依次生成到选定视点的轨迹。如果没有边界存在，则认为探索已完成。

### 2.1 增量式前沿信息结构

边界探索是通过处理整个地图来检索的，对于大场景和高规划频率是不可扩展的。该论文通过增量的方式来进行边界探索，降低了整体运算量，可以进行更精细的规划。

**边界信息结构**

当创建一个新的边界集群时，都会计算出对应的边界信息结构FIS。存储集群的所有单元格$C_i$和对应的平均位置。

**增量式边界检测和聚类**

通过传感器测量更新地图时，也会记录更新区域的边界框，删除旧的边界簇，通过区域增长算法搜索新的边界簇。如果有大规模的集群，就递归地进行拆分，以便所有的大集群都被划分为小的集群，便于进行局部探测。

<img src="https://store.southyang.cn/project/docs/image-20230208205934089.png" width=60% />

**视点生成和代价更新**

当创建集群时，生成一组视点$VP_i= \lbrace x_{i,1}、x_{i,2}、···、x_{i,n_i} \rbrace$覆盖它。$VP_i$是通过在原点位于簇中心的圆柱坐标系中的均匀采样得到的。为了进行全局规划，需要每两个集群的连接代价，计算视点之间移动的时间下界；选择覆盖范围最大的视点来计算集群的连接代价。

![image-20230208210554291](https://store.southyang.cn/project/docs/image-20230208210554291.png)

### 2.2 分层探索规划

<img src="https://store.southyang.cn/project/docs/image-20230208210837306.png" width=60%/>

**全局探索规划**

首先寻找一个全局最短路径，从当前视点出发，覆盖现有的边界集群。通过不对称的TSP问题进行规划。

**局部视点细化**

全局探索规划找到了一个最短路径来访问所有的集群。但只涉及每个集群的单一视点，并不一定是所有视点中的最佳组合。通过局部视点细化，寻找最优路径。

**最小时间B样条轨迹**

根据给定离散的视点，生成平滑、安全和动态可行的b样条轨迹；进一步优化B样条曲线的参数，使总轨迹时间最小化。

## 3. 实验

**实验环境：** 桥、大型迷宫

**探索效率**

<img src="https://store.southyang.cn/project/docs/image-20230208211407932.png" width=60% />

**实验指标统计**

<img src="https://store.southyang.cn/project/docs/image-20230208211514765.png" width=50% />

## 4. 总结

在基于边界的探索策略中，加入分层探索思想，通过增量的方式降低运算量，提高了决策频率，并优化局部路径。

状态估计能力需要提高。

FUEL: Fast UAV Exploration using Incremental Frontier Structure and Hierarchical Planning

Yang, Fan, et al. "FAR planner: Fast, attemptable route planner using dynamic visibility update." *2022 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)*. IEEE, 2022.  [PDF](https://arxiv.org/pdf/2110.09460.pdf)



## 1. 概述

**基于可见性图的规划方法**

- 主要困难：在构建可见性图时，需要进行大量的计算，特别是在复杂三维环境中。（构建多边形）

- 主要优点：具有快速重新规划方面的优势，以及处理未知和部分已知环境的能力。

**贡献点**

- 提出一种多边形提取和增量可见性图构建的两层算法框架；

- 该框架能够动态地调整可见性图，以便在未知的环境下进行可尝试的导航并处理动态障碍；

**实验结果：** 在未知的和部分已知的环境中，达到了基准测试的最先进规划性能。

![image-20230205222517016](https://store.southyang.cn/project/docs/image-20230205215141836.png)

彩色曲线是从蓝点开始到红点结束的车辆轨迹。

青色线：在导航过程中建立的可见性图，用于引导车辆达到目标。

红色区域：观察到的全局环境。

黄色区域：表示用于更新局部图的局部环境。

## 2. 方法

### 2.1 障碍多边形的提取与记录

对于地面车辆，通常会在系统中运行一个地形可穿越性分析模块来分析地形特征。该模块从激光雷达或深度摄像机进行距离测量，输出$S$表示障碍物。根据$S$中的数据，构造二值图像，对二值图像做平均过滤，生成模糊图像，由此提取多边形组。从每个多边形中提取顶点，并根据内角清除部分顶点，得到最终的多边形。

<img src="https://store.southyang.cn/project/docs/image-20230205215628243.png"/>



### 2.2 两层可视性图的动态更新

通过增量的方式，只更新车辆附近的区域，由此对可视性图进行逐步更新，将计算均匀地分配到每个数据帧，有效降低了计算代价。

**构建局部层：** 对于$\mathcal E_{local}$中超过阈值的边，忽略了连接一个或两个多边形的不必要的边，并保留了“传递”边

<img src="https://store.southyang.cn/project/docs/image-20230205220226779.png"/>



**更新全局层：** 在局部上构造局部可见性图后，将局部与全局合并，更新与局部重叠区域的全局区域。

- 对局部图和全局图的顶点进行关联。
- 通过迭代消除离群值关联。
- 对局部边进行合并。

<img src="https://store.southyang.cn/project/docs/image-20230205221313003.png"/>

### 2.3 可视性图的规划

给定当前位置和目标位置，想在可视性图$G$中搜索当前点和目标点之间的最短路径。

- 首先将$p_{position}$和$p_{goal}$添加为全局层上的两个顶点，并将它们连接到具有非阻塞可见性边的$P^l_{global}$中的顶点。
- 在$\mathcal L_{global}$上运行广度优先搜索，如果有路径可用，则找到$p_{position}$和$p_{goal}$之间的最短路径。

### 2.4 扩展到三维多层可视性图

扩展三维版本的方法是将环境建模为多个水平切片，并提取多层多边形。

<img src="https://store.southyang.cn/project/docs/image-20230205221456289.png"/>

## 3. 实验

实验平台为地面车辆和无人机

实验内容：车辆：室内、室外、大型隧道；无人机：室外

**中等尺度、中等复杂的室内环境中的地面车辆模拟：**

<img src="https://store.southyang.cn/project/docs/image-20230205222136.png" width=50%/>

**数据分析：**

<img src="https://store.southyang.cn/project/docs/image-20230205222517016.png" width=58%/>

## 4. 结论

通过构造可视性图，来实现一个底层的场景图，具有快速重新规划方面的优势，以及处理未知和部分已知环境的能力。

通过分层和增量的方式来降低运算量

FAR Planner: Fast, Attemptable Route Planner using Dynamic Visibility Update

> 由于在学习配置时，网上的教程比较杂乱，用时很久才做好一些基础配置，把流程记录一下方便和我一样的小白学习
>
> 本文写于2023.2.10，如果间隔太久，下述内容可能会失效，请另寻教程





**仅包含基础教程，个人服务未涉及到负载均衡**

- 安装nginx
- 配置静态服务器
- 配置端口转发
- 配置域名
- 配置https

**服务器：** 阿里云ubuntu20.04

**nginx版本：** nginx/1.18.0 (Ubuntu)

### 1. 安装nginx

#### 1.1 安装及常用命令

```shell
# 更新apt-get源
sudo apt-get update
# 安装
sudo apt-get install nginx
# 安装后将自动开启nginx服务，打开浏览器输入ip即可查看初始页面
```

```shell
# 查看安装版本
nginx -v
# 输出:nginx version: nginx/1.18.0 (Ubuntu)
```

```shell
# systemctl命令
# 查看状态
sudo systemctl status nginx
# 启动
sudo systemctl start nginx
# 停止
sudo systemctl stop nginx
# 重启
sudo systemctl restart nginx
```

**注意：**对nginx配置文件修改之后，都要**重启nginx服务**，加载修改后的配置文件

#### 1.2 文件结构

```shell
# 查看文件结构
tree /etc/nginx
```

```shell
/etc/nginx
├── conf.d
├── fastcgi.conf
├── fastcgi_params
├── koi-utf
├── koi-win
├── mime.types
├── modules-available
├── modules-enabled
│   ├── 50-mod-http-image-filter.conf -> /usr/share/nginx/modules-available/mod-http-image-filter.conf
│   ├── 50-mod-http-xslt-filter.conf -> /usr/share/nginx/modules-available/mod-http-xslt-filter.conf
│   ├── 50-mod-mail.conf -> /usr/share/nginx/modules-available/mod-mail.conf
│   └── 50-mod-stream.conf -> /usr/share/nginx/modules-available/mod-stream.conf
├── nginx.conf
├── proxy_params
├── scgi_params
├── sites-available
│   └── default
├── sites-enabled
│   └── default -> /etc/nginx/sites-available/default
├── snippets
│   ├── fastcgi-php.conf
│   └── snakeoil.conf
├── uwsgi_params
└── win-utf
```

#### 1.3 配置文件内容

**nginx.conf** （为了方便看，我删掉了初始内容中所有带注释的代码）

```nginx
user www-data;
worker_processes auto;
pid /run/nginx.pid;
include /etc/nginx/modules-enabled/*.conf;

events {
	worker_connections 768;
}

http {

	sendfile on;
	tcp_nopush on;
	tcp_nodelay on;
	keepalive_timeout 65;
	types_hash_max_size 2048;

	include /etc/nginx/mime.types;
	default_type application/octet-stream;

	ssl_protocols TLSv1 TLSv1.1 TLSv1.2 TLSv1.3; # Dropping SSLv3, ref: POODLE
	ssl_prefer_server_ciphers on;

	access_log /var/log/nginx/access.log;
	error_log /var/log/nginx/error.log;

	gzip on;

	include /etc/nginx/conf.d/*.conf;
	include /etc/nginx/sites-enabled/*;
}
```

最关键的是下面两行引入，上面的代码含义目前我还没研究，用到再说

```nginx
include /etc/nginx/conf.d/*.conf;
include /etc/nginx/sites-enabled/*;
```

这两行的意思是：从conf.d中加载所有后缀为conf的文件，从sites-enabled中加载所有文件，均作为配置文件

sites-enabled文件我用不习惯，因此我注释掉了这行，使用conf.d做配置文件

**在conf.d中添加`static.conf`**

```nginx
server {
    listen       80;
    server_name  localhost;

    charset utf-8; # 防止中文显示出现乱码

    #access_log  logs/host.access.log  main;

    location / {
        root   /var/www/html; # 你的静态资源路径
        index  index.html index.htm;# 访问的文件为html, htm
    }
}
```

要注意的是，在`/var/www/html`目录中，文件的名字不是`index.html`，原名为`index.nginx.debian.html`，改成前者即可。

通过三处修改，完成从`sites-enable`到`conf.d`的迁移

- 在`nginx.conf`中注释掉`include /etc/nginx/sites-enabled/*;`
- 在`conf.d`目录下新建`static.conf`，添加如上文件内容
- 修改`/var/www/html`目录中的文件名为`index.html`

```shell
# 检查配置文件是否有误
nginx -t
# nginx: the configuration file /etc/nginx/nginx.conf syntax is ok
# nginx: configuration file /etc/nginx/nginx.conf test is successful

# 重启服务
sudo systemctl restart nginx
```

### 2. 配置静态服务器

自行寻找一个网页做测试，上传到`/var/www/html`

我上传了之前写过的一个markdown在线编辑器，是一个文件夹，文件夹名为`markdown`

**开始修改`static.conf`文件**

```nginx
server {
    listen       80;
    server_name  localhost;

    charset utf-8; # 防止中文显示出现乱码

    # 根据自己需要配置日志文件，可以单独配置，也可以全部放在/var/log/nginx的日志中
    #access_log  logs/host.access.log  main;

    location / {
        root   /var/www/html; # 你的静态资源路径
        index  index.html index.htm;# 访问的文件为html, htm
    }
    
    location /markdown {
        alias   /var/www/html/markdown; # 你的静态资源路径
        index  index.html index.htm;# 访问的文件为html, htm
    }
    
    # 后续如果有其他配置，模仿markdown的配置添加即可
    # location /example {
    #     alias   /var/www/html/example; # 你的静态资源路径
    #     index  index.html index.htm;# 访问的文件为html, htm
    # }
}
```

**对于多个路径的配置：** [1]

- 使用**root**会将location后的markdown追加在路径的尾部，在访问时就会访问到/var/www/html/markdown/markdown

- 使用**alias**则不会将location后的markdown追加在路径尾部，访问时就为正确路径/var/www/html/markdown

**如果添加`charset utf-8;`后还存在乱码，强制刷新一下试试**

输入`IP/markdown`查看配置结果

### 3. 配置端口转发

自行寻找一个服务做测试，开在非80端口即可，我开在了8822端口

**注：要在服务器的安全组配置，打开对应端口**

首先测试一下 IP:8822 能不能正常使用，可以使用说明服务成功启动在8822端口，进行后续配置。

```nginx
server {
    listen       80;
    server_name  localhost;
 
    charset utf-8; # 防止中文显示出现乱码

	# 添加头部信息
    proxy_set_header  Cookie $http_cookie;
    proxy_set_header  X-Forwarded-Host $Host;
    proxy_set_header  proxy_set_Server  $Host;
    proxy_set_header  X-Forwarded-For $proxy_add_x_forwarded_for;
	
    # 访问IP/eat，则会自动访问对应地址IP:8822
    location /eat/ {
        proxy_pass http://localhost:8822/;
    }
    
    # 后续如果有其他配置，模仿eat的配置添加即可
    # 访问IP/example，则会自动访问对应地址IP:port
    # location /example/ {
    #     proxy_pass http://localhost:port/;
    # }
}
```

输入`IP/eat`查看配置结果

在配置proxy_pass代理转发时，如果后面的url加/，表示绝对根路径；如果没有/，表示相对路径：

**加 /**

```nginx
location /eat/ {
    proxy_pass http://localhost:8822/;
}
```

访问 `IP/eat/index.html` 会转发到  `IP/index.html` 

**不加 /**

```nginx
location /eat/ {
    proxy_pass http://localhost:8822/;
}
```

访问 `IP/eat/index.html` 会转发到  `IP/eat/index.html` 

### 4. 配置域名

我从阿里云购买了域名southyang.cn，将子域名demo.southyang.cn解析到服务器上

**以端口转发为例：**

```nginx
server {
    listen       80;
    server_name  demo.southyang.cn;
 
    charset utf-8; # 防止中文显示出现乱码

	# 添加头部信息
    proxy_set_header  Cookie $http_cookie;
    proxy_set_header  X-Forwarded-Host $Host;
    proxy_set_header  proxy_set_Server  $Host;
    proxy_set_header  X-Forwarded-For $proxy_add_x_forwarded_for;
	
    # 访问demo.southyang.cn/eat，则会自动访问对应地址IP:8822
    location /eat/ {
        proxy_pass http://localhost:8822/;
    }
    
    # 后续如果有其他配置，模仿eat的配置添加即可
    # 访问IP/example，则会自动访问对应地址IP:port
    # location /example/ {
    #     proxy_pass http://localhost:port/;
    # }
}
```

输入`demo.southyang.cn/eat`查看配置结果

### 5. 配置https 

**以端口转发为例：** [2]

```nginx
server {
    listen 80;
    server_name demo.southyang.cn;
    # 跳转https
    return 301 https://$host$request_uri;
}

server {
    listen 443   ssl http2;
    server_name  demo.southyang.cn;
 
    charset utf-8; # 防止中文显示出现乱码

	# 添加头部信息
    proxy_set_header  Cookie $http_cookie;
    proxy_set_header  X-Forwarded-Host $Host;
    proxy_set_header  proxy_set_Server  $Host;
    proxy_set_header  X-Forwarded-For $proxy_add_x_forwarded_for;
    
    # 配置证书
    ssl_certificate 证书密钥地址
    ssl_certificate_key 证书公钥地址
    ssl_verify_client off;
    proxy_ssl_verify off;
	
    # 访问demo.southyang.cn/eat，则会自动访问对应地址IP:8822
    location /eat/ {
        proxy_pass http://localhost:8822/;
        proxy_redirect off;
    }
    
    # 后续如果有其他配置，模仿eat的配置添加即可
    # 访问IP/example，则会自动访问对应地址IP:port
    # location /example/ {
    #     proxy_pass http://localhost:port/;
    # }
}
```

输入`demo.southyang.cn/eat`查看配置结果

**注：** 目前我只用到了上述所列的内容，其他内容用到了再学

> 引用内容：
>
> [1] https://blog.csdn.net/qq_39827677/article/details/113745095
>
> [2] https://github.com/Mereithhh/van-nav