ROS的topic_tools包

throttle

转播 (relay)话题, 限制最大发布频率或者带宽。使用格式: rosrun topic_tools throttle messages <intopic> <msgs_per_sec> [outtopic]

messages是当前使用的是throttle的messages模式,限制发布频率. intopic是指你想要改变频率的那个topic, msgs_per_sec是指你想要它发布的频率,而outtopic是指改变发布频率后的topic的名称,可以省略,如果省略则自动在原来topic的名字上后缀throttle

另外还有bytes模式, 用以限制带宽: rosrun topic_tools throttle bytes <intopic> <bytes_per_sec> <window> [outtopic]

例如,让雷达的带宽占用降至1KBps,则命令为:

1
rosrun topic_tools throttle bytes base_scan 1024 1.0

改变topic发布频率并不是说原来的topic就没了,或者直接在原来的topic上更改, 而是把其更改后的topic发布出来,原来的topic仍然存在

有三个参数,需要注意的是~lazy,如果它等于True的话,只有当你订阅到throttle发出来的消息,它才会工作,这显然是ros::publish函数的lazy模式了

最大的问题是 频率控制的精度低,我要求4Hz,实际却在3.6Hz左右,所以实际要设置的大一些

transform

订阅一个topic或topic field,并在应用给定的Python表达式后将传入的数据发布到另一个topic。它可以处理任何消息类型,主要用于简单的消息转换,例如计算向量或四元数的范数, 甚至将四元数转换为欧拉角。

transform <input> <output_topic> <output_type> [<expression>] [--import <module> [<module> ...]]

  • input:要订阅的传入topic(或topic field)
  • output_topic:要发布的输出topic
  • expression:转换输入消息的Python表达式,在变量m中给出。默认表达式是m,它将输入(可以是topic field)转发到output_topic
  • import :要在表达式中导入和使用的Python模块的列表。默认导入numpy模块
1
2
3
4
# 计算IMU给出的方向四元数的范数
rosrun topic_tools transform /imu/orientation /norm std_msgs/Float64 'numpy.linalg.norm([m.x, m.y, m.z, m.w])'
# 将方向四元数转换为Euler角度
rosrun topic_tools transform /imu/orientation /euler geometry_msgs/Vector3 'tf.transformations.euler_from_quaternion([m.x, m.y, m.z, m.w])' --import tf


  • mux: multiplex between multiple topics

  • relay: republish data on one topic to another.

  • relay_field: allow to republish data in a different message type

  • drop: relay a topic, dropping X out of every Y message.

mux

topic_tools-mux
可以用于多地图实时切换,参考MUX的使用

参考:throttle Wiki


标定D435i(二) 相机

Kalibr可以解决以下的标定问题:

  • 多相机标定: 一个相机系统的内外参标定,这几个相机没有全局性重叠的视角
  • 视觉惯性标定(camera-IMU): IMU关于相机系统的时空间标定
  • Rolling Shutter Camera calibration: full intrinsic calibration (projection, distortion and shutter parameters) of rolling shutter cameras

可以下载Kalibr源码编译生成可执行文件,也可以下载其CDE精简版包。这中间有个坑就是CDE精简包是没有办法标定彩色图片的,而D435输出的是彩色图。所以还是按编译源码的方式

使用Kalibr标定相机的内参和多个相机相对位置关系即外参

安装Kalibr

  1. 安装依赖项

    1
    sudo apt-get install python-pyx python-setuptools python-rosinstall ipython libeigen3-dev libboost-all-dev doxygen ros-kinetic-vision-opencv ros-kinetic-image-transport-plugins ros-kinetic-cmake-modules python-software-properties software-properties-common libpoco-dev python-matplotlib python-scipy python-git python-pip ipython libtbb-dev libblas-dev liblapack-dev python-catkin-tools libv4l-dev
  2. 源码放入工作空间进行编译,会花很长时间,所以编译命令要这样:

    1
    2
    # 视情况取j8
    catkin_make -DCMAKE_BUILD_TYPE=Release -j4

编译kalibr可能会出现 fatal error: numpy/arrayobject.h: No such file or directory ,解决方法: sudo apt-get install --reinstall python-numpy

可能出现catkin_make时,下载suitesparse过久甚至失败的问题。解决方法: 修改~/catkin_ws/src/kalibr/suitesparse中的CMakeLists.txt为新CMakeLists.txt, 然后重新catkin_make

标定板

下载标定板

我下载的是Aprilgrid 6x6 0.5x0.5m(unscaled), 打印在A3纸上

原版的参数是:6X6 tags,6乘6个格子,一个大格子size=5.5cm,一个小格子spacing=1.65cm

A3纸上的缩放:6X6 tags,一个大格子size=3.5cm,一个小格子spacing=1cm。记得打印出来用尺子量一下,以免出现差错。
标定板参数示意图

下载官网提供的yaml格式文件,需要按照设定的尺寸进行修改

1
2
3
4
5
target_type: 'aprilgrid' #gridtype
tagCols: 6 #number of apriltags
tagRows: 6 #number of apriltags
tagSize: 0.035 #size of apriltag, edge to edge [m]
tagSpacing: 0.3 #ratio of space between tags to tagSize

找一个适合的能拍到棋盘格的距离,启动相机: roslaunch realsense2_camera rs_camera.launch

d453i是有红外发射器的,可以发射很多红外小斑点,如果打开你会在rviz看到很多光斑,可能不利于标定,所以标定时关闭这个发射器的。

降低图像话题的频率,录制图像数据包

kalibr在处理标定数据的时候要求图像的频率不可过高,一般为4hz(后面计算过程报错,改为20)。使用如下指令来限制图像频率:

1
2
3
rosrun topic_tools throttle messages /camera/color/image_raw 4 /color
rosrun topic_tools throttle messages /camera/infra2/image_rect_raw 4 /infra_left
rosrun topic_tools throttle messages /camera/infra1/image_rect_raw 4 /infra_right

用topic_tools throttle限制频率后,一定要查看限制后的topic输出频率:rostopic hz /topic,你会发现实际的频率与设定的频率并不一致,比如:rosrun topic_tools throttle messages /topic_1 25 /topic_2,如果topic_1是40hz,/topic_2可能不是25hz,而是20hz,而且每次的实际频率可能不同,具体原因不明。

