Optimization of Route Planning for Dynamic Environments using Swarm Intelligence

Abstract

Environments for algorithms can be categorized as static or dynamic. A static environment remains stationary throughout the execution of the algorithm, while in a dynamic environment the environment changes during the execution of the algorithm. The algorithms for planning in static and dynamic environments can be divided into offline and online algorithms. This research implements an online algorithm for an unknown environment and combined exploration and planning in a hybrid architecture. A simulated system of agents based on swarm intelligence is presented for route optimization and exploration. Two versions of the system are implemented and compared for performance- i.e., a simulated ant agent system and a simulated niche based particle swarm optimization. A simulated ant agent system is presented to address the issues involved during route planning in dynamic and unknown environments cluttered with obstacles and objects. A simulated ant agent system (SAAS) is proposed using a modified ant colony optimization algorithm for dealing with online route planning. The SAAS generates and optimizes routes in complex and large environments with constraints. The traditional route optimization techniques focus on good solutions only and do not exploit the solution space completely. The SAAS is shown to be an efficient technique for providing safe, short, and feasible routes under dynamic constraints, and its efficiency has been tested in a mine field simulation with different environment configurations. It is capable of tracking a stationary as well as a non-stationary goal and performs equally well as compared to moving target search algorithm. Route planning for dynamic environment is further extended by using another optimization technique for generation of multiple routes. Simulated niche based particle swarm has been used for dynamic online route planning, optimization of the routes, and it has proved to be an effective technique. It efficiently deals with route planning in dynamic and unknown environments cluttered with obstacles and objects. A simulated niche based particle swarm optimization (SN-PSO) is proposed using a modified particle swarm optimization algorithm for dealing with online route planning. The SN-PSO generates and optimizes multiple routes in complex and large environments with constraints. The SN-PSO is shown to be an efficient technique for providing safe, short,and feasible routes under dynamic constraints. The efficiency of the SN-PSO is tested in a mine field simulation with different environment configuration, and it successfully generates multiple feasible routes. Finally, the swarm based techniques are further compared with an evolutionary algorithm (genetic algorithm) for performance and scalability. Statistical results showed that evolutionary techniques perform well in less cluttered environments and their performance degrades with the increase in environment complexity. For small size maps, the evolutionary technique performs well but its efficiency decreases with an increase in map size.