Some Algorithm Studies On Ground Mobile Robot Motion Planning And Motion Coordination

Motion planning and motion coordination can be regarded as a part of fundament and key problems in autonomous mobile robot and Multi-Robot Systems(MRS).In real world application,a robot has limited range of communication and sensing,environmental information is unknown or incomplete.Thus it is the main body of this paper to study some problems of ground mobile robot motion planning and MRS motion coordination in unknown or incomplete environment with limited range of communication and sensing,it is the objective to build an integrated frame from individual ability of motion planning to group ability of motion coordination.We aim at indoor environment,work in three aspects below from the point of view of motion planning and motion coordination:(1)Coverage planning is one of basic problem in environmental modeling.It is an important content of exploring unknown environment to design rational motion strategies for coverage of unknown environment ASAR(2)In incomplete environmental information,an algorithm is needed to rapidly replan.The algorithm must exploit the trait of environmental model,replan motion according to the change of environment.(3)Under the basis of individual robot motion planning,it is studied to coordinate motion of MRS.The more detail of researches and results are shown below:(1)In coverage planning of unknown environment,sliding algorithm is improved to incremental style,then it is combined with some strategies of circumnavigation and randomly walk etc.Our MRS can explore obstacle information and incrementally build C-space at the same time.In this way,we not only detect obstacle boundary information, but also get state space which is independent of robot shape.Compared with classical sliding algorithm,incremental sliding algorithm make configuration space incrementally from local area and can beused in MRS,it is much more efficient.(2)An improved GVD(Generalized Voronoi Digram)algorithm based on approximate Voronoi Digram is designed.The GVD algorithm uses a VDC(Van Der Corput)sample sequence,VDC can regulates the precision of GVD easier,its computational performance is also improved by contrast with simple sample sequence,besides it has nice uniformity.(3)A dynamical A~* algorithm in geometric model-GD~* Lite is introduced to get over poor efficiency of brute-force replanning.In this algorithm,a Morse function is proposed to detect critical point,then D~* Lite uses it for fast planning with incomplete environmental information. (4)A bazaar market is established based on market theory,it can be used on allocation of tasks or resources.Robots negotiate through highest-price open-cry auction,when contradiction appears,a robot can continue to bid with higher price which could be drawn from potential profit of alternative resources.(5)A local motion coordination method is designed based on game theory.The motion coordination is carefully formalized to be a game playing process in which every robot locally makes decision with assistance of communication,moreover the idea of GD~* Lite is used to expand nodes.These approaches make MRS plan coordinated motion fastly under frame of classical game theory.