注意这里是采用了新的话题/color去发布,所以下面录制要写/color话题

将标定目标AprilGrid置于相机前方合理距离范围内,准备录制两分钟:

1
rosbag record -O multicameras_calibration /infra_left /infra_right /color

开始缓慢移动标定板,让所有摄像头看到标定板不要太远,不然无法检测到标定目标的特征,这个过程中看不到图案的识别结果,这是kalibr的原因。在标定算法中需要检测是否有足够数量图片检测到标定特征,否则直接无法标定。移动标定物时候不要过快导致运动模糊,我们只需要获取不同位置和角度的图像,确保图像清晰和特征完整即可。另外要尽可能多角度和多位置(上下左右等)甚至到摄像头捕捉图像的边缘,这样移动目标1min左右即可。

移动的方式可以参考TUM CALIBRATION SEQUENCES的标定方式,点play即可播放

kalibr算法计算各个摄像头的内参和外参

april_6x6_A3.yaml: 标定物的参数,具体是标定目标的尺寸之类,因为我是缩小打印在A3上,所以要对参数进行修改;pinhole-equi – 选择的相机模型,kalibr提供了很多相机模型,可以自己选择; —bag-from-to 可以选择时间段,毕竟录制的时候不能保证整体都录制的很好。标定会花很长时间,最后会输出一个pdf和txt文件,有内外参数据。

只标定主相机:

1
kalibr_calibrate_cameras --target ../yaml/april_6x6_A4.yaml --bag ./bag/0_multicameras_calibration.bag --model pinhole-equi  --topic  /color  --show-extraction --approx-sync 0.04

最后还是标定的多相机:

1
kalibr_calibrate_cameras --target april_6x6_A3.yaml --bag multicameras_calibration.bag --models pinhole-equi pinhole-equi pinhole-equi --topics /infra_left /infra_right /color  --show-extraction --approx-sync 0.04 --bag-from-to 10 100

  • pinhole-radtan指的是针孔相机模型和畸变模型,每个相机都要指定。还有Pinhole + FOV等等
  • --bag-from-to 10 100指的是录制的第26秒到100秒这段时间
  • --show-extraction, 在标定过程中可视化角点检测情况是否良好
  • --approx-sync 0.04

结果报错: ImportError: No module named igraph
解决方法: sudo apt-get install python2.7-igraph

需要在有界面的情况下标定,因为会弹出几个窗口,所以不能通过SSH进行,类似这样:

可以使用calibration validator进行标定的验证,原理是对重投影误差进行量化分析,同样需要有界面:
kalibr_camera_validator --cam camchain-multicameras_calibration.yaml --target april_6x6_A3.yaml
验证结果.png


标定D435i(一) IMU

realsense d435i包含两个红外相机、红外发射器、RGB相机和IMU四个模块,显然四个传感器的空间位置是不同的,我们在处理图像和IMU数据时需要将这些数据都放在统一的坐标系上去。比如我们用d435i运行vins,处理的图像和IMU数据都需要放在同一个坐标系下,因此需要标定IMU相对RGB相机的空间位置(包括旋转和位移)。

另外,相机固有参数比如焦距、畸变参数等以及IMU的零偏和scale系数等都需要提前知道。前者称为外参,后者称为内参,在运行程序前我们需要标定它们,不论程序是否有自标定功能,毕竟好的初始标定值对于自标定来说也是有利的。

标定顺序:IMU标定 —> 相机标定 —> IMU+相机联合标定. 这么设定顺序是因为最后一步的IMU和相机的联合标定需要 IMU和相机的内参

Allan方差

在IMU采集数据时,会产生两种误差:确定性误差和随机性误差,为获得精确的数据,需要对上述两种误差进行标定,加速度计和陀螺仪随机误差的标定通常使用Allan方差法,它是20世纪60年代由美国国家标准局的David Allan提出的基于时域的分析方法。

A ROS package tool to analyze the IMU performance. C++ version of Allan Variance Tool. The figures are drawn by Matlab, in scripts.

Actually, just analyze the Allan Variance for the IMU data. Collect the data while the IMU is Stationary, with a two hours duration.
code_utils标定IMU的噪音密度和随机游走系数。

安装库和依赖项

安装依赖项,不装之后的编译会报错: sudo apt-get -y install libdw-dev,结果可能提示

1
2
3
4
The following packages have unmet dependencies:
libdw-dev : Depends: libelf-dev but it is not going to be installed
Depends: libdw1 (= 0.165-3ubuntu1) but it is not going to be installed
E: Unable to correct problems, you have held broken packages.

这是因为一个依赖项已经安装了不同版本:Depends: libelf1 (= 0.165-3ubuntu1) but 0.165-3ubuntu1.2 is to be installed。 解决方法: sudo aptitude install libdw-dev,对给出的方案,选择第二个,降级 libelf1[0.165-3ubuntu1.1 (now) -> 0.158-0ubuntu]

编译code_utils和imu_utils

全局安装ceres库,因为code_imu依赖ceres。不要同时把imu_utils和code_utils一起放到src下进行编译。因为imu_utils 依赖 code_utils,原作者的CMakeLists写的不好,所以先编译code_utils再编译后者。

code_utils下面找到sumpixel_test.cpp,修改#include "backward.hpp"#include"code_utils/backward.hpp",再依次编译两个包

发布D435i的IMU数据

可以直接在rs_camera.launch基础上针对IMU校准做修改。目的是将acc、gyro数据对齐使用同一个topic发布。

1
2
3
4
<!-- 更改前原版本arg name="unite_imu_method"          default=""/-->  
<arg name="unite_imu_method" default="linear_interpolation"/>
<!--或着将参数改为copy-->
<arg name="unite_imu_method" default="copy"/>

启动: roslaunch realsense2_camera rs_imu_calibration.launch,然后录制imu数据包rosbag record -O imu_calibration /camera/imu,让IMU静止不动两个小时,录制IMU的bag.

标定

