EDP Sciences logo
Submit your paper
Search
Menu
Home All issues Volume 12 (2021) Int. J. Simul. Multidisci. Des. Optim., 12 (2021) 24 Full HTML
Issue
Int. J. Simul. Multidisci. Des. Optim.
Volume 12, 2021
Advances in Modeling and Optimization of Manufacturing Processes
Article Number 24
Number of page(s) 8
DOI https://doi.org/10.1051/smdo/2021024
Published online 27 October 2021

© B. Esakki et al., Published by EDP Sciences, 2021

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1 Introduction

Unmanned Aerial Vehicles (UAVs) are of its prominence in military, societal, environmental, disaster response, infrastructure monitoring and wild life monitoring missions [1–5]. Especially, rotary wing UAVs (RWUAVs) are considered to be more popular because of its inherent hovering characteristics, simplicity in design and construction, agile in nature and easy vertical take-off and landing ability [6]. Nevertheless, the RWUAVs are suffering for the flight endurance due to limited storage capacity of the batteries. In order to efficiently utilize the available power source to navigate in the clustered environment an optimal path planning of RWUAV is necessary. In general, path planning involves various factors such as path distance, number of diversions, execution time and collision-free space which are playing a significant role in determining the best path [7]. Popular path planning algorithms on a grid-based generally suit low-dimensional environments. They used to map the environment with a grid by partitioning the domain with respect to small cells [8]. The first heuristic-based approach was the Dijkstra algorithm [9]. Nonetheless, in high-dimensional environments, it has reduced search efficiency. As a result, for UAV applications such as path planning, it is not the best approach. Extended Dijkstra was used to solving problems with path navigation at a specific time [10]. Wavefront can be used to solve path planning issues [11]. It creates a cost matrix in the grid and selecting the lowest cost and perform reverse tracking from the starting to the goal node. Thompson et al. [12] used the Slocum glider with the Wavefront planner to forecast 48-hour ocean currents. Tang et al. [13] findings show that when comparing a modified wavefront to a normal wavefront, there is a 19% improvement. A* is the first best search methods [14] developed from Dijkstra varieties, are widely used in algorithms such as route planning in computer games and robotics. A* works with respect to tracking the grid cell edges and may not traverse into the complex environment [15]. The memory requirement to store the earlier visited nodes also a challenging issue for intricate surroundings. As a result, central processing unit processing time and storage capacity increases. Hence, in order to overcome the aforementioned issues, several variants of A* algorithms have been presented. The iterative-deepening A* (IDA*) was proposed [16] to address the vast memory requirements imposed by the A* algorithm. However, the IDA* was not performing well to identify and select subsequent possible nodes. It is used to select the same node multiple times that made slower performance than A*. In addition, in order to resolve the issue of following the grid edges of individual grid cells to determine an optimal path, a Theta* [17,18] algorithm was proposed. It was found that Theta* performance is much slower than A* in finding an optimal path. However, another variant of A*, namely Field D* (FD*), was formulated [19] to avoid following the edges of the grid cell. It was observed that FD* made more number of turns which are unnecessary than the A* algorithm [19–21]. Recently, the Memory Efficient A* (MEA*) algorithm [15] is becoming popular because of the fact that it does not require large memory and avoiding the edges of the grid cells in contrast to A* for finding an optimal path. It was proven to be an efficient algorithm to determine an optimal path in fewer turns with very minimal execution time. Hence, this work focuses on path planning of RWUAVs in obstacle prone regions to minimize the execution time and avoid unnecessary more requirements. Comparative evaluation analysis will be performed with standard A* algorithm with MEA* to show case the effectiveness of the present approach.

2 UAV path planning algorithms

Path planning in UAV applications [22] to avoid obstacles in a constrained environment is challenging. In this work, in order to efficiently find an optimal path A* and MEA* algorithms are compared. The following section provides an overview of these two algorithms

2.1 A* algorithm

A* is a graph traversal and path searching algorithm which is widely used for finding an optimal path because of its completeness and optimality. It finds an optimal path with less computational efforts and it has memories to store the earlier visited nodes. It uses those memories to identify the best path that can be taken from its current state. It uses the following relation to identify the next node.(1)

where, F is the cost function; G is the cost of moving from one node to another node; H is the heuristic/estimated path between the current node to the destination node.

