Source-linked AI summary
Multi-objective path planning of an autonomous mobile robot using hybrid PSO-MFB optimization algorithm
Fatin H. Ajeil, Ibraheem Kasim Ibraheem, Mouayad A. Sahib, Amjad J. Humaidi
TL;DR
The paper addresses collision-free path planning for autonomous mobile robots in static and dynamic environments, where distance and smoothness must be optimized despite limitations in prior approaches. It proposes a hybrid PSO-MFB planner with local-search feasibility correction and obstacle detection and avoidance, while accounting for robot size through obstacle enlargement. Simulations report competitive path optimality, including a 14.7785 m best path and a 13.6696 m collision-free path in reported scenarios, although the hybrid method requires more computation time than MFB.
Problem
Path planning must produce collision-free routes in static and dynamic environments while optimizing distance and smoothness.
Method
The method combines PSO-MFB path generation, local search for infeasible solutions, and obstacle detection and avoidance, with obstacles enlarged by the robot radius.
Results
14.7785 m was the best reported path with maximum smoothness and shortest distance, while another collision-free path measured 13.6696 m with 4.162 sec computation time.
Takeaways & Limitations
The hybrid PSO-MFB algorithm outperformed the listed optimization techniques in the reported path-comparison results.
Takeaways & Limitations
The hybrid PSO-MFB method required more computation time than MFB despite improving path length.
Abstract
from arXiv · showhide
The main aim of this paper is to solve a path planning problem for an autonomous mobile robot in static and dynamic environments. The problem is solved by determining the collision-free path that satisfies the chosen criteria for shortest distance and path smoothness. The proposed path planning algorithm mimics the real world by adding the actual size of the mobile robot to that of the obstacles and formulating the problem as a moving point in the free-space. The proposed algorithm consists of three modules. The first module forms an optimized path by conducting a hybridized Particle Swarm Optimization-Modified Frequency Bat (PSO-MFB) algorithm that minimizes distance and follows path smoothness criteria. The second module detects any infeasible points generated by the proposed hybrid PSO-MFB Algorithm by a novel Local Search (LS) algorithm integrated with the hybrid PSO-MFB algorithm to be converted into feasible solutions. The third module features obstacle detection and avoidance (ODA), which is triggered when the mobile robot detects obstacles within its sensing region, allowing it to avoid collision with obstacles. The simulation results indicate that this method generates an optimal feasible path even in complex dynamic environments and thus overcomes the shortcomings of conventional approaches such as grid methods. Moreover, compared to recent path planning techniques, simulation results show that the proposed hybrid PSO-MFB algorithm is highly competitive in terms of path optimality.
1. Introduction
Mobile-robot path planning seeks optimized collision-free routes, with static and dynamic environments requiring different planning assumptions. The paper proposes a hybrid PSO-MFB algorithm integrated with feasibility correction and obstacle avoidance.
- 1. Introduction: Path planning creates an optimized collision-free route between two locations and can address static or changing obstacles.Offline methods use complete environmental knowledge, whereas online methods respond to changes detected by local sensors.
- 1. Introduction: Conventional cell decomposition, roadmap, and potential-field methods can be inefficient or inaccurate because of computational cost and local minima.Heuristic methods are presented as suitable for rapidly finding solutions to NP-complete problems.
- 1. Introduction: The proposed planner combines Particle Swarm Optimization and Modified Frequency Bat Algorithms to optimize shortest distance and path smoothness.It also converts infeasible solutions into feasible ones and employs obstacle avoidance as a separate module.
- 1. Introduction: The paper evaluates its methodology through simulation results compared with previous works.The paper structure identifies simulation-based effectiveness comparisons and subsequent discussion of the results.
2. Related Works
Prior work applies swarm, heuristic, neural, fuzzy, and hybrid methods to robot path planning, but important limitations remain. The paper addresses these limitations with a three-module planner combining PSO-MFB, local search, and obstacle avoidance.
- 2. Related Works: Prior studies use swarm, heuristic, neural-network, and fuzzy-logic methods for single- and multi-objective mobile-robot path planning.Examples include ACO, Bat, PSO, Cuckoo Search, Bacterial Foraging, Artificial Immune Systems, WOA, GA, and controller-integrated approaches.
- 2. Related Works: Hybrid methods combine meta-heuristics such as GA-PSO, MOBBPSO, and CS-BA to improve robot path planning.The stated objective is to combine advantages from two meta-heuristic algorithms.
- 2. Related Works: Prior approaches often model the robot as a point, optimize shortest distance without smoothness, or use grids that waste space and reduce dynamic-environment flexibility.Grid cells may reserve an entire cell even when an obstacle occupies only part of it.
- 2. Related Works: The paper contributes a three-module planner with PSO-MFB point generation, local-search feasibility correction, and sensor-triggered obstacle avoidance.The first module optimizes a multi-objective combination of shortest path and path smoothness; the third uses twelve sensors around the robot.
3. Problem Statement and Preliminaries
The paper models path planning as finding a safe, short, and smooth route from a start position to a goal among static or moving obstacles. It represents the physical robot as a point by expanding obstacles and selects intermediate points using weighted distance and smoothness objectives.
- Problem formulation: The planning problem seeks an optimum or near-optimum path from a start position to a goal without collision.The supported objectives include safety, shortness, and smoothness in workspaces containing static and dynamic obstacles.
- Problem formulation: The robot is modeled as a point by expanding each circular obstacle by the mobile robot’s radius.This accounts for the robot’s physical size while simplifying collision checking.
- Performance criteria: Path quality combines shortest distance and path smoothness through a weighted objective whose weights sum to one.Shortest distance minimizes path length, while smoothness minimizes angle differences between successive candidate segments.
- Mid-point selection: At each iteration, candidate mid-points are compared by the balance between shorter distance and smaller angle error.The paper illustrates selecting a point that balances the two criteria rather than always choosing the shortest-distance option.
- Dynamic environments: Dynamic obstacles are modeled with linear or circular motion, updating their positions over successive time steps.Linear motion uses velocity and direction; circular motion uses a center, radius, and angular position.
4. Swarm-based Optimization
The paper introduces swarm intelligence as a nature-inspired optimization approach and reviews PSO and the Modified Frequency Bat algorithm as the optimization foundations. PSO combines individual and swarm experience, while MFB updates bat positions using frequency, velocity, loudness, and pulse-emission mechanisms.
- Swarm intelligence: Swarm intelligence uses simple nature-inspired agents to search for optimization solutions until an optimal solution or stopping condition is reached.These methods are applied across optimization problems and form the conceptual basis for the paper’s swarm-based approach.
- Particle Swarm Optimization: PSO updates particles using attraction toward each particle’s personal best and the swarm’s global best positions.The attractions are scaled by weights and random factors before the next position is computed.
- Modified Frequency Bat: The Modified Frequency Bat algorithm models echolocation and updates artificial bats through frequency, velocity, and position equations.Its frequency schedule changes over iterations to improve global search performance.
- Modified Frequency Bat: MFB also perturbs candidate positions using average loudness and updates loudness and pulse-emission rate during iterations.The loudness decreases while pulse-emission rate increases according to design-parameterized update rules.
5. Proposed Method
The proposed method combines hybrid PSO-MFB optimization, Local Search repair, and sensor-based obstacle detection and avoidance to plan feasible paths for an omnidirectional mobile robot.
- Hybrid PSO-MFB Optimization: Hybrid PSO-MFB combines Particle Swarm Optimization and Modified Frequency Bat algorithms to optimize candidate paths using distance and smoothness.PSO adapts MFB parameters α and γ to balance exploration and exploitation.
- Local Search Feasibility Repair: The Local Search module identifies infeasible candidate points and line segments intersecting obstacles, then updates them into feasible solutions.A point is infeasible when it lies within an obstacle, while a segment is infeasible when it intersects or is tangent to the obstacle.
- Local Search Feasibility Repair: For candidate points inside obstacles, the method computes their distance from the obstacle center and moves them outside the occupied region.The updated coordinates use the obstacle radius, safety distance, candidate angle, and distance between consecutive waypoints.
- Local Search Feasibility Repair: For line segments crossing obstacles, the method substitutes the segment equation into the obstacle-circle equation and classifies feasibility using the discriminant.A negative discriminant indicates no intersection, whereas zero or positive values indicate tangency or intersection and therefore infeasibility.
- Obstacle Detection and Avoidance: Obstacle Detection and Avoidance uses twelve equally spaced sensors, each covering 30°, with a sensing range set to 0.8 m.Obstacles are expanded by the robot radius so the robot can be treated as a point, and the sensing vector records occupied angular regions.
- Obstacle Detection and Avoidance: The avoidance module converts occupied sensor regions into a gap vector and selects the available gap yielding the shortest movement toward the goal.The sensing vector is derived from obstacles within the sensing range and their angular coverage relative to the robot.
6. Simulation Results
Simulations evaluated the proposed algorithm in static and dynamic environments and against prior path-planning methods. The hybrid PSO-MFB produced collision-free paths and the shortest reported paths in the comparison cases.
- Experimental design: The experiments covered static and dynamic environments, comparison studies, and ten algorithm executions using MATLAB.The static and dynamic cases used different obstacle configurations and robot settings.
- Static environment: 14.7785 m was the best path in the static environment, with maximum smoothness and shortest distance, obtained in 3.48 minutes.The environment contained five static obstacles, with start point (0, 0), goal point (10, 10), and robot radius 0.5 m.
- Dynamic environment: 13.6696 m was the best collision-free path in the dynamic environment, obtained with a computation time of 4.162 seconds.The robot changed its path after detecting obstacles within its sensing region and then continued toward the goal.
- Comparison with prior methods: 14.3255 m was obtained by Hybrid PSO-MFB, compared with 14.3625 m using DABC, 14.3371 m using MAABC, 14.5095 m using GA, and 14.3802 m using BC.The comparison used an environment with four static obstacles; GA and BC results were scaled for comparison.
- Comparison with prior methods: The Hybrid PSO-MFB algorithm outperformed the listed optimization techniques in the comparison studies in terms of shortest distance.The first comparison also reports that its mean, minimum, and maximum fitness values verify the best path result.
- Comparison with prior methods: 14.6384 m was obtained by Hybrid PSO-MFB, compared with 14.7422 m using DABC, 14.7163 m using MAABC, and 14.8821 m using ABC.This second comparison used an environment with six static obstacles, and the ABC result was scaled by 10.
7. Discussion
The discussion attributes improved path length to PSO particles invoking complete MFB procedures with dynamic parameters, while acknowledging increased computation time. It also notes that safety considerations can limit further path improvement.
- Performance and trade-offs: Dynamic MFB parameters increase adaptation and help Hybrid PSO-MFB find better solutions than MFB alone.Each PSO particle calls a complete MFB algorithm with dynamic α and γ parameters, adapting to loudness and pulse-emission rates.
- Performance and trade-offs: Hybrid PSO-MFB requires more computation time than MFB, although the discussion identifies faster hardware as a possible remedy.The discussion links this cost to the hybrid algorithm's performance advantage.
- Safety constraint: Further improvement over existing path-planning methods may be constrained by mobile-robot safety when the robot approaches obstacles too closely.The discussion frames safety as a consideration in evaluating additional path improvement.
8. Conclusions
The paper concludes that Hybrid PSO-MFB combined with Local Search and obstacle detection and avoidance provides feasible path planning in static and dynamic environments. It reports efficacy in avoiding obstacles and identifies real-platform and more cluttered dynamic testing as future work.
- Proposed contribution: The proposed method integrates Hybrid PSO-MFB swarm optimization with Local Search and obstacle detection and avoidance strategies.The robot size is incorporated by enlarging obstacles in free space.
- Evaluation and conclusion: The algorithm was tested in static and dynamic environments to minimize path length and minimum angles.The conclusion reports obstacle avoidance in both environment types.
- Future work: Future work includes hardware implementation on a real omnidirectional mobile platform and testing in intricate cluttered dynamic environments with moving targets.These directions are stated as possible extensions of the simulation-based study.