Study On Multiple Mobile Robots Coordinated Planning Algorithms

Multi-robot system with coordinated control can accomplish tasks that unable or difficult to be completed with one single robot, such as searching in a dangerous environment, transportation of relief supplies, or pursuit of targets, and so on. Path planning, formation planning, holes detection and repair for regional coverage, and detection and coverage of events happened in the region are vital problems for multi-robot systems.Aiming at the above key problems, this paper proposes a series of algorithms. The content mainly includes the following four aspects.(1) Poly-clonal artificial immune network algorithm is proposed for mobile robots path planningIn an unknown complex dynamic environment, path planning based on the environmental information obtained by sensors is one of the most fundamental functions for mobile robots to carry out tasks. In a dynamic environment, it is difficult to obtain the motion equations of moving obstacles and moving goals, and to establish the mathematical model of an unknown environment. The most challenge of dynamic path planning is how to plan a safe path based on the real-time sensing of locations of obstacles and goals.Poly-clonal artificial immune network algorithm is proposed for mobile robot path planning in an unknown environment with static obstacles. Environmental information obtained by sensors is defined as antigen, and possible movement directions of a robot are defined as antibodies. According to the biological immune mechanism and the interaction between antigen and antibody, the optimal steering direction is computed and selected. Poly-clonal algorithm increases the diversity of antibodies and solves the problem of immature convergence. Moreover, the proposed algorithm effectively solves the problem of local minima caused by artificial potential field. Poly-clonal artificial immune network algorithm successfully avoids static obstacles and reaches the goal with the optimal path. Simulation and discussions validate the effectiveness of the proposed algorithm, and the comparison with other existing algorithm shows the superiority of the proposed algorithm.Improved poly-clonal artificial immune network algorithm with memory units is proposed for multi-robot dynamic path planning with moving obstacles and moving goals. The interaction model between antigen and antibody is redefined with taking other robots, moving obstacles and moving goals into account. Moreover, memory units are used for preserving the environmental information which robot encounters and preserving the antibody in a specific situation. The proposed algorithm selects the optimal steering direction based on the real-time locations of moving obstacles and moving goals. Memory ability increases the probability of a specific antibody is selected, and reduces the response time for dynamic path planning. Simulation and discussions validate the effectiveness of the proposed algorithm, and the comparison with other existing algorithm shows the superiority of the proposed algorithm.(2) Poly-clonal artificial immune network algorithm is proposed for multi-robot formation planningMulti-robot formation planning has many advantages:it can obtain environmental information sufficiently, it can enhance the ability of resisting invasion, and it can improve the efficiency of completing tasks. Based on the environmental information obtained by sensors, how to establish and keep the adaptive formation and switch between different formations with obstacles avoidance is the main difficulty for multi-robot formation planning.A novel multi-robot dynamic formation planning algorithm in an unknown environment with static obstacles is proposed. The desired formation is computed based on the desired separation and desired angle between the leader robot and follower robot. Improved poly-clonal artificial immune network algorithm realizes formation establishing and formation keeping with obstacles avoidance for multi-robot formation planning. Control graph theory is used for the smooth exchange between two isomorphic formation shapes. Formation-change and leader-change are used to avoid obstacles and realize dynamic formation planning. Simulation and discussions validate the effectiveness of the proposed algorithm.In order to solve the problems of obstacles avoidance, formation establishing and formation keeping, we consider from different views and adopt different methods to calculate the steering direction and the linear velocity of the follower robot. Steering direction of the follower robot is calculated with poly-clonal artificial immune network algorithm. The optimal steering direction quickly tracks the steering direction of leader robot, and successfully avoids obstacles. Linear velocity of the follower robot is calculated with position tracking control method without the constraints of angular velocity and the initial orientation. It guarantees that the position errors of follower robot quickly converge to zeros. Lyapunov theory is used to prove the stability of multi-robot formation system. Several Matlab simulations and MobileSim experiments validate the effectiveness of the proposed algorithm, and the comparison with other existing algorithm shows the superiority of the proposed algorithm.(3) A sub-Voronoi cell area algorithm is proposed for coverage holes detection and repair in mobile sensor networksRegional coverage in the mobile sensor networks has been widely used in practical applications:cleaning in indoor and outdoor, mine clearance, searching for the emergency scene, sowing in the farmland, and so on. Mobile robot can be regarded as a mobile node in the mobile sensor networks. Algorithm used for regional coverage of a mobile node can be used for regional coverage of a mobile robot. Coverage holes in regional coverage may affect the overall performance of networks, such as decreasing the data reliability, changing the global topology of the network, and destroying the communication links. In mobile sensor networks with a limited number of mobile nodes, it is one of the key issues that how to detect and repair coverage holes, improve the coverage ratio and coverage efficiency and improve the performance of mobile sensor networks.In order to cover the region, a novel sub-Voronoi cell area based coverage holes detection and repair algorithm is proposed for mobile sensor networks. Each Voronoi cell is divided into the same number with its Voronoi edges based on the node and any two adjacent Voronoi vertices. The area of a hole in a sub-Voronoi cell is computed based on the geometric relationship between the sub-Voronoi cell and its sensing disk. A mobile node moves toward an optimal location inside a sub-Voronoi cell with the maximum area of a hole. The proposed algorithm can estimate locations of coverage holes. Moreover, it can accurately calculate the holes area in each sub-Voronoi cell, and repair coverage holes with maximizing the coverage efficiency and coverage ratio. Simulation results validate the effectiveness of the proposed algorithm and its superiority to other algorithms.(4) Dynamic k-coverage planning for multiple events with mobile robots is proposedVarious events may occur in the monitoring region. Movement with the minimum energy for regional coverage, events detection and events coverage is a challenge for the coverage of multiple mobile robots.Dynamic k-coverage problem for multiple events with mobile robots is solved. Two sub-problems are divided for multiple events coverage, namely mobile robots uniform deployment and nodes selection. Firstly, sparse mobile robots randomly deploy in the environment, and mobile robots need to deploy uniformly in order to effectively communicate with static nodes and extremely cover the entire region. Weight-sub-Voronoi-half-gravity method and weight-sub-Voronoi-half-incenter method are presented for uniform deployment of mobile robots. Secondly, analog game theoretic algorithm is used for the selection of k mobile robots which cover an event. The analog game theoretic algorithm depends on the remaining energy, movement energy, and communication energy of mobile nodes. The proposed algorithm guarantees mobile robots deploying with a higher coverage ratio, and achieves k-coverage of each event with less energy consumption. Simulation and discussions validate the effectiveness of the proposed algorithm, and the comparison with other existing algorithm shows the superiority of the proposed algorithm.