Based on this relation, the minimal cost function is determined to visit the forthcoming optimal nodal point. The consecutive optimal nodal points are determined based on this cost function to arrive at an optimal path by avoiding the obstacles. Figure 1 shows the steps involved in finding the optimal path in the A* algorithm. It is primarily based on heuristic cost efficiency, search space expands in high-dimensional areas, and applicable only in a static context. Since A* solution paths are made up of adjacent map values, the path solution is long and jagged.

thumbnail Fig. 1

A* algorithm.

2.2 MEA* algorithm

MEA* algorithm is a variant of the A* algorithm that primarily focuses on the stringent memory requirement of the A* algorithm and solving high dimensional grid environment [15]. A* also has an issue of tracking the edges of grids, and it may not provide an efficient optimal path. In order to overcome these bottlenecks for determining an optimal path in high dimensional space, the MEA* algorithm is developed. It has three lists, an empty list containing the nodes to be explored, a close list that has already explored nodes, and the parent list have the parent node of the current node. At the initial stage, all lists are set to empty.

Its cost function is given by(2)

where G(n) is cost from initial to present node and H(n) is the heuristic estimation cost from present to end node. Initially, G(n) is set to zero for the start point, and all other nodes in the map are assumed to be infinity. The minimum F-Value is considered and added to the open list and other nodes are ignored during each iteration. Due to this, execution time and memory requirements are minimized. However, A* considers all the neighboring nodes which are not necessary for an optimal path that causes more memory requirements and increases execution time. The flow chart shown in Figure 2 depicts the step-by-step process involved in MEA* algorithm.

The Table 1 describes the initial configuration of the MEA* matrix where boxes marked with 2 and 7 are the starting and ending cost respectively, similarly 1 and 0 represents the obstacles and the free path. The final configuration of the MEA* matrix given in Table 2 where in the boxes are shaded in green color marked with numbers other than 0 and 1 is denoted as minimum and maximum number for the path.

thumbnail Fig. 2

MEA* algorithm.
Table 1

Initial Configuration of MEA*.

Table 2

Final Configuration of MEA*.

3 Simulation analysis of path planning algorithms

In order to understand the efficiency of both the algorithms the obstacles in the environment is varied with few to many, narrow and concave passages are introduced. The C1, C2, C3, C4, and C5 are the various environmental map considered for the simulation studies given in Table 3. The simulation was performed on Intel i7 processor 64-bit Windows 7 platform with 8 GB of inbuilt memory and 8 RAM. Spyder was used to build a graphical simulation environment for performing mathematical and graphical comparison analyses. The Table 3 provides the simulation results of A* and MEA* algorithms.

The comparison between A* and MEA* algorithm with reference to execution time, path length and total number of turns to reach the target are calculated and they are shown in Figures 3-5 respectively.

Table 3

Comparison between A* and MEA* algorithms: Simulation results.

thumbnail Fig. 3

Execution time.
thumbnail Fig. 4

Total path length travelled.
thumbnail Fig. 5

Total number of turns.

4 Experimental analysis by real time UAV flight trials

The flight trials are conducted in the outdoor environment using a custom-built UAV platform. The hardware and software architecture, including the mission planner using a Ground Control Station (GCS), wherein optimal path is fed in from the simulation environment. In this study, Q Ground Control (QGC) software platform is utilized to navigate the UAV in the designated waypoints. A flight controller (Pixhawk 4) and an on-board computer (Raspberry Pi 3) to process the signal are embedded on the UAV.

In the event of navigation. GCS provides optimal waypoints, which is determined through an optimal path planning algorithm that will be fed into the flight controller. The latitude and longitude information for each waypoint are obtained from the on-board GPS sensor. As an output, GCS software displays the list of waypoints extracted from an optimal path. The Figure 6 shows a typical step-by-step process involved in providing input from GCS in navigating the UAV with respect to an optimal path on the predefined obstacles region to achieve designated inspection tasks. Outdoor experiments are performed by implementing the determined optimal path in real-time. The altitude of the UAV is kept at 15 m and vehicle speed is maintained at 2 m/s. The on-board computer receives the list of waypoints from GCS and executes the path planning algorithm in real-time. The desired position, velocity and yaw of UAV is obtained based on the waypoints, and the controller sends the control signal to the motor for achieving the navigation.

The planned trajectory for A* algorithm and the corresponding executed trajectory is also shown in Figure 7. Similarly, for MEA* algorithm flight trials are conducted and the optimal path is shown in Figure 8.

