Path Planning for Robot Navigation

Abstract

This paper focuses on finding the best path for a mobile robot to follow, especially when it\'s sent to remote or rough areas. Often, we can use aerial images—taken by satellites or drones—to plan a rough route for the robot. These images are analyzed and divided into different terrain types based on how bright or dark the areas appear. Each type of terrain is given a \"cost,\" which could represent things like energy use or the risk of an accident. These costs are put into a map called a “cost map,” where each spot on the map has a number showing how hard it is for the robot to travel there. This map is then used with the A* algorithm—a popular method for finding the shortest and safest path. The A* algorithm uses this cost map to figure out the most efficient route for the robot. The result is shown as a path drawn over the aerial image, and this process is tested with different image resolutions and sample sizes. The goal of this work is to improve path planning, even when there\'s uncertainty, to ensure smooth and safe travel for the robot.While higher-resolution images give more accurate results, they also take much more time and computing power to process. It also includes a practicality involvement of SLAM Algorithm for the classification of different terrains of Grass, Road, or objects. It is used in a dynamic environment. All these algorithms are used here to get trace the optimal path to the Goal state, so that the robot can be able to map out the path in which it has to traverse safely without any obstruction.

Introduction

I. Introduction

• Robotics aims to design autonomous systems capable of navigating complex environments.

• Path planning is crucial and challenging, especially in unknown, outdoor, or hostile terrains.

• Robots often rely on aerial images (from drones or satellites), which can be noisy and hard to interpret.

II. Purpose

• To develop an optimal, obstruction-free path planning method.

• The robot must:

  • Recognize terrain types (roads, grass, obstacles)

  • Avoid risks

  • Choose the safest and shortest path

• Uses A algorithm* for optimal routing and SLAM for real-time localization and mapping.

III. Key Algorithms

1. A Algorithm*

• Uses:

  • g(n): cost from start to current point

  • h(n): estimated cost from current to goal

  • f(n) = g(n) + h(n) to choose the best path.

• Works on a cost map built from aerial image classification.

2. SLAM (Simultaneous Localization and Mapping)

• Builds a map and localizes the robot simultaneously.

• Ideal for unfamiliar or dynamic environments.

• Uses LiDAR, cameras, and other sensors for mapping.

• Does not require preloaded maps.

3. Gaussian Process Bayesian Classifier

• Classifies terrain from image pixels into:

  • Roads (low cost)

  • Grass (medium cost)

  • Obstacles (infinite cost)

• Trained on sample pixels using Bayesian inference.

• Creates a cost map for path planning with A*.

IV. Navigation Strategy

• Input: Aerial image

• Process:

  1. Classify terrain via Gaussian classifier

  2. Generate a cost map

  3. Use A* to plan path

• Two-step planning:

  • Global planning: Rough path via GPS and map

  • Local planning: Avoids immediate obstacles in real time

V. Performance & Optimization

• Resolution trade-off:

  • Higher resolution → more accuracy, slower computation

  • Solved using bilinear interpolation to balance speed and detail.

• Increased training samples improve classification accuracy but also increase processing time.

VI. Results

• Tested on ~50 aerial images (e.g., airport site).

• Terrain classes:

  • Roads = cost 1

  • Grass = cost 10

  • Obstacles = ∞

• Figures illustrate how:

  • Gaussian classifier traces accurate paths (e.g., Figure 6–8)

  • SLAM classifies terrain (Figures 9–10)

  • A* overlays the optimal route (red/blue lines)

• As image resolution increases, A execution time* rises, showing a trade-off.

Conclusion

In this paper, we developed a method to create a detailed map (called a costmap) using aerial images, which helps in planning paths for robots. First, we used a machine learning model (the Gaussian Process classifier) to classify different types of terrain in the image, such as roads, grass, or obstacles. Based on this classification, we created a costmap where each type of terrain has a different movement cost. For better accuracy, we found that using more sample data improved the quality of classification, and therefore, the costmap. We then used the A* pathfinding algorithm to find the best path for the robot by treating each part of the map as a node with a specific cost. The algorithm found the most efficient route across the map based on these costs. We then used another algorithm in this path planning method SLAM Algorithm which helps to get an optimal map classification and path tracing ahead. Looking ahead, we plan to improve this approach by including uncertainty in the cost values — essentially creating a costmap that shows not just a single cost, but a range of possible costs for each area. This probabilistic approach will be more realistic but also more complex, since standard A* algorithms aren’t designed to handle probabilities. We also aim to build a larger dataset of different terrain types to automate classification and reduce the need for manual labelling. Lastly, we plan to test this system with real robots to verify its performance in practical scenarios.

References

[1] Kavraki, L.E., Siesta, P., Latombe, J.C., Overmars, M.H. Probabilistic roadmaps for path planning in high- dimensional configuration spaces. IEEE Deals on Robotics and robotization 12( 4), 566 – 589 [2] Tiwari, R., Shukla, A., Kala, R. Intelligent Planning for Mobile Robotics Algorithmic Approaches. IGI Global Publishers, Hershey [3] Xia, G.S., Yang, W., Delon, J., Gousseau, Y., Sun, H., Maitre, H. Structural high resolution satellite image indexing. In Proceedings of 2010 ISPRS, TC Vii Symposium, Part A 100 Times ISPRS- Advancing Remote seeing Science, Vienna, Austria [4] Izraelevitz, D., Carlotto, M. Extracting road networks from low resolution upstanding imagery. In Proceedings of the SPIE Visual Communication and Image Processing Conference, Cambridge, MA\\ [5] Kambhampati, S., Davis, L. Multi resolution path planning for mobile robots. IEEE Journal of Robotics and automation 2( 3), 135 – 145 [6] Yang, W. High- resolution Satellite Scene Dataset. Signal Processing and Modern Communication Lab, Wuhan University. [7] Kala, R., Warwick, K.: Planning Autonomous Vehicles in the Absence of Speed Lanes using an Elastic Strip. IEEE Transactions on Intelligent Transportation Systems 14(4), 1743–1752 [8] Sofman, B., Bagnell, J.A.D., Stentz, A.T., Vandapel, N.: Terrainclassification from aerial data to support ground vehicle navigation. Technical Report No. CMU RI-TR 05-39, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA (2006) [9] O’Callaghan, S., Ramos, F.T., Durant-Whyte, H.: Contextual occupancy maps using Gaussian processes. In: Proceedings of the 2009 IEEE International Conference on Robotics and Automation, Kobe, Japan, pp. 1054–1060 (2009) [10] Bazi, Y., Melgani, F.: Gaussian Process Approach to Remote Sensing Image Classification. IEEE Transactions on Geoscience and Remote Sensing 48(1), 186–197 (2010) [11] Dai, D., Yang, W.: Satellite Image Classification via Two-layer Sparse Coding with Biased Image Representation. IEEE Geoscience and Remote Sensing Letters 8(1), 173–176 (2011) \\ [12] Xia, G.S., Yang, W., Delon, J., Gousseau, Y., Sun, H., Maitre, H.: Structural high resolution satellite image indexing. In: Proceedings of 2010 ISPRS, TC VII Symposium, Part A: 100 Years ISPRS - Advancing Remote Sensing Science, Vienna, Austria [13] Yang, W.: High-resolution Satellite Scene Dataset. Signal Processing and Modern Communication Lab, Wuhan University. http://dsp.whu.edu.cn/cn/staff/yw/HRSscene.html (accessed September 18, 2014)

Copyright

Copyright © 2025 Aditi Shrivastava. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.