第20卷第4期Vol.20,No.4机器人ROBOT1998年7月July,1998机器人C-空间障碍边界建模与无碰路径规划王伟杨扬原魁(北京科技大学智能及计算机科学研究所100083)马玉林蔡鹤皋(哈尔滨工业大学机器人研究所150001)摘要基于机器人与障碍实体的实际碰撞关系,通过对C-空间障碍的特性分析,定义了临界碰撞关节角,提出了基于临界碰撞关节角的C-空间障碍边界建模方法.该方法计算量小,可直接同机器人动态仿真模型相联,便于系统集成.路径搜索利用改进的A*算法,采用动态变步长并进行目标可见性测试,提高了搜索效率,并利用全局路径优化算法对路径进行了优化.仿真结果表明本文提出的算法对静态结构化环境下机器人操作机的路径规划是切实有效的.关键词C-空间障碍,路径规划,A*算法1引言机器人路径规划要求机器人根据给予的指令及环境信息自主地决定运动路径,避开障碍,实现任务目标.基于不同的机器人结构类型、判别准则、机器人表示和工作空间的描述,有不同的路径规划方法.虽然机器人路径规划方法多种多样,但基本均基于两种规划空间:机器人工作空间(欧氏空间)和C-空间(C-space,ConfigurationSpace)[1].对于大多数工业机器人来说,控制是在关节级进行的,对于工作空间中的规划结果需要通过逆雅克比矩阵从笛卡尔空间向关节空间的转换,这种转换的计算量是很大的.但在C-空间中,机器人手臂的每个位姿可表示为一个点,C-空间中机器人手臂与障碍物发生碰撞位姿的集合构成C-空间障碍.求出C-空间障碍后,路径规划问题就转化为求从初始位姿点到目标位姿点的不与C-空间障碍发生碰撞的路径问题.求机器人操作机C-空间障碍物是比较困难的,C-空间往往被离散并只测试一些离散值[2,3].如何快速有效地计算C-空间障碍和在C-空间内进行路径搜索是实现C-空间路径规划的关键.本文利用机器人与障碍物体的空间关系,充分利用障碍的边界信息,通过在障碍边界上寻求特征点,利用特征点的临界碰撞角,来求解C-空间障碍的上边界和下边界,从而得到C-空间障碍的边界.算法避免了大量繁琐计算,具有较高的计算效率.在将A*算法用于机器人自由空间的路径搜索时,由于搜索空间过大,搜索效率很低且得到的路径是相对栅格优化的.本文在用A*算法进行路径搜索时,采用了动态可变步长,同时进行目标的可见性测试,提高了搜索速度,通过对所得路径进行全局优化,减少了不必要的路径波折.2C-空间障碍边界建模2.1临界碰撞关节角与障碍的特征点1997-11-17收稿第20卷第4期王伟等:机器人C-空间障碍边界建模与无碰路径规划2812DRR臂具有两个自由度,末端点的工作空间形成一个二维流形.C-空间同环面、柱或盘形是拓扑同胚的,这取决于机器人臂的运动学及关节极限.C-空间障碍的边界是由简单封闭曲线构成的,称为C-边界.设障碍在体空间内obs∈B-space,其C-空间障碍为CO(obs).若考虑关节极限,由于将关节极限作为虚拟障碍来处理,因此关节极限在C-空间内的像是C-空间的边界.机器人与障碍物体的碰撞检验算法可归结为两类:离散检验法和扫描体法.无论是离散检验法还是扫描体求交法都归结为障碍物体及机器人运动扫描体之间的干涉碰撞问题.利用这些方法可以计算整个碰撞区域,但对于求解C-空间障碍来说,我们只关心碰撞区域的边界,即一系列的临界碰撞点,而诸多的中间碰撞姿态信息是冗余的.为此,本文作如下定义.定义:设连杆L前面的关节值已定,关节Jk的运动范围为[-P,P],连杆L与点P发生碰撞可有两个关节角:连杆以逆时针转动时与p接触形成的关节角,称为下临界碰撞关节角,以HLC表示;连杆以顺时针转动时与p点接触形成的关节角,称为上临界碰撞关节角,以HUC表示.临界碰撞关节角是指连杆与障碍接触时形成的关节角.图1(a)所示为点P对于连杆L形成的上界临界碰撞角HUC和下界临界碰撞角HLC.在图1(b)中,对于障碍顶点P,HUC是存在的,而HLC实际是不可能发生的.当连杆L与障碍物obs发生碰撞时,有一个碰撞点cp,碰撞点的HLC或HUC就是障碍的C-边界点,或者是C-边界的上边界UCO(obs)中的点,称上界点UP,或者是C-边界之下边界LCO(obs)中的点LP.对于obs只需两个碰撞点就完全可以确定其碰撞区间,计算效率明显提高.(a)上下临界碰撞角(b)有效临界碰撞角图1点的临界碰撞角如果能求得障碍与机器人的碰撞点,则由碰撞点的HLC和HUC可得到C-边界的上界点UP和下界点LP,这是求C-边界的基础.求C-边界首先要确定碰撞点,碰撞点cp∈B-space,本文定义多