Research On The Application Of Particle Swarm Optimization In Map Construction

Multi-Robot Based Map-Construction has been considered a acceptable solution to the problem of map-construction, because of its adaptability, safety, accuracy and reliability. In this solution, the coordination among nodes and the assignment of tasks is the key point that determines the efficiency. Considering is problem of large-scale swarm coordination, parallel and multi-agents will be the key to that problem. The existing coordination algorithms in large-scale swarms are all assignment allocation based, with the typical allocation algorithms of Market-Based, Threshold Based, Behavior Based and etc. These algorithms resolve the problem from some sub-problems and allocate them in a centralization way, basing on the hiberarchy of nodes. This will bring the extra communication cost for instruction delivery, as well as the efficiency decrease because of the increase of computation cost brought by increased nodes'numbers. Therefore, we need to find out a new coordination algorithm with a better distribution and scalability.This paper proposes a map-construction algorithm basing on Particle Swarm Optimization (PSO) model to solve the problem above. PSO is a classical Swarm Intelligence (SI) algorithm and emphases the coordination among particles, which achieves the search to the solution space in a distributed way. In our research, we change the problem of exploring unknown area into the problem of searching for optimized solution in solution space, by which we realize the map-construction of the unknown area. The particles in PSO are completely distributed and homogeneous and only need to calculate its own movement path, which requires no extra computation cost when particle number rises. To solve the problem of communication cost, a Virtual Pheromone (VP) model is introduced in our algorithm to realize the interaction among nodes. The model uses small-scale broadcast, which has no routing calculation and can reduce the communication cost. With the PSO model and VP model, we can realize a better scalability in map-construction.The main work of this paper includes:(1) Reviewing the research status of Map-Construction and PSO, and giving the theoretical analysis of feasibility.(2) Proposing a map-construction algorithm basing on PSO model, including Two-Phases Research Path Decision Scheme and Virtual Pheromone based Interaction Scheme. Algorithm Statement is given, with its theoretical analysis, as well as the algorithm realization in pseudo code.(3) Realizing the algorithm on our self-developed simulation platform, and carrying out a series of simulation on the efficiency, scalability and parameter impactions, as well as a detailed analysis on the simulation results.In our PSO Based Map-Construction algorithm, all nodes coordinate in a self-organized way and calculate their search path in a distributed way, which ensures the map-construction of unknown area can be finished in a finite time, as well as a splendid scalability. This algorithm is completely suitable for the application of Multi-Robot Based Map-Construction.