动态规划

动态规划

第27卷第5期

南　京　理　工　大　学　学　报Vol.27No.52003年10月Journal of N anjing U niversity of Science and T echnology Oct.2003

基于动态规划思想的多机器人路径规划

Ξ

唐振民ΞΞ　赵春霞　杨静宇　张　进

(南京理工大学计算机科学与技术系,南京210094)摘要　该文围绕着一个机器人巡逻街道小区的仿真环境,讨论了多机器人路径规划中的路由优化问题。在解决这些问题的过程中,充分考虑到多机器人系统的动态特征,将运筹学中动态规划的思想和Dijkstra 算法及其相关图论知识引入到机器人的路径规划求解中,不仅降低了问题的复杂度,并且得到了问题的解决方案。关键词　机器人,路径规划,动态规划

分类号　TP 391.9学科代码　520.60

多机器人协作是近期的研究热点,其中一个应用领域是多机器人的路径规划,该问题是移动机器人导航与控制的基础[1]。Buck 指出了多机器人路径规划个例性[2],并以机器人足球赛为例给出了一种适合于协作的方法;Bennewitz [3]给出基于爬山法的路径规划寻优策略;Cai [4]运用遗传算法原理给出了一种基于定长十进编码方法的多个移动机器人路径规划问题。本文以一个机器人巡逻街道小区的仿真系统为例,运用动态规划方法解决多机器人路径规划中的路由优化问题,并给出相关实现算法。

1　问题的描述

本文设计如下的仿真系统:即以多个移动机器人为控制对象,以一个街道小区为试验环境,要求这些移动机器人负责各自管辖区的街道巡逻工作,而且每个机器人要有不同层次的合作能力,具体描述如下。

设有由k 个机器人组成的团队负责M 行N 列个街区的巡逻工作,要求:

(1)每个机器人负责一片街区m i ×n j ,其中m i ∈[0,M ),n i ∈[0,N );

(2)每个机器人的辖区与相邻辖区有部分边界重叠;

(3)任意时刻,一条街道上同时只可以有一个机器人行进或静止;

(4)当某个机器人检查到某条街道出现故障时,必须通知其他机器人绕道行驶;

(5)每一条街道的巡逻次数大致相同,并且重复路径最少;

Ξ

ΞΞ唐振民(1961—

),男,1978年3月就读哈尔滨船舶工程学院,教授,博士生导师。主要研究方向:智能机器人,图像处理。E 2mail :Tang.zm @mail.njust.edu.cn

收稿日期:2003-05-08　　Ξ

　国防科工委基础研究项目

第1页下一页