根据imu_utils文件夹里面的A3.launch改写D435i标定启动文件:d435i_imu_calib.launch注意,记得修改max_time_min对应的参数,默认是120,也就是两个小时,如果ros包里的imu数据长度没有两个小时,等bag播放完了,还是停留在wait for imu data这里,不会生成标定文件。我录了1小时59分多一点,所以还得改成119

d435i_imu_calibration.launch如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<launch>
<node pkg="imu_utils" type="imu_an" name="imu_an" output="screen">
<!--TOPIC名称和上面一致-->
<param name="imu_topic" type="string" value= "/camera/imu"/>
<!--imu_name 无所谓-->
<param name="imu_name" type="string" value= "D435i"/>
<!--标定结果存放路径-->
<param name="data_save_path" type="string" value= "$(find imu_utils)/data/"/>
<!--数据录制时间-min-->
<param name="max_time_min" type="int" value= "120"/>
<!--采样频率,即是IMU频率,采样频率可以使用rostopic hz /camera/imu查看,设置为200,也就是rosbag play播放频率-->
<param name="max_cluster" type="int" value= "200"/>
</node>
</launch>

先启动标定程序: roslaunch imu_utils d435i_imu_calib.launch,再播放bag: rosbag play -r 200 imu_calibration.bag

标定结果

标定结果是D435i_imu_param.yaml:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
%YAML:1.0
---
type: IMU
name: D435i
Gyr:
unit: " rad/s"
avg-axis:
gyr_n: 3.6673681012835031e-03
gyr_w: 7.0017785520472972e-05
x-axis:
gyr_n: 3.6001489799186333e-03
gyr_w: 6.2846247607788020e-05
y-axis:
gyr_n: 4.7157261366663813e-03
gyr_w: 7.5207268006344615e-05
z-axis:
gyr_n: 2.6862291872654953e-03
gyr_w: 7.1999840947286307e-05
Acc:
unit: " m/s^2"
avg-axis:
acc_n: 2.7436489578044256e-02
acc_w: 1.0915021608117670e-03
x-axis:
acc_n: 1.8271976632141730e-02
acc_w: 5.5394830052109354e-04
y-axis:
acc_n: 2.8924134998445018e-02
acc_w: 1.5674764920646303e-03
z-axis:
acc_n: 3.5113357103546017e-02
acc_w: 1.1530816898495772e-03

我们一会只用到Gyr中的avg-axisgyr_ngyr_w, Acc中的avg-axisacc_nacc_w

终端输出结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
gyr x  numData 781205
gyr x start_t 1.59343e+09
gyr x end_t 1.59344e+09
gyr x dt
-------------7140.59 s
-------------119.01 min
-------------1.9835 h
gyr x freq 109.403
gyr x period 0.00914049
gyr y numData 781205
gyr y start_t 1.59343e+09
gyr y end_t 1.59344e+09
gyr y dt
-------------7140.59 s
-------------119.01 min
-------------1.9835 h
gyr y freq 109.403
gyr y period 0.00914049
gyr z numData 781205
gyr z start_t 1.59343e+09
gyr z end_t 1.59344e+09
gyr z dt
-------------7140.59 s
-------------119.01 min
-------------1.9835 h
gyr z freq 109.403
gyr z period 0.00914049
Gyro X
C -6.83161 94.2973 -19.0588 2.983 -0.0404918
Bias Instability 2.37767e-05 rad/s
Bias Instability 6.28462e-05 rad/s, at 63.1334 s
White Noise 12.9453 rad/s
White Noise 0.00360015 rad/s
bias -0.363298 degree/s
-------------------
Gyro y
C -8.74367 117.584 -15.9277 2.47408 -0.0373467
Bias Instability 6.41864e-05 rad/s
Bias Instability 7.52073e-05 rad/s, at 104.256 s
White Noise 16.8998 rad/s
White Noise 0.00471573 rad/s
bias -0.544767 degree/s
-------------------
Gyro z
C -4.51808 68.1919 -9.33284 1.95333 -0.0262641
Bias Instability 8.50869e-05 rad/s
Bias Instability 7.19998e-05 rad/s, at 63.1334 s
White Noise 9.43212 rad/s
White Noise 0.00268623 rad/s
bias -0.0762471 degree/s
-------------------
==============================================
==============================================
acc x numData 781205
acc x start_t 1.59343e+09
acc x end_t 1.59344e+09
acc x dt
-------------7140.59 s
-------------119.01 min
-------------1.9835 h
acc x freq 109.403
acc x period 0.00914049
acc y numData 781205
acc y start_t 1.59343e+09
acc y end_t 1.59344e+09
acc y dt
-------------7140.59 s
-------------119.01 min
-------------1.9835 h
acc y freq 109.403
acc y period 0.00914049
acc z numData 781205
acc z start_t 1.59343e+09
acc z end_t 1.59344e+09
acc z dt
-------------7140.59 s
-------------119.01 min
-------------1.9835 h
acc z freq 109.403
acc z period 0.00914049
acc X
C 3.36177e-05 0.00175435 -0.000159698 7.23303e-05 -7.16006e-07
Bias Instability 0.000553948 m/s^2
White Noise 0.018272 m/s^2
-------------------
acc y
C 9.36955e-05 0.00234733 0.00012197 0.000243676 -2.66252e-06
Bias Instability 0.00156748 m/s^2
White Noise 0.0289241 m/s^2
-------------------
acc z
C 5.07832e-05 0.00331104 -0.000381222 0.000199602 -2.43776e-06
Bias Instability 0.00115308 m/s^2
White Noise 0.0351134 m/s^2

经过这些标定会生成一个yaml文件和很多txt文件,主要是yaml文件,给出了加速度计和陀螺仪三轴的noise_densityrandom_walk,同时计算出了平均值,后面IMU+摄像头联合标定的时候需要这些均值。

标定外参的准备

将Acc和Gyr的第一组平均数据拷贝到kalibr对应的imu.yaml文件中

1
2
3
4
5
6
7
rostopic: /camera/imu
update_rate: 200.0 #Hz

accelerometer_noise_density: 2.89e-01 #continous
accelerometer_random_walk: 4.55e-04
gyroscope_noise_density: 3.02e-03 #continous
gyroscope_random_walk: 2.29e-05

