基于区域空间知识模型的在线快速路径规划  

Online fast path-planning based on regionalized spatial knowledge model

作　　者：仲朝亮[1] 刘士荣[1,2] 张波涛[2] 

机构地区：[1]华东理工大学自动化研究所,上海200237 [2]杭州电子科技大学电气自动化研究所,浙江杭州310018

出　　处：《控制理论与应用》2015年第3期357-365,共9页Control Theory & Applications

基　　金：国家自然科学基金项目(61175093;61375104);浙江省自然科学基金项目(LQ14F030012)资助~~

摘　　要：人类在其导航过程中运用了区域化的空间知识模型并采取了"由精到粗"的寻路策略.受此启发本文首先提出一种区域化的空间知识模型.在该模型中,多个小尺度的区域组合在一起形成上一层级的区域,构成一种层次化的空间表示结构.在此基础上提出一种基于该空间知识模型的在线路径规划算法FTC–A*(fine-to-coarse A*).FTC–A*能够根据环境信息的远近采取不同的规划策略.在机器人所在的区域中,进行路径的精细规划,而对远处空间进行粗糙规划.该策略利用环境描述的区域化特性,降低了搜索空间的大小,从而显著地降低了规划时间和内存负载,减少了机器人的运动响应延迟.本算法能适应环境规模巨大以及目标点经常改变的应用场合.通过在Mobile Sim平台的仿真实验以及与A*和HA*算法的对比分析,验证了该方法的可行性与有效性.Human beings use the regionalized spatial knowledge and adopt the ＂fine-to-coarse＂ way-finding strategy in / the process of navigation. Inspired by this, we put forward a regionalized spatial knowledge model. In this model, small scale regions are grouped together to form the bigger regions at the next hierarchy level which leads to a hierarchical spatial representation structure. Based on the spatial knowledge model, we develop a kind of online route-planning algorithm FTC- A＊（fine-to-coarse A＊） which can take different planning strategies according to the distance of environmental information. In the area where the robot stays, a fine route-planning will be conducted while for the distant space a coarse planning will be done. Taking advantage of regionalization feature of environment description, this strategy can shrink the search space; thus, remarkably reducing the planning time and the memory loading as well as lowering the motion response lags of the robot. The algorithm FTC-A＊ can be applied to occasions with huge number of environments or target-points change frequently Through the simulation experiment on MobileSim platform and the contrastive analysis of algorithms A＊ and HA＊, we find the proposed method is feasible and effective.

关 键 词：导航 由精到粗的寻路策略 区域空间知识模型 路径规划 

分 类 号：TP242[自动化与计算机技术—检测技术与自动化装置]