It is evident from Table 4 that, the MEA* outperforms with respect to decrease in distance travelled, minimal execution and flight time with less number of turns. Hence, it is envisaging to deploy MEA* algorithm for proficient path planning for UAV applications. Outdoor flight tests conducted at our university campus where in UAV is flying at an altitude of 15m in a stable manner.

The execution time of MEA* algorithm is compared with other algorithms and the percentage increase in execution time is tabulated (Tab. 5). It is evident that MEA* algorithm performs faster in comparison to other algorithms which is considered for path planning of UAVs.

thumbnail Fig. 6

UAV path planning using ground control station.
thumbnail Fig. 7

Optimal path of A* algorithm.
thumbnail Fig. 8

Optimal path of MEA* algorithm.
Table 4

Comparison between A* and MEA* algorithms experimental results.

Table 5

Comparison of execution time with other algorithms [15].

5 Conclusion

An efficient optimal path planning strategy using A* and MEA* algorithms is developed. Simulation analysis results of these two algorithms with respect to varied obstacles having narrow passages confirmed that MEA* outperforms A* algorithm in terms of execution of time, distance travelled and total number of turns it achieved. The experimental UAV flight trails in the outdoor environment to reach the destination from a target confirms that MEA* achieved superior performance than A* algorithm. The MEA* algorithm has resulted in 44% reduction in execution time, 31% saved flight time, 77% reduced number of turns and 3% less in execution time in comparison with A* algorithm. MEA* also reduced the stringent memory requirements and found an optimal path efficiently. Hence, the MEA* algorithm can be effectively utilized for UAV navigation in the obstacle prone regions to minimize the power consumption of UAV and thereby increase in flight endurance is achieved.

Conflict of interest

Authors declares that there is no conflict of interest.

Acknowledgements

Authors would like to express sincere thanks to Indian Space Research Organization (ISRO), Department of Space, Govt. of India for providing the funding under ISRO − Respond scheme (ISRO/RES/3/843/19-20) to execute this project and Vel Tech Institute to utilize the available facilities for necessary experimental work.