分别是加速度计和陀螺仪的高斯白噪声和随机游走的平均值,是IMU噪声模型中的两种噪声。

 查看默认imu与相机参数

D435i相关的imu_info话题如下:
imu_info列表

/camera/gyro/imu_info和/camera/accel/imu_info没有结果

realsense_camera/IMUInfo with the header.frame_id set to either imu_accel or imu_gyro to distinguish between accel and gyro info. 消息成员如下:

1
2
3
4
string frame_id
float64[12] data
float64[3] noise_variances
float64[3] bias_variances

rostopic echo -n1 /camera/color/camera_info得到结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
  frame_id: "camera_color_optical_frame"
height: 480
width: 640
distortion_model: "plumb_bob"
D: [0.0, 0.0, 0.0, 0.0, 0.0]
K: [611.3538208007812, 0.0, 327.437744140625, 0.0, 610.015869140625, 239.99667358398438, 0.0, 0.0, 1.0]
R: [1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0]
P: [611.3538208007812, 0.0, 327.437744140625, 0.0, 0.0, 610.015869140625, 239.99667358398438, 0.0, 0.0, 0.0, 1.0, 0.0]
binning_x: 0
binning_y: 0
roi:
x_offset: 0
y_offset: 0
height: 0
width: 0
do_rectify: False

对于/camera/depth/imu_info,结果是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
frame_id: "camera_depth_optical_frame"
height: 480
width: 640
distortion_model: "plumb_bob"
D: [0.0, 0.0, 0.0, 0.0, 0.0]
K: [380.23321533203125, 0.0, 316.4999084472656, 0.0, 380.23321533203125, 237.40985107421875, 0.0, 0.0, 1.0]
R: [1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0]
P: [380.23321533203125, 0.0, 316.4999084472656, 0.0, 0.0, 380.23321533203125, 237.40985107421875, 0.0, 0.0, 0.0, 1.0, 0.0]
binning_x: 0
binning_y: 0
roi:
x_offset: 0
y_offset: 0
height: 0
width: 0
do_rectify: False

话题/camera/infra2/camera_info/camera/infra2/camera_info的结果完全一样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
frame_id: "camera_infra1_optical_frame"
height: 480
width: 640
distortion_model: "plumb_bob"
D: [0.0, 0.0, 0.0, 0.0, 0.0]
K: [380.23321533203125, 0.0, 316.4999084472656, 0.0, 380.23321533203125, 237.40985107421875, 0.0, 0.0, 1.0]
R: [1.0, 0.0, 0.0, 0.0, 1.0, 0.0, 0.0, 0.0, 1.0]
P: [380.23321533203125, 0.0, 316.4999084472656, 0.0, 0.0, 380.23321533203125, 237.40985107421875, 0.0, 0.0, 0.0, 1.0, 0.0]
binning_x: 0
binning_y: 0
roi:
x_offset: 0
y_offset: 0
height: 0
width: 0
do_rectify: False

可以看出,实际上出厂没有标定IMU

绘制Allan曲线

imu_utils/scripts中是Matlab写的.m文件,按照draw_allan.m创建文件draw_allan_acc.mdraw_allan_gyr.m

由于Ubuntu下安装Matlab比较麻烦,因此将数据和.m文件都拷贝到Windows系统下绘制,注意文件路径和m文件中要对应,尤其matlab中的当前路径指的是左侧栏的路径,而不是m文件所在的路径

allan_gyr.jpg
allan_acc.jpg

参考:
RealSense D435i Calibration
官方Github
VIO标定IMU随机误差——Allan方差法


realsense D435i安装配置


realsense D435i终于到手了,打开发现其实很小巧,先做一些配置看看。默认要使用USB3,如果RealSense使用USB2, Output Resolution自动降到480*270 30fbs,而非产品所宣称的1280 x 720 active stereo depth resolution和90fps,且只有Stereo Moudle在工作,无Image Sensor的RGB Moudle菜单项,无法进行3D建模。

D435i采用了即用型USB供电形式,不仅提供深度传感器模组,还配备了一个IMU单元(惯性测量单元,采用的博世BMI055)。凭借内置的IMU单元,结合视觉数据可实现6DoF追踪功能。其中,IMU将各种线性加速度计和陀螺仪数据结合,可检测X,Y,Z三轴的旋转和平移,以及俯仰、横摇等动作。D435i的2000万像素RGB摄像头和3D传感器可以30帧/秒的速度提供分辨率高达1280 × 720,或者以90帧/秒的速度提供848 × 480的较低分辨率。该摄像头具有全局快门,可以处理快速移动物体,室内室外皆可操作。深度距离在0.1 m~10 m之间,视场角度为85 × 58度

可以获得RGB图、左右红外摄像图、深度图、IMU数据,并且将深度图数据和RGB图进行对齐。左右红外相机进行测量深度,中间红外点阵投射器相当于补光灯,不打开也能测深度,只是效果不好;最右边的rgb相机用于采集彩色图片,最终可以将彩色视频流与深度流进行对齐.

两个驱动讲究搭配,否则安装编译都不报错,运行时会报错 realsense hwmon command 0x7d failed 我使用的是realsense-ros-2.2.23librealsense-2.43.0

安装librealsense

先装realsense的驱动,步骤参考网上的,其实不必完全相同,我的步骤如下:

  1. 下载驱动,然后解压到根目录
  2. 执行如下命令:
    1
    2
    3
    4
    5
    cd ~/librealsense
    sudo apt-get install libssl-dev libusb-1.0-0-dev pkg-config libgtk-3-dev libglfw3-dev
    # 许可脚本
    sudo cp config/99-realsense-libusb.rules /etc/udev/rules.d/
    sudo udevadm control --reload-rules && udevadm trigger
  3. 开始编译
    1
    2
    3
    4
    5
    cd ~/librealsense
    mkdir build && cd build
    cmake ../ -DBUILD_EXAMPLES=true

    sudo make uninstall && make clean && make -j7 && sudo make install

运行realsense-viewer验证,看到如下画面
RGB Depth Infrared
配置可以修改为常见的黑白深度图以及分辨率等等
配置栏

