解读 Path Planning with Risk Consideration by Hopping Mobility for Long Distance Traversability
[toc]
本文运用星球跳跃漫游者 (hopping rover) 的移动特性 (可以跳过而不是绕过障碍物)，提出了一种新的路径规划和导航方法，并且讨论了因为跳跃行为和测量误差带来的不确定性。
In this paper, a navigation method for a small size hopping rover with advantages on its mobility is discussed by considering with some uncertainties caused by jumping behavior and measurement error.
和通常的路径规划一样，本文首先从环境数据中提取障碍物，构建三角形 (triangular polygons) 的环境网格，然后使用 A star 算法来规划安全的路径。其中，算法着重考虑了和障碍物的碰撞风险，复杂地形 (roughness of terrain) 和失败的跳跃行为 (failures of hopping action)。
By extracting obstacles from environmental data and constructing triangular polygons it is possible to form paths. The algorithm considers with safety of collision with obstacles, roughness of terrain and failures of hopping action, and then could generate safer path based on A* algorithm.
多平台维护不易，内容实时更新于 个人网站，请移步阅读最新内容。
INTRODUCTION
目前，月球等星球的表面探索主要是使用一个笨重的履带机器人 (heavy wheel rovers)，但是履带机器人开发周期长，发射时极少，对安全的需求要求更多的资源来保障，甚至进入了恶性循环。
作者提出一种新的方法，使用多个轻量紧凑的探索机器智能体 (light and compact exploration robot agent) 来共同工作，构成一个大的智能体。
One possibility is the introduction of a light and compact exploration robot agent, and it is possible that multiple types of agents work together in one system. Various roles (functions) can be played on various kinds of equipment, and all of them can constitute one exploration system.
一个创意：通过将同样的功能分散到若干个智能体上，可以忽略一定程度的智能体功能失效，那么风险被分散到整个大系统上，有可能获得较高的效率。
By allocating the same function (equipment) to some or many of them, it is possible to ignore some percentage of the agent's loss rate, so that risk can be distributed to the system and the mission and there is a high possibility of obtaining higher efficiency.
虽然小机器人 (A small size rover) 因为大小 (size) 和重量 (weight) 有很多优势，但是其移动性 (traversability) 和测量能力 (measurement) 却受到局限。
However, its size causes problems on its traversability and measurement ability.
所以，可以引入跳跃行为 (hopping mobility) 来获得更高的移动性能 (higher traversability) 和更广的测量范围 (wider measurement range)。
We have introduced hopping mobility to obtain higher traversability and wider measurement range.
通过固定区域的地面机器人 (land-based agent) 和跳跃机器人互相配合，来构成探测系统 (exploration system)。
Introduction of two types of rovers is being considered in the exploration system. One is a land-based agent and a stochastic existence region is given in the search region, contributing to the search of the ground surface. The other is hopping rover. the rover that makes path planning taking advantage of sensing from high places while moving the exploration area together with the ground moving rover plays an important role.
- 相比轮式机器人，在低重力环境下 (low gravitational environment)，可以通过跳跃的方式跳过障碍物，从而抄近路 (adopt a short-cut path)。
Especially under low gravitational environment such as other planet or satellite, it indicates higher performance, e.g.Thus, it can jump over a long distance upon terrains and obstacles, adopt a short-cut path without a detour of a wheeled type, and also measure an environment from higher position in the air of jumping trajectory.
ISSUE AND OBJECTIVES
- 为什么导航问题需要研究：现有的导航研究，没有利用跳跃机器人的运动特性 (文章发表于 2017)，所以需要进一步利用跳和远距离的优势来导航。
For a hopping rover, though a lot of jumping hardware designs have been studied, its software e.g. navigation algorithms have been discussed hardly. So, the navigation method hasn't been established by taking advantage of hopping mobility such as jumping over obstacles or a long distance yet.
本文利用跳跃机器人的运动特性，基于对移动性和测量数据的风险考虑，提出一种导航方法 (主要是如何规划路径)。
In this paper, a navigation method for a small size hopping rover with advantages on its mobility is discussed with some risk considerations on its mobility and measured data.
PATH PLANNING FOR HOPPING MOBILITY
Selection of Jumping Target Position
移动机器人跳跃行为 (jumping motion) 的不确定性包括初始速度变化 (initial speed change)，跳跃距离 (jump distance)，跳跃方向 (jumping direction)，落地后的束缚 (bound after landing) 以及跳跃失败 (failure of leap)。
The uncertainty factor of hopping rover's jumping motion is the initial speed change, jump distance, jumping direction, bound after landing, failure of leap.
因为跳跃行为的不确定性，所以需要选取目标落地点 (landing point)。
如何环境建模
- 连接被识别到的障碍物，构成不规则三角形的环境模型。
Each obstacle captured by sensing is connected and the observation area is divided into triangles
- 在观测到的障碍物上使用狄洛尼三角剖分 (Delaunay triangulation)，可以获得每三个点的外心 (outside heart)，即可能的落地点。
By using Delaunay triangulation on the observed obstacles, we can set the landing point.
> Delaunay三角剖分定义：平面上的点集P是一种三角剖分，使得P中没有点严格处于剖分后中任意一个三角形**外接圆**的**内部**(可以是圆上)。
外心安全设定：假设外心是落脚点，那么它到三个端点的距离是一致的，只要有一定的距离保障，就可以确保安全。
Since the outer heart is equally distant from each vertex, it can be said that it is safe if a certain margin can be secured.
Safety distance is secured by creating a circumscribed circle (其实是 delaunay triangulation) so as not to include other obstacles in the circle
Candidate Path Network
- 通过连接外心，可以得到一个维诺图 (Voronoi diagram)。
The Voronoi diagram is a method of dividing the region by joining the outer centers formed by Delaunay triangulation.
MC: 什么是 Voronoi diagram？ Voronoi diagram
> 泰森多边形是对空间平面的一种剖分，其特点是多边形内的任何位置离该多边形的样点（如居民点）的距离最近，离相邻多边形内样点的距离远，且每个多边形内含且仅包含一个样点。维诺图安全设定：维诺图包含障碍物，那么可以生成安全的节点 (safe nodes)。
It can be confirmed that there are no obstacles on the sides of the Voronoi diagram enclosing the obstacles and safe nodes can be generated.
Add Uncertainty
作者设定跳跃运动有一定的不确定度，误差通常是正态分布 (不清楚是否有理论依据)，取决于初始速度，跳的角度，方向角。
The error is generally given in the form of a normal distribution, which rides on the initial speed, the jumping angle, and the direction angle, respectively.
基于上述假设，rover 在未来的位置误差会累加 (accumulated)，可以使用一个误差椭圆 (error ellipse) 来表示。
The position of the rover can be indicated as the existence probability, and generally takes a shape called an error ellipse.
MC: 通过椭圆来表示误差和不确定性，算是一个新奇的做法。
SIMULATION OF PATH PLANNING
作者在一个很理想的环境下仿真，认为对于非质点的、大块的障碍物仍然可以规划出路径，但是没有讲清楚，如何实现？假设障碍物很高，那么跳跃机器人是否就无法跳跃过去呢？
Even if the obstacle is the size of the black part of the figure.
在虚拟的月球环境下仿真，比简单的理论仿真，更具有说服力。
Simulation was also carried out in the virtual lunar environment created based on the rock distribution collected by “Surveyor 7” of NASA.
当在椭圆内的障碍物到达一定比例后，进行位置的自校正 (self-position estimation)。
When the occupancy rate of the obstacle in the error ellipse exceeds the threshold value, the rover performs self-position estimation.
CONCLUSION
The results of this research
- In consideration of the uncertainty of the hopping rover, we were able to determine a safe landing point.
- By performing self-position estimation in the virtual lunar environment, it was possible to induce Rover while suppressing position error.
Works to do
- 路径规划限于 2 维，缺乏对障碍物和跳跃高度的考虑。
- 如何切分大的障碍物，而不仅仅是把障碍物作为质点考虑。
- 跳跃机器人的设计，物理构建，环境识别，以及规划好路径后，如何对跳跃行为进行控制，准确抵达目标点。