多目标追逐问题的一种混合整数线性规划解

研究多车辆多目标追逐的路径规划问题。提出两个基于混合整数线性规划(Mixed integer linear programming,MILP)的多目标追逐(Multi-target pursuit,MTP)模型:就近追逐和"一对一"使能追逐。在两个MIP追逐模型中,小车运动的状态方程考虑为具有线性阻尼的质点动力学方程。采用整数变量描述小车与障碍物的相对位置信息,提出"目标膨胀尺寸"的概念来描述对目标的追逐,定义小车的"追逐方向"。采用选取整变量的等高面法求解MILP追逐问题,并给出初始内点整变量的确定方法。最后给出仿真试验1对两个多目标追逐模型进行对比研究,仿真试验2证实了算法的效率。

The path planning for multi-target pursuit(MTP)is studied.Two MTP models,the nearest target pursuit and one-vehicle-one-target enable pursuit,based on the mixed integer linear programming(MILP)are presented.In the two MTP models, the dynamic equation of mass point with linear damping is taken as the state equation of vehicle motion.Integer variables are used to describe the relative position of vehicle and obstacle.Target expansion size is proposed to describe the pursuit process for target. Pursuit direction of vehicle is defined.The isometric plane method selecting integer variables is used to solve MILP pursuit problem. How to select the integer variables in initial inner point is also given.Finally,simulation experiment 1 is given to make comparisons between two MTP models and simulation experiment 2 to show the efficiency of the method.

国家高技术研究发展计划(863计划，2006AA04z206)资助项目。