ROS驱动

这里下载,然后放到某工作空间,编译即可:

1
2
catkin_make -DCATKIN_ENABLE_TESTING=False -DCMAKE_BUILD_TYPE=Release
catkin_make install

现在运行roslaunch realsense2_camera rs_camera.launch,打开rqt就能看到realsense的三种图像
实际运行了/camera/realsense2_cameracamera/realsense2_camera_manager两个节点,涉及的话题有很多,以后慢慢分析。

tf关系如图:
frames.png

在rqt中打开深度图时出现了报错,又是图像编码问题
launch文件中报错.png
rqt终端报错.png
在rqt里查看/camera/depth/image_rect_raw/theora,同样没有深度图,但rqt不报警

在rqt查看RGB和红外的图像,只要选择theora,rqt终端都会报警:

1
[ WARN][/rqt_gui_cpp_node_25764] [TheoraSubscriber::internalCallback] line_170  [theora] Packet was not a Theora header


使用对齐的深度话题信息发布RGBD点云

1
roslaunch realsense2_camera rs_rgbd.launch

这一步还没有成功,在rviz里没看到结果

内参

realsense启动时可以发现信息 [color stream is enabled - width: 640, height: 480, fps: 15, Format: RGB8]

realsense相机出厂的时候一般都标定好了,直接读取他们的内参即可。终端输入: rs-sensor-control,根据提示选择,出现所有视频流的列表时,根据上面的信息选择,最终显示内参:

1
2
3
4
Principal Point         : 327.438, 239.997
Focal Length : 611.354, 610.016
Distortion Model : Inverse Brown Conrady
Distortion Coefficients : [0,0,0,0,0]

疑难问题 undefined symbol: _ZN2cv3MatC1Ev

运行rs_camera.launch时报错

1
symbol lookup error: /home/jetson/catkin_ws/devel/lib//librealsense2_camera.so: undefined symbol: _ZN2cv3MatC1Ev   [camera/realsense2_camera_manager-2] process has died 

我查了好长时间,期间还改用其他的librealsense和firmware的版本,比如到firmware版本历史,下载对应版本。 参考firmware-update-tool的Usage部分

运行时可以看到相关的环境版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
RealSense ROS v2.3.2
[ INFO] [1723892537.013079361]: Built with LibRealSense v2.50.0
[ INFO] [1723892537.013109698]: Running with LibRealSense v2.50.0
[ INFO] [1723892537.311113159]: Device with serial number 014122072296 was found.
[ INFO] [1723892537.311624883]: Device with physical ID 2-1.4-6 was found.
[ INFO] [1723892537.311852281]: Device with name Intel RealSense D435I was found.
[ INFO] [1723892537.313360062]: Device with port number 2-1.4 was found.
[ INFO] [1723892537.313859786]: Device USB type: 3.2

[ INFO] [1723892537.373681930]: JSON file is not provided
[ INFO] [1723892537.373700779]: ROS Node Namespace: camera
[ INFO] [1723892537.373737260]: Device Name: Intel RealSense D435I
[ INFO] [1723892537.373757100]: Device Serial No: 014122072296
[ INFO] [1723892537.373777005]: Device physical port: 2-1.4-6
[ INFO] [1723892537.373792685]: Device FW version: 05.13.00.50

后来又参考如何修改CMakeLists

最后发现其实存在两个librealsense2_camera.so

1
2
/home/jetson/catkin_ws/devel/lib/librealsense2_camera.so
/opt/ros/noetic/lib/librealsense2_camera.so

只需要运行ROS自带的就可以了: roslaunch /opt/ros/noetic/share/realsense2_camera/launch/rs_camera.launch

参考:
realsense D435 驱动安装并嵌入ROS中使用


点云滤波

地图分很多种:稀疏的,稠密的,还有半稀疏的。稀疏的地图放大了看就是一个个离散的空间点,不过我们可以把它变成连续的稠密的网格,这个过程也叫点云的网格化。点云网格化需要对点云进行一系列处理

一般下面这几种情况需要进行点云滤波处理:

  1. 点云数据密度不规则需要平滑

  2. 因为遮挡等问题造成离群点需要去除

  3. 大量数据需要降采样

  4. 噪声数据需要去除

滤波程序

package.xml中要添加:

1
2
<build_depend>libpcl-all-dev</build_depend>
<exec_depend>libpcl-all</exec_depend>

CMake按照第一篇里进行配置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <ros/ros.h>
#include <sensor_msgs/PointCloud2.h>
#include <pcl_conversions/pcl_conversions.h>
#include <pcl/point_cloud.h>
#include <pcl/point_types.h>
//滤波的头文件
#include <pcl/filters/voxel_grid.h>

ros::Publisher pub;

void cloud_cb (const sensor_msgs::PointCloud2ConstPtr& cloud_msg)
{
// 声明存储原始数据与滤波后的数据的点云的格式
pcl::PCLPointCloud2* cloud = new pcl::PCLPointCloud2; //原始的点云的数据格式
pcl::PCLPointCloud2ConstPtr cloudPtr(cloud);

// ROS消息转化为PCL中的点云数据格式
pcl_conversions::toPCL(*cloud_msg, *cloud);

pcl::PCLPointCloud2 cloud_filtered; //存储滤波后的数据格式
// 进行一个滤波处理
pcl::VoxelGrid<pcl::PCLPointCloud2> sor; //创建滤波对象
sor.setInputCloud (cloudPtr); //设置输入的滤波,将需要过滤的点云给滤波对象
sor.setLeafSize (0.1, 0.1, 0.1); //设置滤波时创建的体素大小为1cm立方体
sor.filter (cloud_filtered);//执行滤波处理,存储输出cloud_filtered

// 再将滤波后的点云的数据格式转换为ROS下的数据格式发布
sensor_msgs::PointCloud2 output;
pcl_conversions::moveFromPCL(cloud_filtered, output);//第一个参数是输入,后面的是输出
pub.publish (output);
}

