Research On Multi-Robots Path Planning Based On Evolutionary Game Theory

Path planning technology is significant research direction of artificialintelligence field. Its purpose of research is to plan the path from start point todestination point based on a certain evaluation criterion without collision.Traditional methods running global searching based on greedy algorithm cansolve individual robot path planning problem. As industrializationdevelopment, multi-robots path planning problem has become a hot researchspot, which not only solving the path planning problem but also cooperativeproblem among robots. According to allocating path source cooperativelyamong robots, the global utility can be most. For one thing, modernintelligence algorithms such as artificial neural network, genetic algorithmand evolution strategy have been used to solve multi-robots path planningproblem more and more, which anticipating to allocate source among robotsadaptively according to direct simulation of natural process. For another,rising game theory provides firm math theory for multi-robots path planningproblem to allocate path source adaptively from global aspect.The evolutionary game algorithm is constructed by economic gametheory and evolutionary strategy. The proposed approach sets up relevantmappings between the search space and objective function of optimizationproblem and the strategy profile space and utility function of non-cooperativegame respectively, and achieves the optimization objective through thedynamic evolutionary game process of adaptive agents.To begin with, we present defination and procedure of some involvedpath planning technologies such as model of visibility graph, geneticalgorithm and evolution strategy. Then we introduce the process of formationand development of game theory and evolutionary game theory andapplications on some intelligence problems included path planning problem.We in detail describe how to build relationship between evolutionary game theory and multi-robots path planning based on model of visibility graph. Wepropose a multi-robots path planning model under evolutionary game theorywith frame of multi-robots cooperative problem. According to introduceRT(relay time) and set utility on time dimension, breaking definition thateffective factors of traditional research just path sources, we can acquire moreoptimal solution in practical environment.We certify results using computer simulation and results imply that thismethod can not only solve cooperative path planning problem but alsoprovide possible of more optimal solution. The last, we analysis someunaccomplished works and propose some suggestions to multi-robots pathplanning under antagonistic environment. The contributions of this work are:(1) It disclose profound relationships between evolutionary game theoryand path planning problem and avoid absolute ration problem in applicationsof traditional game theory and define multi-robots path planning evolutionarygame model under frame of cooperation.(2) According to Visual Graph, we describe workspace and definefunction. Introducing RT(delay time) and setting utility function on timedimension, breaking definition that effective factors of traditional researchjust path sources, we can acquire more optimal solution in practicalenvironment.