1. Introduction

Path planning is a cornerstone in the vast realm of mobile robotics. It's the very essence that dictates how robots, unaided by human interference, decide the course they should take to reach their destination efficiently and safely. Historically rooted in computational geometry and algorithmic theory, the domain of path planning has grown exponentially, reflecting the complexities and challenges introduced by real-world scenarios. The significance of path planning in mobile robotics cannot be understated. As the world becomes increasingly automated, robots are assigned critical roles, be it in healthcare, manufacturing, transportation, and even defense [1]. Ensuring these machines navigate their environments without causing disruptions or posing threats is paramount. At its core, path planning is not just about reaching point B from point A; it's about doing so while considering dynamic obstacles, minimizing energy consumption, and adhering to the physical and computational constraints of the robot [1].

Moreover, the realm of path planning has a broader significance than just navigation. It bridges the gap between theoretical computer science and tangible, real-world applications. Concepts studied abstractly in algorithm design and analysis are brought to life when a robot successfully navigates a maze, avoids moving obstacles, or plans a route in an unknown environment [2]. Looking ahead to the structure of this review, this article aims to embark on a journey arranged in chronological order. Starting from the historical roots of path planning, this review runs through traditional technologies and marks an important milestone in technological development. The narrative will gradually transition to modern methods and emphasize the impact of artificial intelligence on path-planning technology. Finally, this article delves into the current challenges and focuses on areas that still require urgent research, ultimately looking forward to the future of robot path planning [3].

This paper is structured to provide readers with a comprehensive understanding, irrespective of their familiarity with the domain. Whether it is for an experienced robotics expert, a student who has just entered this field, or a curious person who is eager to understand robots, this review is of great significance in revealing the development history and prospects of path planning for mobile robots.

2. Historical context of path planning in mobile robotics

The annals of mobile robotics are dotted with pivotal moments, and central to many of these has been the perpetual quest to conquer the intricacies of path planning. As robots transitioned from mere static machines to dynamic entities capable of movement, navigating an environment emerged as a paramount challenge.

2.1. Initial challenges and motivations

In the dawn of mobile robotics during the mid-20th century, the idea of a machine navigating autonomously in a space teeming with obstacles was nothing short of revolutionary. Robots were primarily restricted to controlled environments, like factories, where their movements were predictable and repetitive. The outside world, with its dynamic and often unpredictable nature, posed several challenges. The initial motivations for path planning were multi-faceted. On one hand, there was a surge in industrial demand for robots that could function outside the constraints of fixed environments. These robots could be employed in warehousing, transport, and even rudimentary search and rescue operations [4]. On the other hand, fuelled by the space race and the Cold War, there was a push from the defense and space sectors, aiming to deploy robots in unfamiliar terrains – be it the rugged landscapes of distant planets or reconnaissance missions in hostile territories [5].

2.2. Early strategies and their limitations

The first forays into path planning were largely deterministic. One of the foundational approaches was the grid-based method. Environments were discretized into grids, and robots would compute paths based on these predefined cells. While straightforward, this method was computationally expensive, especially for larger environments, and lacked finesse. Robots often moved in noticeably rigid patterns, unable to smoothly navigate curves or nuanced terrains [6]. The potential field method was another seminal technique. Here, robots were guided by virtual forces. Obstacles exerted repulsive forces, and goals exerted attractive ones. Conceptually elegant, this approach mimicked natural phenomena. However, in practice, robots often find themselves trapped in local minima, especially in complex environments with multiple obstacles. They would get "stuck" in places where the repulsive forces from obstacles and the attractive forces from the goal balanced out [7].

Visibility graphs and Voronoi diagrams also rose to prominence as tools for path planning. While visibility graphs connected all obstacle vertices to find the shortest path, Voronoi diagrams aimed to keep the robot as far away from obstacles as possible by navigating along the midpoints between obstacles. These methods were sound in theory, but they too had their limitations. Constructing such graphs was computationally intensive, and for dynamic environments where obstacles could move or change, these methods struggled to keep up in real time [8].

3. Traditional path planning techniques in mobile robotics

The evolution of path planning in mobile robotics has taken a dramatic turn over the years. Old methods were characterized by essentially simple and physically intuitive ‘straight-line’ geometric solutions, which formed part of the springboard from which subsequent significant developments evolved; although they also entailed a separate set of serious drawbacks. This paper provides an overview of some of the basic methods.

3.1. Grid-based methods

The most intuitive but earliest way of approaching path planning is the grid-based solution. The environment was represented as grids, with each cell denoting a potential position that the robot might occupy. The size of the robot and environment configuration defined several classes of cells: occupied, free, or partially occupied [9]. This simple approach helps plan through established algorithms like A* or Dijkstra, which search for the shortest path from the start to the final goal. However, since slightly increasing granularity in grids captured more detail, computational cost blew up fast. It did not handle real-world problems representative of an un-uniformly discretized environment smoothly—leading to sub-optimal plans [10].

