Research On Robots Area Coverage Algorithm In Unknown Environments

The definition of robots area coverage in unknown environments is that mobile robots use their sensors to cover the target environment in their sensing range without any recognition of executive coverage task environment. The optimized goal is to make the cover time shorter, repeated path less and non-ergodic region smaller. Robots area coverage is encountered in many real world applications such as military survey, resource search, etc.We create formalized model about robots area coverage by using the grid map of the environment representation, this model sets the robots’visual range and coverage according to the relative location between robots and the obstacles in the environment. On the basis of the model, we carry out the research on covering algorithm.It is difficult for robots to obtain the exact mathematical model of the environments due to the lack of awareness for the surroundings that the robots work in. As a consequence, we propose a Q-Learning coverage algorithm (QLCA) in this paper. As a kind of reinforcement learning, the idea of Q-learning is used in QLCA:in order to get the best strategy, the agents make use of the feedback signal to adjust and improve their behavior through the interaction with the environment. The subsequent action choices and path plans of the robots are directed by the Qtable gained from the robots’self-learning of the QLCA with good coverage result. Compared with the random selection coverage algorithm (RSCA), the QLCA has obvious optimization in four aspects:①the coverage executing steps,②redundancy,③success rates,④shaking times of action choices. The results also states that learning plays an important role in adapting to a unknown environments and making the right decisions for robots.Normally, the workload of area coverage is heavy. For multi-robots, it is a great advantage to perform tasks together in efficiency and robustness. If there is no effective coordination mechanism between robots, simple superposition inevitably cause some redundancy, cannot achieve perfect effect. The robots choose action without coordinating with others in QLCA, therefore the performance still has much space to improve, then the Q-Learning Coordination Coverage Algorithm (QCCA) is proposed which based on QLCA with coordination progress: use Max-sum Algorithm, firstly, compute the coordination sets for a robot and build the factor graph that comprising variable nodes and function nodes, and each variable and function node is allocated to a robot in this set, then both variable and function nodes perform computation for updating messages, after several iterative calculation it will converge to the joint optimal solution. A reasonable and sound cooperation mechanism is the key to give full play to the advantages for multi-robots. The simulation experiments show that the various evaluation of coverage improved greatly compared with QLCA, and prove QCCA’s effectiveness in solving the problem of robot area coverage in unknown environment.This paper makes research on the area coverage algorithm in unknown environment, and proposes the Q-Learning and the coordination coverage algorithm which greatly enhance efficiency of the cover, and provides a certain theoretical and practical value for the future study on this problem.