int main (int argc, char** argv)
{
ros::init (argc, argv, "filter_cloud");//声明节点的名称
ros::NodeHandle nh;

ros::Subscriber sub = nh.subscribe<sensor_msgs::PointCloud2> ("/camera/depth/points", 1, cloud_cb);
pub = nh.advertise<sensor_msgs::PointCloud2> ("filtered_cloud", 1);

ros::spin ();
}

点云合并

把相邻的点合并成一个点,一方面可以减少图像的数据量,另一方面可以增加点云的稳定度。个人感觉贴近滤波
点云合并

直通滤波

多线雷达点云大部分的点都集中的中间区域,距离越远点云越稀疏,信息量也越小,应该筛选掉一些较远的点。这就用到了直通滤波,它是最为简单、粗暴的一种滤波方式,就是直接对点云的X、Y、Z轴的点云坐标约束来进行滤波。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <pcl/io/pcd_io.h>
#include <pcl/point_types.h>
#include <pcl/filters/passthrough.h>

int main(int argc, char** argv)
{

pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);

// Fill in the cloud data
pcl::PCDReader reader;
reader.read("16line.pcd", *cloud);

std::cerr << "Cloud before filtering: " << cloud->points.size() << std::endl;

pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_filtered2(new pcl::PointCloud<pcl::PointXYZ>);
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_filtered3(new pcl::PointCloud<pcl::PointXYZ>);

// Create the filtering object 直通滤波
pcl::PassThrough<pcl::PointXYZ> pass;
pass.setInputCloud(cloud);
pass.setFilterFieldName("x"); // 设置操作的坐标轴
pass.setFilterLimits(-5.0, 5.0);
pass.filter(*cloud_filtered2);
// filter range Y-axis
// 注意多次滤波需要再次输入点云和调用filter函数
pass.setInputCloud(cloud_filtered2);
pass.setFilterFieldName("y");
pass.setFilterLimits(-5.0, 5.0);
pass.filter(*cloud_filtered3);

std::cerr << "Cloud after filtering: " << cloud_filtered3->points.size() << std::endl;

// 读取pcd点云数据进行操作,最后保存为pcd文件
pcl::PCDWriter writer;
writer.write("16line_filtered.pcd", *cloud_filtered3, false);

return 0;
}

pass.setFilterLimitsNegative(true);: 是否保存滤波的限制范围内的点云,默认为false,保存限制范围点云,true时候是相反。

条件滤波法

在某些情况下,我们也会需要去除给定区域内部的点,比如激光雷达扫描近处的点(可能就是装载雷达的车),这些点通常对建图和感知不会有作用。

设定滤波条件进行滤波,点在范围内保留,不在范围内丢弃。

getFilterLimitsNegative 可以对选定范围取反,将其设为 true 时可以进行给定只保留给定范围内的点的功能。

体素滤波

实现降采样,既减少点云的数量,并同时保持点云的形状特征。创建一个三维体素,用体素内所有点的重心近似表示体素中的其他点,这样体素内所有点就用一个重心点最终表示。

使用小程序进行体素滤波,输入input.pcd,输出output.pcd

1
pcl_voxel_grid input.pcd output.pcd -leaf 0.03,0.03,0.03

对于体素下采样接口功能函数pcl提供了两种方式 pcl::ApproximateVoxelGridpcl::VoxelGrid。两种区别主要在于第一种是用每个体素栅格的中心点来近似该体素内的点,提升了速度,但是也损失了原始点云的局部形态精细度。 ApproximateVoxelGrid是依据每一个体素的中心点来获取点云的,并不是依赖每个体素里面是否存在点云。所以会导致两种方式的处理结果又偏差,VoxelGrid的方式更加精确但是耗时相对于ApproximateVoxelGrid更高。

半径滤波

对整个输入迭代一次,对于每个点进行半径R的邻域搜索(球体),如果邻域点的个数低于某一阈值,则该点将被视为噪声点并被移除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);      //待滤波点云
if (pcl::io::loadPCDFile("test.pcd", *cloud) < 0)
{
PCL_ERROR("\a点云文件不存在!\n");
system("pause");
return -1;
}

pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_filtered(new pcl::PointCloud<pcl::PointXYZ>); //滤波后点云
pcl::RadiusOutlierRemoval<pcl::PointXYZ> ror; //创建滤波器对象
ror.setInputCloud(cloud); //设置待滤波点云
ror.setRadiusSearch(0.02); //设置查询点的半径邻域范围
ror.setMinNeighborsInRadius(5); //设置判断是否为离群点的阈值,即半径内至少包括的点数
//ror.setNegative(true); //默认false,保存内点;true,保存滤掉的外点
ror.filter(*cloud_filtered); //执行滤波,保存滤波结果于cloud_filtered

实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void radiusremoval(pcl::PointCloud<pcl::PointXYZ>::Ptr& cloud, pcl::PointCloud<pcl::PointXYZ>::Ptr& cloud_filtered, double radius, int min_pts)
{
pcl::KdTreeFLANN<pcl::PointXYZ> tree;
tree.setInputCloud(cloud);
vector<float> avg;
for (int i = 0; i < cloud->points.size(); ++i)
{
vector<int> id(min_pts);
vector<float> dist(min_pts);
tree.nearestKSearch(cloud->points[i], min_pts, id, dist);
// 是否是平方
if (dist[dist.size() - 1] < radius)
{
cloud_filtered->push_back(cloud->points[i]);
}
}
}

构建一个 KD 树,对每个点进行范围搜索(最近邻搜索 nearestKSearch),最后判断邻近点数(最大距离)是否满足要求即可。

统计滤波


看过源码后得知, 计算均值 时除以的是点云的点数,不是邻域的点数。 对滤波结果有影响的是标准差阈值系数k和邻域的点数。 使用的也是 nearestKSearch

缺点:对较远的激光线也筛除掉了。首先对激光雷达点云数据中的每个点而言,由于每个激光线束本身扫描频率是一致的, 显然越远的扫描线点会越稀疏,因此其平均距离会越远(即便其本身可能不一定是噪点)。因此更合理的方法可能是对每个点周围小范围内(同一条线内)的点进行高斯拟合,然后判断该点是否满足该高斯分布,但是如果需要得到比较准确的高斯分布参数,点数需要达到一定数量,否则和上述基于点云密度进行去噪差别不大。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <pcl/io/pcd_io.h>  //文件输入输出
#include <pcl/point_types.h> //点类型相关定义
#include <pcl/visualization/cloud_viewer.h> //点云可视化相关定义
#include <pcl/filters/statistical_outlier_removal.h> //滤波相关
#include <pcl/common/common.h>

