Encyclopedia
Please note this is an old version of this entry, which may differ significantly from the current revision.
Subjects:
Automation & Control Systems
One of the most significant processes in the autonomous navigation is path planning. Path planning involves the determination of a possible path for a mobile robot to move from a start to a target location in a particular environment while considering optimization parameters like path distance, time and path smoothness. Mobile robot path planning is a subcategory of trajectory planning.
- path planning
- wheeled mobile robot
- generalized laser simulator
1. Introduction
One of the most significant processes in the autonomous navigation is path planning [1]. Path planning involves the determination of a possible path for a mobile robot to move from a start to a target location in a particular environment while considering optimization parameters like path distance, time and path smoothness [2,3,4]. As a result, the mobile Robot is expected to reach its destination within the shortest time.
Robots have been proven to be useful in various industries, including in areas which are inaccessible to humans. In recent years, autonomous navigation and path planning have attracted attention for a wide range of applications in which robots must operate in complex and hazardous environments [5]. A large amount of work is being performed to develop an intelligent algorithm that can be applied to navigating a mobile robot without a need for manual assistance.
Path planning is divided into two types, namely global and local path planning. In global planning, the autonomous robot requires information about the environment, the starting and end locations, and the positions of obstacles (all of which deal with an entirely known environment). In contrast, such information is not known (somewhat known and unknown environment) in local path planning [6].
There are two categories of obstacle settings, namely static and dynamic obstacles. In the former, the complete path must be determined prior of the start of robot movement; however, in the latter, replanning in real time is often required in dynamic or partially unknown environments, which takes a long time for path determination. The path-planning problem can be described briefly in the following steps: firstly, a feasible path for the robot must be determined based on defined start and goal positions in both known and unknown environmental settings. Secondly, the mobile robot should be able to avoid collisions with dynamic and static obstacles. Additionally, the mobile robot should complete the obstacle avoidance and pathfinding tasks using the shortest path and the least amount of time.
The advancement of automation and in-depth research in autonomous navigation technology has facilitated an increase in the use of autonomous robots in a wide range of industrial applications, including nuclear power plants using Grid-based rapidly random exploring trees GB-RRT* [7], space exploration using Ordered Upwind Method based Direction-dependent optimal path planning (OUM-BD) [8], rescue missions, mines, and war zones [9,10]. Planning algorithms are also helpful for frequent operations in static environments wherein optimality is needed (for example, industrial applications) [11,12,13,14].
To achieve the path-planning goal, many factors should be taken into consideration, such as the obstacle and map borders. Furthermore, factors such as static/dynamic obstacles and complete/partial unknown environments increase the difficulty of handling the path-planning problem. In an unknown setting, the mobile robot must execute simultaneous localization and mapping while exploring the environment, known as the simultaneous localization and mapping (SLAM) problem [5]. Although robot path planning in a known environment with static obstacles is considered an easy task, path planning in a dynamic environment is a challenging and fascinating area of robotics research.
2. Background and Related Works of Mobile Robot Path Planning
Mobile robot path planning is a subcategory of trajectory planning. The aim is to determine an optimal path from a defined start to a goal point without considering kinematics and control inputs [15,16].
A feasible path for the robot in a predictable environment can be generated using global path planning approaches. Global planning methods are searching for an optimal path in known environments which is particularly successful static environments. Some of the most popular methods include Voronoi diagrams [17,18], visibility graphs and adaptive roadmaps [19], and virtual force fields (VFF) [20].
In contrast, local planning is built based on a dynamic approach that relies entirely on local perception instead of knowing the entire environment. Since the workspace is uncertain, local planning guides the mobile robots to detect nearby obstacles and take appropriate action. To avoid unexpected problems that may occur with dynamic obstacles, reactive planning must be precise and work in real time. Such situations often lead to failures in global path planning. When an unexpected obstacle appears in the robot’s path, it is necessary to re-plan to avoid colliding with the obstacle [21]. Planning in an unpredictable setting is a complicated issue due to the generated map must always be adjusted at every iteration of the path planning algorithm. To offer a complete solution to such a problem, many autonomous systems combine the features of global and local navigation systems [22].
The uncertainty and complications of the path-planning problem in a local environment with obstacles have drawn the interest of many researchers [23] and have been a subject of great interest in recent years. As a result, such path planning algorithms have been thoroughly explored, with several approaches and the solutions presented to solve this problem being as follows:
The artificial potential field (APF) method, invented by Khatib [24], is a traditional path-planning method based on potential energy (gravity, magnetic field, or gravitational). A robot in the coordinate space could travel using this method while being driven by attractive and repulsive fields produced by obstacles and targets. This method is used in the robotics field due to its analytical clarity, real-time performance, and ease of use in determining the shortest path from start to goal positions.
Barraquand et al. have introduced a search-based path-planning method based on the potential field with a direct path search [25]. Despite the many benefits that APF provides due to its simple structure, it has certain drawbacks, such as that the robot can become trapped in local minima based on the obstacle location and the potential field they produce. To address this issue, several studies have proposed various ways to avoid local minima in APF [26].
Virtual field histogram (VFH) [27,28] and enhanced VFH+ [29] are prominent approaches that describe the sensor uncertainty due to spatial data from sensors, similar to APF. VFH and APF will perform efficiently with dynamic and static obstacles in constrained settings. Numerous path planning methods that consider obstacles in unpredictable settings have been discussed in [22,30,31]. Ayawli et al. [32] provided a path-planning method in an uncertain environment based on the Voronoi diagram and computation geometry technique (VD-CGT), employing VD and mathematical modeling, with a narrow rectangular area around the robot used to assess collisions. Ravankar et al. have described collision detection based on virtual obstacles using VD-CGT [33]; however, in [34,35], they show how to use dispersed obstacle knowledge transfer for collision avoidance and path planning in complex environments with multiple robots.
Sampling techniques are remarkable because they use deterministic function sampling to plan using the C-connection space. These functions create a map of the robot’s possible C-space movements [36]. Due to its effectiveness, the sampling-based planning (SBP) methods have received close attention in recent years. The common sampling-based planners are probabilistic road maps (PRM) [37] and rapidly random exploring trees (RRT) [38]. The PRM’s fundamental idea revolves around the distribution of nodes over C-space before connecting them with horizontal lines that form a roadmap graph. By confining the search to a network and interconnecting the free working space, the PRM can effectively determine the shortest paths.
The RRT and PRM algorithms address local minima and high computation periods for pathfinding due to their outstanding practical performance and solid theoretical characteristics [39,40]. A potential function based-RRT* (P-RRT*) integrates APF in RRT* to enhance the convergence of the path into optimal solution [39]. Such algorithms compute many dispersed sample points throughout the free space and link them to establish a tree from which a path is found using a search method using Improved A* [41]. The rapidly exploring random trees (RRT) technique has been frequently used in the literature, but the selection of a specific tree to be expanded is the most critical issue that impacts the overall efficiency of path planning in RRT. Wang et al. [42] have presented revolutionary multi-RRTs based on learning for mobile robot path planning (LM-RRT) in narrow passages.
Bidirectional-RRT [43] uses a bidirectional tree search for faster path planning. Similarly, work in [44] proposed a lazy PRM method, an enhanced PRM that minimizes the frequency of collision tests that occur during pathfinding and, therefore, minimizes the planner’s run time. On the other hand, the work presented in [45] demonstrated how to improve the roadmap’s connectivity by linking previously developed connected components. Probabilistic road maps-star (PRM*) is an improved variant of the initial PRM method, which was proposed by [46]. With such a method, the number of sample nodes determines the connection distance. As the number of samples grows, the connection radius gets smaller, making it easier to move from one place to another. For moving from one node on the generated roadmap to the next, SBP approaches employ a local planner. The planning issue is resolved by finding the shortest route between the start of the roadmap on one side and the roadmap to the goal on the other side. Search-based techniques, such as the Dijkstra and A* algorithms, have been used to discover the shortest paths on a built network. The A* method starts by examining the undiscovered node and has the lowest projected cost [47]. These search plans are fast and can work with maps of various sizes. By analyzing the mechanics of the robotic system, when the design has been generated on the graph, the path smoothing methods can generate a smoother path from start to goal positions [48] such as Infused Tangential Curves (ICT) method [49].
Several authors have studied the advantages of the genetic algorithm (GA) for addressing the planning problems for autonomous robots in complex environments. Some of these algorithms depend on a novel fitness function for controlling the distance, safety, and energy of the robot [50], a knowledge-based GA [51], and adaptive GA [52]. Another way to find a collision-free path is to calculate artificial potential values using GA. This method was initially used in [24] for solving the obstacle-free mobile robot path-planning problem. The robot is considered as an object that is navigating in various surroundings, and the technique is cantered upon the attraction and repulsion forces produced by the goal and obstacles [52].
The authors in work [53] presented a hybrid metaheuristic based on the genetic algorithm–particle swarm optimization (GA–PSO) method for mobile robot path planning in grid maps to determine a feasible path from predefined starting and ending points. In contrast to traditional GA and PSO algorithms, the suggested technique avoids computational complexity and premature convergence. First, the integer factorization problem (IFP) is generated using a hybrid GA–PSO, and then a cubic B-spline method is adopted to provide a near-optimal obstacle-free path. Bi et al. have presented a robot-path-planning approach using fuzzy logic and evolutionary algorithms to lower the complexity of robot path planning during obstacle avoidance in a dynamic environment [54].
The use of deep reinforcement learning (DRL) for robot navigation in environments with unknown rough topography, such as in urban search and rescue (USAR), is investigated by Zhang et al. [55]. In this work, they created an Actor-critic-model-3 (A3C)-based network that employs depth images, elevation maps, and 3D orientation as inputs to identify the best robot navigation movements. The network was trained in a series of simulated 3D environments that have been varied in traversal motion. The experiment’s results reveal that when the rough terrain is unknown, the DRL approach may successfully navigate a robot in an environment to a specified target location.
A detailed study on the computational intelligence (CI) algorithms with the time domains and the environment models that are used for 2D/3D-unmanned aerial vehicle (UAV) path planning was presented by Zhang et al. [56]. The authors analyzed the modeling, optimization criteria, and path planning algorithms for UAV robots and concluded that the common methods to address the path planning of mobile robots are genetic algorithm (GA), particle swarm optimization algorithm (PSO), artificial potential field (APF), and ant colony optimization algorithm (ACO).
Patle et al. [57] have thoroughly examined several mobile robot navigation techniques that are now commonly used in robotics applications. The investigations of classical and reactive approaches were presented in detail. The review compares tabular data and charts for the individual navigational strategies that can be used with specific robotics applications. Seckin [58] has presented a method for robot navigation using the real-life bookmarks arranged in its memory. With this method, the robot utilizes the memorized traveled path with several key points to plan its path from starting to target positions. It uses the laser detection and ranging sensor (LIDAR) for mapping the environment into 2D maps. The robot is then driven on its path using the previously prepared map in its memory. Another method for memorizing the robot’s path through generating a network of reuse paths in planetary exploration has been proposed by Stenning et al. [59]. It expands the visual teach and repeat method that allows the robot to visit and revisit any network nodes. To select the right path, the rapidly exploring random tree (RRT) method is used to effectively plan the robot’s path in such networks. Khan et al. have proposed RNN-based metaheuristic algorithms for obstacle avoidance, robot path planning, and control [60,61]. Table 1 shows a comparison between reviewed methods in mobile robot path planning in terms of algorithms, testing types (simulation or physical), sensors used, obstacle avoidance, and indoor/outdoor applications, as follows:
Table 1. Illustrates a comparison between reviewed works.
| Author Year | Algorithm | Static Obstacle | Dynamic Obstacle | Mapping | Online Path Planning | Indoor/Outdoor | Type of Test |
|---|---|---|---|---|---|---|---|
| Zhang 2018 | DRL | Yes | Yes | 3D | No | - | Simulation |
| Chao 2018 | GB-RRT | Yes | No | 2D | No | - | Simulation |
| Shum 2015 | OUM-BD | Yes | No | 2D | No | - | Simulation |
| Zhang 2012 | Multi-objective PSO | Yes | No | 2D | No | - | Simulation |
| Bakdi2017 | GA/AFL | Yes | No | 2D | Yes | Indoor | Simulation/Experiment |
| Han 2017 | SPS/PI FLP | Yes | No | 2D | No | - | Simulation |
| Muhammad 2021 | GLS | Yes | Yes | 2D | Yes | Indoor/Outdoor | Simulation/Experiment |
| Khatib 1985 | APF | No | Yes | 2D | Yes | Indoor | Simulation/Experiment |
| Barraquand 1992 | PF | Yes | Yes | 2D | No | - | Simulation |
| Cetin 2012 | APF | Yes | No | 2D | No | - | Simulations |
| Borenstein 1991 | VFHV | Yes | No | 2D | No | Indoor | Simulation/Experiment |
| Ulrich 2000 | VFH* | Yes | No | 2D | Yes | Indoor | Simulation/Experiment |
| Ulrich 1998 | VFH+ | Yes | No | 2D | Yes | Indoor | Simulation/Experiment |
| Ravankar 2020 | VFH+ | Yes | Yes | 2D | Yes | - | Simulation |
| Tuncer 2012 | GA | Yes | Yes | 2D | No | - | Simulation |
| Ayawli 2019 | VD/CGT | Yes | Yes | 2D | No | - | Simulation |
| Ravankar 2019 | VD/CGT | Yes | Yes | 2D | Yes | Indoor/Outdoor | Simulation/Experiment |
| Ravankar 2017 | VD/CGT | Yes | Yes | 2D | Yes | Indoor/Outdoor | Simulation/ Experiment |
| Ravankar 2017 | VD/CGT | Yes | Yes | 2D | Yes | Indoor/Outdoor | Simulation/Experiment |
| Qureshi 2016 | P-RRT* | Yes | No | 2D | No | - | Simulation |
| Fu 2018 | Improved A* | Yes | No | 2D | Yes | Indoor | Simulation/Experiment |
| Wang 2018 | LM-RRT | Yes | No | 2D | Yes | Indoor | Simulation/Experiment |
| Xinyu 2019 |
Bidirectional-RRT | Yes | No | 2D | Yes | Indoor | Simulation/Experiments |
| Bohlin 2000 |
Lazy PRM | Yes | No | 2D | Yes | Indoor | Simulation/Experiment |
| Karaman 2011 |
PRM* & RRT* | Yes | No | 2D | Yes | - | Simulation |
| Ravankar 2019 |
ITC | Yes | No | 2D/3D | Yes | Indoor | Simulation/Experiment |
| Lamini 2018 |
GA | Yes | No | 2D | No | - | Simulation |
| Hu 2004 | GA | Yes | Yes | 2D | No | - | Simulation |
| Karami 2015 | GA | Yes | No | 2D | No | - | Simulation |
| Huang 2011 | GA-PSO | Yes | No | 2D | No | - | Simulation |
| Bi 2008 | GA-FL | Yes | Yes | 2D | Yes | - | Simulation |
| Ali 2019 | LS/Sensor fusion | Yes | No | 2D | Yes | Indoor/ Outdoor |
Simulation/Experiment |
| Ali 2020 | LS/FL | Yes | No | 2D | Yes | Indoor/ Outdoor |
Simulation/Experiment |
| Ali 2018 | LS/Vision system | Yes | No | 2D | Yes | Indoor/ Outdoor |
Simulation/Experiment |
The contribution of this paper is to present an approach for mobile robot path planning in complicated environments with the presence of obstacles. In circumstances where standard methods fail to offer a solution, such as for small passages, obstacle avoidance, and local minima problems, the generalized laser simulator (GLS) can overcome such associated path-planning problems. Furthermore, the algorithm presented an optimized version that will generate pathways with lesser nodes and a greater success rate while being computationally efficient. It is an enhancement of the laser simulator method, which has been successfully adopted in many works [62,63,64,65] and an extension of [1] for avoiding obstacles during path planning.
This entry is adapted from the peer-reviewed paper 10.3390/s22218177
This entry is offline, you can click here to edit this entry!