References

  1. H. Shakhatreh, A.H. Sawalmeh, A. Al-Fuqaha, Z. Dou, E. Almaita, I. Khalil, M. Guizani, Unmanned aerial vehicles (UAVs): A survey on civil applications and key research challenges, IEEE Access 7, 48572–48634 (2019) [Google Scholar]
  2. P. Radoglou-Grammatikis, P. Sarigiannidis, T. Lagkas, I. Moscholios, A compilation of UAV applications for precision agriculture, Comput. Netw. 172, 107148 (2020) [Google Scholar]
  3. S. Park, Y. Choi, Applications of unmanned aerial vehicles in mining from exploration to reclamation: A review, Minerals 10, 663 (2020) [CrossRef] [Google Scholar]
  4. A. Valsan, B. Parvathy, G.H. Vismaya Dev, R.S. Unnikrishnan, P.K. Reddy, A. Vivek, Unmanned aerial vehicle for search and rescue mission, in: 2020 4th International Conference on Trends in Electronics and Informatics (ICOEI)(48184) (IEEE, 2020), pp. 684–687 [CrossRef] [Google Scholar]
  5. A. Sigala, B. Langhals, Applications of Unmanned Aerial Systems (UAS): A delphi study projecting future UAS missions and relevant challenges, Drones 4, 8 (2020) [CrossRef] [Google Scholar]
  6. B. Esakki, S. Mathiyazhagan, M. Moses, K.J. Rao, S. Ganesan, Development of 3D-printed floating Quadrotor for collection of algae in remote water bodies, Comput. Electron. Agric. 164, 104891 (2019) [CrossRef] [Google Scholar]
  7. H. Shin, J. Chae, A performance review of collision-free path planning algorithms, Electronics 9, 316 (2020) [CrossRef] [Google Scholar]
  8. S.K. Debnath, R. Omar, S. Bagchi, E.N. Sabudin, M.H.A.S. Kandar, K. Foysol, T.K. Chakraborty, Different cell decomposition path planning methods for unmanned air vehicles-A review, in: Proceedings of the 11th National Technical Seminar on Unmanned System Technology 2019, Springer, Singapore, 2020, pp. 99–111 [Google Scholar]
  9. D. González, J. Pérez, V. Milanés, F. Nashashibi, A review of motion planning techniques for automated vehicles, IEEE Trans. Intell. Transp. Syst. 17, 1135–1145 (2015) [Google Scholar]
  10. D.D. Zhu, J.Q. Sun, A new algorithm based on Dijkstra for vehicle path planning considering intersection attribute, IEEE Access 9, 19761–19775 (2021) [CrossRef] [Google Scholar]
  11. S. Wu, Y. Du, Y. Zhang, Mobile robot path planning based on a generalized wavefront algorithm, Math. Prob. Eng. 2020 (2020) [MathSciNet] [Google Scholar]
  12. D.R. Thompson, S. Chien, Y. Chao, P. Li, B. Cahill, J. Levin, O. Schofield et al., Spatiotemporal path planning in strong, dynamic, uncertain currents, in: 2010 IEEE International Conference on Robotics and Automation (IEEE, 2010), pp. 4778–4783 [CrossRef] [Google Scholar]
  13. S.H. Tang, C.F. Yeong, E.L.M. Su, Comparison between normal waveform and modified wavefront path planning algorithm for mobile robot, in: Applied Mechanics and Materials, vol. 607, Trans Tech Publications Ltd, 2014, pp. 778–781 [CrossRef] [Google Scholar]
  14. S. Koenig, M. Likhachev, D. Furcy, Lifelong Planning A*, Artif. Intell. 155, 93–146 (2004) [CrossRef] [Google Scholar]
  15. I. Noreen, A. Khan, Z. Habib, Optimal path planning using memory efficient A*, in: Proceedings of the IEEE International Conference on Frontiers of Information Technology, Islamabad, Pakistan, 19–21 December 2016, pp. 142–146 [Google Scholar]
  16. Z. Bu, R.E. Korf, A*+ BFHS: A hybrid heuristic search algorithm, arXiv preprint arXiv:2103.12701 (2021) [Google Scholar]
  17. K. Daniel, A. Nash, S. Koenig, Theta any-angle path planning on grids, J. Artif. Intell. Res. 39, 533–579 (2010) [CrossRef] [Google Scholar]
  18. C. Wu, X. Huang, Y. Luo, S. Leng, F. Wu, An improved sparse hierarchical lazy theta* algorithm for UAV real-time path planning in unknown three-dimensional environment, in: 2020 IEEE 20th International Conference on Communication Technology (ICCT), IEEE, 2020, pp. 673–677 [CrossRef] [Google Scholar]
  19. D. Ferguson, N. Kalra, A. Stentz, Replanning with RRTs, in: Proceedings of the IEEE International Conference on Robotics and Automation, Orlando, FL, USA, 15–19 May 2006 [Google Scholar]
  20. C.W. Warren, Fast path planning using modified A* method, in: Proceedings of the IEEE International Conference on Robotics and Automation, Atlanta, GA, USA, 2–6 May 1993 [Google Scholar]
  21. A. Botea, M. Muller, J. Schaeffer, Near optimal hierarchical path-finding, J. Game Dev. 1, 1–30 (2004) [Google Scholar]
  22. M. Radmanesh, M. Kumar, P.H. Guentert, M. Sarim, Overview of path-planning and obstacle avoidance algorithms for UAVs: A comparative study, Unmanned Syst. 6, 95–118 (2018) [CrossRef] [Google Scholar]

Cite this article as: Balasubramanian Esakki, Gayatri Marreddy, M. Sai Ganesh, E. Elangovan, Simulation and experimental approach for optimal path planning of UAV using A* and MEA* algorithms, Int. J. Simul. Multidisci. Des. Optim. 12, 24 (2021)

All Tables

Table 1

Initial Configuration of MEA*.

In the text
Table 2

Final Configuration of MEA*.

In the text
Table 3

Comparison between A* and MEA* algorithms: Simulation results.

In the text
Table 4

Comparison between A* and MEA* algorithms experimental results.

In the text
Table 5

Comparison of execution time with other algorithms [15].

In the text

All Figures

thumbnail Fig. 1

A* algorithm.
In the text
thumbnail Fig. 2

MEA* algorithm.
In the text
thumbnail Fig. 3

Execution time.
In the text
thumbnail Fig. 4

Total path length travelled.
In the text
thumbnail Fig. 5

Total number of turns.
In the text
thumbnail Fig. 6

UAV path planning using ground control station.
In the text
thumbnail Fig. 7

Optimal path of A* algorithm.
In the text
thumbnail Fig. 8

Optimal path of MEA* algorithm.
In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.