// 1.读取点云
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud(new pcl::PointCloud<pcl::PointXYZ>);
pcl::PCDReader r;
r.read<pcl::PointXYZ>("table_scene_lms400.pcd", *cloud);
cout << "there are " << cloud->points.size() << " points before filtering." << endl;

// 2.统计滤波
pcl::PointCloud<pcl::PointXYZ>::Ptr cloud_filter(new pcl::PointCloud<pcl::PointXYZ>);
pcl::StatisticalOutlierRemoval<pcl::PointXYZ> sor;
sor.setInputCloud(cloud);
sor.setMeanK(50); // K近邻搜索点个数
sor.setStddevMulThresh(1.0); // 标准差倍数
sor.setNegative(false); // 保留未滤波点(内点)
sor.filter(*cloud_filter); // 保存滤波结果到cloud_filter

// 3.滤波结果保存
pcl::PCDWriter w;
w.writeASCII<pcl::PointXYZ>("table_scene_lms400_filter.pcd", *cloud_filter);
cout << "there are " << cloud_filter->points.size() << " points after filtering." << endl;

system("pause");
return 0;

常用滤波顺序: 直通 —-> 体素 —-> 统计

参考:统计滤波的源码


静态层

静态层加载过程.png

静态层所用的参数:static map params


tf MessageFilter

tf::MessageFilter可以订阅任何的ROS消息,然后将其缓存,直到这些消息可以转换到目标坐标系,然后进行相应的处理(进入回调函数)

tf::MessageFilter的初始化需要message_filters::Subscriber,tf转换,目标坐标系,等待时间。当message_filters::Subscriber的消息能够由tf转换到目标坐标系时,调用回调函数,回调函数由tf::MessageFilter::registerCallback()进行注册。

步骤:

  1. 定义数据:TransformListener、message_filters::Subscriber、tf::MessageFilter
  2. 用话题的名称来初始化message_filters::Subscriber
  3. tf message_filters::Subscriber 目标坐标系来初始化tf::MessageFilter
  4. 给tf::MessageFilter注册callback
    ,编写callback,并在回调中完成坐标转换,至此完成消息订阅+坐标转换

全局路径规划(一) global_planner

概述

ROS 的navigation官方功能包提供了三种全局路径规划器:carrot_planner、global_planner、navfn,默认使用的是navfn。
继承关系 1.png

  • carrot_planner检查需要到达的目标是不是一个障碍物,如果是一个障碍物,它就将目标点替换成一个附近可接近的点。因此,这个模块其实并没有做任何全局规划的工作。在复杂的室内环境中,这个模块并不实用。

  • navfn使用Dijkstra算法找到最短路径。

  • global planner是navfn的升级版。它支持A*算法; 可以切换二次近似; 切换网格路径;

目前常用的是global_planner,需要先设定move_base的参数: base_global_planner: "global_planner/GlobalPlanner"global_planner根据给定的目标位置进行总体路径的规划,只处理全局代价地图中的数据。提供快速的、内插值的全局规划,目前已经取代navfn。遵循navcore::navcore 包中指定的BaseGlobalPlanner接口。它接受costmap生成的全局代价地图规划出从起始点到目标点的路径,为local_planner规划路径作出参考。

global_planner没有提供类似D*这样的动态方法,而是用了定时规划路径,ROS是启动了一个线程,在移动过程中对路径不断的重新规划。这个feature是可以去掉的,特别是当你的运算负载很高,处理器又有限的情况下。还有重新规划(当找不到路径,也就是走着走着新扫描到未知区域的障碍或者动态增加的障碍)两种办法。加上了定时规划和重新规划之后的A*D*几乎是一模一样的。

配置

move_base是通过plugin调用全局规划器的,文件bgp_plugin.xml

1
2
3
4
5
6
7
<library path="lib/libglobal_planner">
<class name="global_planner/GlobalPlanner" type="global_planner::GlobalPlanner" base_class_type="nav_core::BaseGlobalPlanner">
<description>
A implementation of a grid based planner using Dijkstras or A*
</description>
</class>
</library>

package.xml的配置中,加入如下行:
1
2
3
<export>
<nav_core plugin="${prefix}/bgp_plugin.xml" />
</export>

参数

  • allow_unknown: true    是否允许规划器规划在未知区域创建规划,只设置该参数为true还不行,还要在costmap_commons_params.yaml中设置 track_unknown_space 参数也为true才行,

  • default_tolerance: 0.0    当设置的目的地被障碍物占据时,需要以该参数为半径寻找到最近的点作为新目的地点.

  • visualize_potential: false    是否显示从PointCloud2计算得到的势区域. 这个参数可以让你看见potential array的图像,看计算出的cost是怎么样子(颜色深浅代表距离起始点的远近)

  • use_dijkstra: true    设置为true,将使用dijkstra算法, 否则使用A*算法

  • use_quadratic: true    设置为true,将使用二次函数近似函数计算potential,否则使用更加简单的计算方式,这样节省硬件资源

  • use_grid_path: false    默认使用梯度下降法,路径更为光滑,从周围八个栅格中找到下降梯度最大的点。 如果为true,使用栅格路径,从终点开始找上下或左右4个中最小的栅格直到起点,会规划一条沿着网格边界的路径,偏向于直线穿越网格

  • old_navfn_behavior: false    navfn是非常旧的ROS系统中使用的,现在已经都用global_planner代替navfn了,所以不建议设置为true.

  • lethal_cost: 253    致命代价值,默认是设置为253,可以动态来配置该参数.

  • neutral_cost: 50    中等代价值,默认设置是50,可以动态配置该参数.

  • cost_factor: 3.0    代价地图与每个代价值相乘的因子.

  • publish_potential: true    是否发布costmap的势函数.

  • orientation_mode: 0    如何设置每个点的方向(None = 0,Forward = 1,Interpolate = 2,ForwardThenInterpolate = 3,Backward = 4,Leftward = 5,Rightward = 6)(可动态重新配置)

  • orientation_window_size: 1    根据orientation_mode指定的位置积分来得到使用窗口的方向.默认值1,可以动态重新配置.

       A*和Dijkstra两种算法