3.2. Visibility graphs

Visibility graphs are rooted in computational geometry. Here, nodes are created for the start and goal positions and every vertex of each obstacle. A direct line, or edge, is then drawn between every pair of nodes if they're "visible" to each other, meaning the line doesn't cross any obstacle [11]. Once the graph is constructed, algorithms like Dijkstra's can find the shortest path. While this method guarantees optimality, constructing the visibility graph can be computationally intense, especially in environments crowded with obstacles.

3.3. Voronoi diagrams

Voronoi diagrams work on a distinct principle: for every point in free space, find the closest obstacle. The diagrams split the environment into regions, where every point within a region is closer to its associated obstacle than any other [12]. Robots then navigate along the edges of these regions, ensuring they stay maximally distant from obstacles. While this ensures safety, especially in environments where obstacle proximity can be hazardous, the paths might not always be the most direct or shortest. Moreover, constructing Voronoi diagrams, especially in higher dimensions, can be computationally demanding.

3.4. Potential fields

Potential fields were conceived as a reactive path-planning method based on drawing inspiration from electromagnetic fields. The robot is treated as a particle under the influence of virtual forces. An attractive force originating from the goal is pulling it towards the ill, while obstacles try to repel the robot and push it away [13]. Navigating through potential fields is like rolling down a hill; the robot moves by following a gradient of combined attractive and repulsive fields. However, one great challenge occurs in the form of local minima – places where equal pull comes simultaneously from all directions but gets “stuck”. These locations become more than pitfalls for robots navigating solely upon potential fields, especially when working in complex terrains [13].

4. Transition to modern path planning algorithms

The slow-moving transition from deterministic techniques to more flexible and adaptive ones is what characterizes the development of path-planning methods in robotics. At the earlier core of this transition, acceptance of the use of probabilistic methods that exemplify how mathematical veracity can be combined with the capability for handling uncertainty and complexity in real-world surroundings comes into play.

Probabilistic methods, unlike their deterministic predecessors that just look for a single optimal path based on a static model of the environment, try to model uncertainty and dynamics by imagining lots of possible futures and looking at them individually in addition to considering probabilities [14]. Robots are empowered to make decisions even with incomplete or corrupted data using the Probabilistic Roadmap (PRM), which constructs a roadmap of feasible paths and quickly checks it against an action plan. This technique is efficient in high-dimensional spaces and adaptable for many purposes, including wireless automation. The PRM led to the development of the Rapidly-exploring Random Trees technique (RRT) [15,16]. As it suggests, RRT rapidly expands trees into unexplored regions within a state space, ensuring thorough exploration while maintaining computational efficiency. Particularly good at handling non-linear dynamics and differential constraints, it finally came about being used for incremental search methods, which were quite an advancement, precisely D-Lite*, which marks a very important one. Built upon the traditional A* algorithm, D*-Lite stands out in its ability to deal with environmental changes by updating the shortest path incrementally, making it perfect for robots scouring dynamic terrains [17].

5. Influence of AI on path planning

Artificial intelligence (AI) catapulted the evolution of path planning considerably faster in mobile robotics. As practical as they are on more straightforward, smaller types of tasks, Trivial algorithms needed to be revised with expanding robotic applications and complex changing environments. The entry point is machine learning techniques incorporated from AI apparatuses that endowed robots with human-like learning abilities and adaptabilities.

5.1. Path optimization via Machine Learning and Neural Networks

Deep learning, in particular, Machine Learning (ML), has by and large left its mark on the path planning domain as well. Neural networks exploit their function approximation capabilities to model manifold complexities of a real-world environment [18]. Convolutional Neural Networks (CNNs) can process environmental data that are usually restricted for image processing tasks which they identify as obstacles and suitable paths or ruts. By learning over plenty of environmental samples though, these nets can predict safe routes even in unknown terrains [19].

Recurrent neural networks, especially with long-short term memory (LSTM) network-based versions of them, therefore remember sequences and consequently make them suitable for time-series data. Utilized in path planning, they have been adopted to predict as well as account for the movement trajectories of dynamic obstacles [20]. This is especially useful where other entities may be moving through the environment, such as cars or pedestrians. On the downside, using deep neural networks has a high computational cost, rendering on-robot real-time operations few and far between.

5.2. Reinforcement Learning and its applications in path planning

