Hello, Welcome to Hangzhou Qogori Technology Co., Ltd. (K2 Tech) official website!
TEL:+86 18072831879

Path Planning

Multi-angle shooting point cloud fusion, build a complete 3D model, and generate the robot execution path according to the actual application.


Path planning from location A to location B, simultaneous obstacle, avoidance and reacting to environment changes are simple tasks for humans but not so straightforward for an autonomous vehicle. These tasks present challenges that each wheeled mobile robot needs to overcome to become autonomous. A robot uses sensors to perceive the environment (up to some degree of uncertainty) and to build or update its environment map. In order to determine appropriate motion actions that lead to the desired goal location, it can use different decision and planning algorithms. In the process of path planning, the robot’s kinematic and dynamic constraints should be considered.

Planning algorithms

Global path planning is a relatively well-studied research area supplied with many thorough reviews; see, e.g., [111, 112]. MPC may be implemented with a number of different path-planning algorithms. The main relevant measure of algorithm quality is completeness, which indicates whether calculation of a valid path can be guaranteed whenever one exists. Some common global path-planning algorithms are summarized as follows:

Rapidly-exploring random trees. This method is based on building a tree of possible actions to connect initial and goal configurations; see, e.g., [183, 184]. Some variants are provably asymptotically optimal [184].

Graph search algorithms. Examples include A* and D* algorithms (see, e.g., [185] and [186], respectively), and Fast Marching; see, e.g., [187]. Most methods hybridize the environment into either a square graph, an irregular graph [188], or a Voronoi diagram [187], where the latter is the skeleton of points that separates all obstacles. A search can then be performed to calculate the optimal sequence of node transitions. In addition, this may be used as the first step to find a bounded area within which further path-planning operations can take place [189].

Optimization of predefined paths. Examples include Bezier curves [190], splines [191], and polynomial basis functions [20]. While these are inherently smoother, showing completeness when using them may be more difficult in some situations.

Artificial potential field methods. These methods will be introduced in Section 3.4.3, as they are also ideally suited to online reactive navigation of robots (without path planning). These can also be used as path planning approaches, essentially by using more information about the environment; see, e.g., [192, 193]. However, the resultant trajectories would not be optimal in general.

Mathematical programming and optimization. This usually is achieved using Mixed Integer Linear Programming constraints to model obstacles as multiple convex polygons [194]. Currently, this is commonly used for MPC approaches.

Tangent graph based planning. This limits the set of trajectories to cotangents between obstacles and obstacle boundary segments, from which the minimum distance path being found in general [16, 195]. The problem of shortest path planning in a known environment for unicycle-like mobile robots with a hard constraint on the robot’s angular speed was solved in [16]. It was assumed that the environment consists of a number of possibly non-convex obstacles with a constraint on the curvatures of their boundaries, along with a steady target that should be reached by the robot. It has been proved that the shortest (minimal in length) path consists of edges of the so-called tangent graph. Therefore, the problem of the shortest path planning is reduced to a finite search problem.

Evolutionary algorithms, simulated annealingparticle swarm optimization. These are based on a population of possible trajectories, which follow some update rules until the optimal path is reached; see, e.g., [196, 197]. However, these approaches seem to be suited to complex constraints, and may have slower convergence for normal path planning problems.

Partially observable Markov decision processes. This approach is based on calculating a type of decision tree for different realizations of uncertainty. It also employs probabilistic sampling to generate plans that may be used for navigation over long time frames; see, e.g., [198]. However, this may not be necessary for all MPC-based navigation problems.

Follow us

Company Add: 4th floor, No. 7 building, Jinsheng industrial park, No. 611, Dongguan road, Binjiang district, Hangzhou city, Zhejiang, China
Postal Code: 310053
Sale:+86 18072831879
Overseas offices: Korea office | India office