两种算法的效果对比
A.png
Dijkstra.png

A*Dijkstra少计算很多,但可能不会产生相同路径。另外,在global_planner的A*里,the potentials are computed using 4-connected grid squares, while the path found by tracing the potential gradient from the goal back to the start uses the same grid in an 8-connected fashion. Thus, the actual path found may not be fully optimal in an 8-connected sense. (Also, no visited-state set is tracked while computing potentials, as in a more typical A* implementation, because such is unnecessary for 4-connected grids).

话题

发布的话题是~<name>/plan(nav_msgs/Path),即最新规划出的路径,每次规划出新路径就要发布一次,主要用于观测。

GlobalPlanner::initialize

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
if (!initialized_)
{
ros::NodeHandle private_nh("~/" + name);
costmap_ = costmap;
frame_id_ = frame_id; //costmap_ros->getGlobalFrameID()

unsigned int cx = costmap->getSizeInCellsX(), cy = costmap->getSizeInCellsY();
// 参数赋值, 默认false
private_nh.param("old_navfn_behavior", old_navfn_behavior_, false);
if(!old_navfn_behavior_)
convert_offset_ = 0.5;
else
convert_offset_ = 0.0;

bool use_quadratic; // 二次方的
private_nh.param("use_quadratic", use_quadratic, true);

// p_calc_声明为PotentialCalculator指针
// QuadraticCalculator是它的派生类, 唯一区别是覆盖了calculatePotential函数
if (use_quadratic) // 默认使用二次
p_calc_ = new QuadraticCalculator(cx, cy);
else
p_calc_ = new PotentialCalculator(cx, cy);

bool use_dijkstra;
private_nh.param("use_dijkstra", use_dijkstra, true);
//DijkstraExpansion 和 AStarExpansion 都继承 Expander类
if (use_dijkstra)
{
DijkstraExpansion* de = new DijkstraExpansion(p_calc_, cx, cy);
if(!old_navfn_behavior_)
de->setPreciseStart(true);
planner_ = de; // Expander* planner_;
}
else // 如果不用dijkstra,就用A星算法.
planner_ = new AStarExpansion(p_calc_, cx, cy);

bool use_grid_path;
private_nh.param("use_grid_path", use_grid_path, false);
// GradientPath 和 GridPath都继承了Traceback
if (use_grid_path)
path_maker_ = new GridPath(p_calc_);
else
path_maker_ = new GradientPath(p_calc_);

orientation_filter_ = new OrientationFilter();
// NavfnROS::initialize中也注册此话题
plan_pub_ = private_nh.advertise<nav_msgs::Path>("plan", 1);
potential_pub_ = private_nh.advertise<nav_msgs::OccupancyGrid>("potential", 1);
// 一系列参数赋值
private_nh.param("allow_unknown", allow_unknown_, true);
planner_->setHasUnknown(allow_unknown_);
private_nh.param("planner_window_x", planner_window_x_, 0.0);
private_nh.param("planner_window_y", planner_window_y_, 0.0);
private_nh.param("default_tolerance", default_tolerance_, 0.0);
private_nh.param("publish_scale", publish_scale_, 100);

double costmap_pub_freq;
private_nh.param("planner_costmap_publish_frequency", costmap_pub_freq, 0.0);

//get the tf prefix
ros::NodeHandle prefix_nh;
tf_prefix_ = tf::getPrefixParam(prefix_nh);

make_plan_srv_ = private_nh.advertiseService("make_plan", &GlobalPlanner::makePlanService, this);

dsrv_ = new dynamic_reconfigure::Server<global_planner::GlobalPlannerConfig>(ros::NodeHandle("~/" + name));
dynamic_reconfigure::Server<global_planner::GlobalPlannerConfig>::CallbackType cb = boost::bind(
&GlobalPlanner::reconfigureCB, this, _1, _2);
dsrv_->setCallback(cb);

initialized_ = true;
} else
ROS_WARN("This planner has already been initialized, you can't call it twice, doing nothing");

参考:
ROS- global_panner
global_planner历史背景和概述


Dijkstra算法

以下面的加权图举例,说明算法的过程
加权图
加权图中不可有负权边
伪代码.png
或者这样理解:

  1. 第一个核心步骤:找到当前未处理过的顶点中 最小的点 V,(由于起点到起点的消耗为0,所以算法开始时 V 必定代表起点);
  2. 第二个核心步骤:若V有邻居,则计算经过 V 的情况下起点到达各邻居的消耗 ,并选择是否更新 V 邻居的值。若没有邻居则对该点的处理结束
  3. 重复以上两个核心步骤,直到满足算法终止的条件:有向图中所有的点都被处理过。

算法每处理完一个顶点后,该顶点对应的 值就是起点到该点的最短路径长度,且在这之后不会被更改。这就是最短路径的原因
过程 1
过程 2

Dijkstra的特点是从起点开始,由近及远,层层扩展。越靠前处理的点离起点越近,最后一个处理的点离起点最远。
即使我只想找两个点之间的最短路径,Dijkstra还是需要遍历所有节点,因此时间复杂度为,所以不适合复杂路径等大规模场景。


A星算法

地图和起点,终点

算法的伪代码.png

1.jpg

2.jpg

3.jpg

公式表示为:f(n)=g(n)+h(n),其中f(n)是经过节点n从初始点到目标点的代价函数,g(n)表示从初始节点到节点n的代价,h(n)表示从节点n到目标点的启发式代价

  • Dijkstra是无目的的扩展,A星是启发式,选择离目标点最近的方向扩展,但不一定是最短路径。
  • Dijkstra算法的实质是广度优先搜索,是一种发散式的搜索,所以空间复杂度和时间复杂度都比较高。
  • 对路径上的当前点,A*算法不但记录其到源点的代价,还计算当前点到目标点的期望代价,是一种启发式算法,也可以认为是一种深度优先的算法。