Reinforcement Learning (RL) gives a different perspective where an agent learns by interacting with its environment and receives feedback in the form of rewards or penalties depending on actions taken [21]. In a path-planning context, a robot learns through exploration, making decisions at each step. It obtains rewards from the latest experiments upon successful completion to decide about future activities on acquiring knowledge, if feasible or not. For example, reaching a destination quickly could be considered a high reward, whereas collision with any obstacle will lead to a penalty. Moreover, such methods as Proximal Policy Optimization (PPO) and others are introduced wherein not only does 'the robot find out the right act to do in every situation', but indeed not necessarily having written his long-term value [22]. RL thus shows promise and has worked wonders in simulations along with some specific applications though equally there persist difficulties. Such training can be time-consuming, and ensuring that the learned policies generalize well to all possible real-world scenarios remains an ongoing endeavor in research.

6. Hybrid and integrated approaches in path planning

The realm of mobile robotics has persistently sought to optimize path planning by ingeniously amalgamating traditional methodologies with the power and adaptability of contemporary AI-driven approaches. These hybrid techniques aim to leverage the robustness and predictability of traditional algorithms while benefiting from the flexibility and adaptability of modern AI techniques.

6.1. Combining traditional and modern techniques for enhanced efficiency

Traditional path planning techniques, like grid-based methods or Voronoi diagrams, provide deterministic results, ensuring that, given the same environment and parameters, the outcome will remain consistent. Such predictability can be essential in many applications [19]. On the other hand, AI-based techniques, especially those rooted in machine learning, offer adaptability, allowing robots to cope with dynamic and uncertain environments better. A classic example of such integration is using neural networks as heuristic functions in A* or Dijkstra's algorithms. While the traditional search algorithms chart the path, the neural networks, trained on vast environmental data, provide the heuristic, improving the efficiency of the search process [23]. Another strategy involves employing Convolutional Neural Networks (CNNs) to process environmental data, extracting features that inform traditional algorithms, like potential fields, of the environment's nuances. This allows for a more adaptive reaction to complex terrains or dynamic obstacles [24].

6.2. Multi-objective path planning

Path planning is not always about the shortest path. Sometimes, robots might have multiple objectives to consider, like minimizing energy consumption, avoiding threat zones, or maximizing data collection [25]. Such scenarios demand multi-objective optimization. Traditionally, techniques like the Pareto front were used, where multiple objectives were weighed, and a set of non-dominated solutions were presented. However, these solutions, in large-dimensional spaces, can be computationally expensive. AI-driven multi-objective optimization, particularly using evolutionary algorithms, has provided a fresh avenue. For instance, algorithms like the Non-dominated Sorting Genetic Algorithm II (NSGA-II) employ genetic algorithm principles to find a set of optimal paths considering multiple objectives simultaneously [26]. Furthermore, integrating reinforcement learning with multi-objective criteria has shown potential. Here, the agent receives feedback based on multiple objectives, refining its policy to strike a balance among them.

7. Complex environment navigation in mobile robotics

Navigating intricate environments represents a critical challenge in mobile robotics. As robots find increased applications in myriad domains, from urban landscapes to remote terrains, their path-planning algorithms are continually tested by the dynamism and unpredictability of these environments present. These challenges only amplify when multiple robots are introduced, necessitating inter-robot coordination.

7.1. Path planning in dynamic and uncertain environments

Historically, many path-planning algorithms assumed a static environment. However, real-world applications frequently involve changing scenarios – moving pedestrians, vehicles, or other obstacles [27]. One prominent solution is the Probabilistic RoadMap (PRM) method, which creates a roadmap of an environment by randomly sampling collision-free paths. When dynamic elements are introduced, a temporal aspect is included to adjust the roadmap, making it adaptable to changing circumstances. Another approach is the Dynamic Window Approach (DWA), tailored for robots with velocity constraints. It combines local trajectory optimization and obstacle avoidance by considering the robot's dynamics and only searching in the reachable velocity space [28].

7.2. Multi-robot path planning and coordination

Introducing multiple robots into the equation complicates the planning process. It's no longer just about the optimal path; it's about ensuring paths don't collide, tasks are distributed effectively, and there's a consensus among the robots. Decentralized planning strategies, where each robot plans for itself while considering others, have been a go-to solution. Techniques like rapidly Rapidly-exploring Random Trees (RRT) can be extended for multi-robot systems, where each tree represents a robot's path and the algorithm ensures these paths remain collision-free [29]. Centralized methods, though computationally more intensive, provide a holistic solution by considering the entire robot team as a single entity and planning paths for all robots simultaneously.

7.3. Addressing Real-world Challenges: Crowd Navigation and Variable Terrains

Two pertinent challenges in complex environment navigation are navigating through crowds and handling variable terrains.

