Study On Minimum Constraint Problem And Its Algorithm Based On Mobile Obstacle Environment

Robot path planning is an important basic problem in robot navigation technology.It has made a lot of research achievements,many studies point to how to avoid obstacles and through the global or local optimization method to search the shortest path without obstruction at present.But in reality robot work scenario,it's hard to find path without obstacles blocking.At the same time,robot doesn't have to avoid obstacles or can remove obstacles(mobile)in some cases.The two actual situations,triggered a new robot path planning research thinking,Minimum constraint removal(MCR)problem is proposed in this background.MCR problem is that a robot in the current environment can't find the barrier-free path,and try to find contain minimum geometric constraint path for robots.The sense of the MCR problem is that even if the robot must be through the path contains the constraints,also as far as possible make the path contains the least constraints.Once you find such path,whether it is removed or mobile obstacles in path or through obstacles area will have higher efficiency.At home and abroad research focuses on the mathematical modeling and complexity of MCR problem analysis.In this paper MCR problem is studied from three aspects,including the MCR computational complexity analysis,solving MCR problem based on improved ant colony optimization algorithm,study of MCR multi-objective optimization.Innovative research mainly includes:(1)The existing methods that prove MCR NP hard problem are SET-COVER method and Horn clauses satisfiability method.The graph used in the SET-COVER method is generally non planar,and the graph obtained by vertex intersection is generally not connected,and the solution of the SET-COVER method can not be easily converted into the solution of the MCR problem.In Horn clauses satisfiability method,convex polygon minimum constraint problem is converted into a discrete MCR,which the constraints of the removal based on graph,but from the transformation of diagram and the disorder has very strict restrictions,prove process is very complicated.This paper analysis similarity of the structure of MCR and SAT problems,using the extremely simple combination structure of SAT problem,the SAT problem polynomial time reduction to the MCR problem,and then gives a new method proof the discrete MCR problem is NP,the mathematical method and the proof process is more simple and intuitive(2)The existing methods for solving the discrete MCR problem are mainly the exact search algorithm and the greedy search algorithm,but exact algorithm is not suitable for large-scale problem solving,greed may not be able to get the optimal solution.This paper introduces ant colony optimization algorithm for solving discrete MCR.First proposed an ant colony optimization algorithm to solve the discrete MCR,inspire the function and pheromone update strategy were improved,so that it is no longer easy to fall into local extremum.Simulation experimental results show that the algorithm is better than that of exact search and greedy algorithm in the solution quality and convergence rate,it provides reference for using a variety of intelligent heuristic algorithm to solve the problem of discrete MCR.Secondly puts forward an ant colony optimization algorithm based on the social force model,and the social force model in physical mechanics was in the design of algorithm,The acceleration of the social force model,the heuristic function,the global and local pheromone update strategy,the classification of the population and the selection of the target vertices are redesigned.The simulation experimental results show that the algorithm is better than exact search,greedy algorithm and the ACO algorithm in solution quality and run time.(3)At present,most of the researches have focused on the single objective of finding the minimum obstacle constraint set in MCR,which has isolated the complicated relationship in the path planning of robot.But the complex environment of MCR is actually a multi-objective problem.Based on this problem,multi-objective optimization for MCR was studied in this paper.First multi-objective model of MCR problem is constructed.Then according to the particularity of multi-objective MCR,the improvement of traditional NSGA-II corresponding specialized processing,such as distribution of keeping strategy,elite strategy,and the label set of fusion MCR model construct the fitness function of the algorithm.Compared with the SACO and Greedy algorithm,the experimental results show that the INSGA-II algorithm under the same obstacles number of scenario is more suitable for solving the problem of MCR,and provides an alternative solution for MCR problem researchers or decision makers.Compared with the traditional algorithm of MOEA and NSGA,the experiment results show that INSGA-II run time faster,the running time of INSGA-II is faster,the search space is vast,and number of quantity,distribution of solutions is good.(4)In order to validate the feasibility and effectiveness of the above algorithm in the application of the real scenario and simulation environment,this paper introduced two groups of simulation experiment based on Gazebo simulation platform and two groups of real environment experiment based on Baxter robot.Effective verify the improved ant colony optimization algorithm(SACO),and the improved multi-objective optimization algorithm(INSGA-II)feasibility and validity in solving the problem of MCR,provides a beneficial exploration in the actual MCR problem application.Gazebo simulation platform of two MCR simulation experiment and real application environment based on Baxter robot two MCR application experiment.The feasibility and effectiveness of the improved ant colony optimization(SACO)algorithm and the improved multi-objective optimization(INSGA-II)algorithm in solving the MCR problem are proved to be useful for the practical application of MCR.