7.3.1. Crowd Navigation. Moving in environments with pedestrians or crowds requires robots to be not just efficient but also socially compliant. The robot needs to anticipate human movement, which often involves understanding subtle social cues and norms. Techniques that combine Deep Reinforcement Learning with traditional motion prediction models have shown promise, allowing robots to both predict pedestrian trajectories and adapt their paths accordingly [30].

7.3.2. Variable Terrains. Whether it's the rugged landscape of a mining site or the shifting sands of a desert, robots need algorithms that can adjust to the ground beneath them. Hybrid algorithms, combining the traditional grid-based methods with learning-based approaches, help map these terrains in real time and adjust paths based on the robot's stability and environmental constraints [25].

8. Current limitations and challenges in path planning

Even with the substantial advancements in path planning for mobile robotics, there persist significant challenges and limitations that need to be addressed for a truly holistic and universally applicable solution. Recognizing these limitations is pivotal for directing future research and ensuring mobile robots are reliable and effective in diverse environments.

8.1. Unsolved problems in path planning

8.1.1. Dynamic environments with unpredictable obstacles. While some algorithms can adapt to environments with moving obstacles, predicting the unpredictable – such as sudden, erratic movements – remains a significant challenge [22].

8.1.2. Scalability issues. As the complexity of an environment increases, so does the computational cost of path planning. Algorithms that work efficiently in simple terrains might become computationally prohibitive in more intricate scenarios [25].

8.1.3. Long-Term path planning. While many algorithms excel at short-term obstacle avoidance, determining the best long-term path in a changing environment remains a complex problem [6].

8.2. Real-world implementation barriers

8.2.1. Sensor limitations. Path planning heavily relies on the robot's sensors. However, sensors can sometimes provide noisy or incomplete data, affecting the robot's perception of its environment [4].

8.2.2. Processing constraints. Onboard processing capabilities can limit the complexity of the algorithms that can be run in real-time. This balance between computational efficiency and optimality is often a significant constraint [1].

8.2.3. Physical limitations of robots. Path planning algorithms can compute a path, but the physical robot needs to execute it. Issues like slippage, mechanical failures, or energy constraints can affect the execution [11].

8.3. Potential pitfalls in Over-relying on AI-driven methods

8.3.1. Loss of determinism. Traditional algorithms have a deterministic nature, meaning given the same inputs, they produce the same outputs. AI-driven methods, especially those based on neural networks, can sometimes produce varied results under identical conditions, leading to unpredictability [26].

8.3.2. Overfitting. Machine learning models might perform exceptionally well in known environments (where they were trained) but could fail in unseen scenarios. This over-specialization can lead to unreliable robot behavior in unfamiliar terrains [26].

8.3.3. Transparency and understandability. AI-driven methods are often seen as black boxes. If a robot makes an error, determining the cause can be challenging with complex neural networks [24].

8.3.4. Training data constraints. Effective machine learning models require vast amounts of training data. However, acquiring comprehensive and diverse datasets for all possible real-world scenarios is daunting, if not impossible [26].

9. Conclusion

As people move through the pages of robotics, path planning is a testimony to human ingenuity and an unrelenting desire for perfection. From rudimental algorithms charting simple terrains to sophisticated AI-driven approaches navigating the convoluted labyrinths that are our dynamic world, path planning has undergone a miracle like no prior systemic engineering endeavor. The historical progression of path planning mirrors more broadly on technological innovation in general. Initial strategies with their deterministic nature attempted to solve this problem within rigid mathematical frameworks. Reaping better solutions than systems without boundaries often stumbled at unpredictability and complexity. This resulted in the integration of AI, a transformative force that brought life to robotic agents for their ability to learn, adjust themselves, and decide just like sentient beings. However, as the promises spread above our heads by AI spread farther apart from us bodies and minds start bothering us simultaneously; its immediate emergence spelt new issues reminding us of the intricate relation existing between innovation and complexity.

Emerging technologies like quantum computing propagate a future brimming with possibilities. They not only promise to enhance computational prowess but also rethink the fundamental paradigms that underpin path planning. But new challenges will arise with every leap forward, be it regarding the ethical implications of ultra-intelligent robots or of implementing bleeding-edge technologies on the fly and balancing its risks against benefits. This cyclical nature of progress and challenge invokes an imperative for continuous research and innovation, as robots integrate deeper into our societal fabric. In flawless navigation, there is increasing demand for seamless cooperation between human beings and robotic agents acting on their behalf in hospitals, factories, homes, and streets alike: this ability to navigate seamlessly becomes an indispensable prerequisite in many contexts.

Our journey is not just about improving technology. It is about pushing boundaries and creating, which reflects humanity's spirit. Standing at the edge of an exciting future, we realize that the road to perfection is continuous and driven by successes and challenges. It is critical to remember that as we evolve with path-planning technology, the endgame is just as important as the steps we take to get there.