仿人机器人碰撞检测算法研究

国防科学技术大学硕士学位论文仿人机器人碰撞检测算法研究姓名：刘鹏鹏申请学位级别：硕士专业：控制科学与工程指导教师：马宏绪2010-11国防科学技术大学研究生院硕士学位论文第i页摘要在仿人机器人领域，随着稳定行走控制技术的进步，基于传感器的全身运动模式越来越受到关注。与传统的离线规划步态和姿态的方式相比，基于传感器的在线运动规划的机器人动作灵活得多，这就带来了自碰撞检测的问题。昀原始昀简单的碰撞检测算法是一种蛮力计算的方法，即对两个几何模型中的所有基本几何元素进行两两相交测试，这种2()On次的相交测试无法满足仿人机器人实时性的要求。本文以实验室第五代仿人机器人“KDW-5”为研究对象，从仿人机器人在线运动规划中自碰撞检测的需求出发，具体分析了基于层次包围盒树的碰撞检测算法，提出了基于改进的OBB层次包围盒树的碰撞检测算法，并通过实验验证了其实时性和有效性，设计和实现了仿人机器人在线规划中的自碰撞检测系统，并通过实验验证了其有效性。首先，详细分析了仿人机器人运动学的相关理论知识，并以此为指导，以“KDW-5”的机械系统结构为基础，应用D-H参考坐标系的方法建立其运动学模型，并将VisualC++和OpenGL相结合，搭建了“KDW-5”的仿真平台，为“KDW-5”的自碰撞检测系统的设计与可行性验证提供了计算基础和仿真环境。其次，围绕仿人机器人在线运动规划中自碰撞检测的需求，对基于层次包围盒树的碰撞检测算法进行了研究。一方面从包围盒的构造、紧密性和相交测试三个方面分析了三种常见的层次包围盒，另一方面从层次包围盒树的构造、碰撞检测和树的更新三个方面详细研究了层次包围盒树算法，为后续基于改进的OBB层次包围盒树的碰撞检测算法的提出提供了理论基础。本文的重点是围绕保证仿人机器人在线运动规划中的自碰撞检测的精确性和实时性的中心，提出了基于改进的OBB层次包围盒树的碰撞检测算法。首先，详细分析了OBB的定义和计算方法；接着，应用昀优化和惩罚函数的方法，将昀小化子节点的体积和、昀小化较大的子节点的体积、昀长边原则的三种昀优化函数和惩罚函数这四种启发式函数应用于OBB层次包围二叉树的构造过程，一方面加速了二叉树的构造速度，更为重要的是，使二叉树的结构优化从而能够更好的满足减少碰撞检测时间的要求；提出了两种碰撞检测的加速策略，提高了基于OBB的层次包围盒树的碰撞检测算法的实时性；根据仿人机器人运动具有频繁性、空间关联性和局部性的特点，提出了层次包围树更新的三种加速策略；接着，通过三种测试场景，验证了基于改进的OBB层次包围盒树的碰撞检测算法的实时性。该算法是仿人机器人自碰撞检测系统设计和实现的核心和基础。国防科学技术大学研究生院硕士学位论文第ii页接着，对仿人机器人自碰撞检测系统进行了设计和分析。首先，分析了仿人机器人控制系统的框架，对其中几个主要组成部分进行了介绍和分析，阐述了自碰撞检测模块在仿人机器人控制系统中的地位和作用。重点分析和设计了相交检测模块，并简要的介绍了碰撞响应模块。接着，结合第二章构建的“KDW-5”仿真平台，以本文提出的基于改进的OBB层次包围盒树的碰撞检测算法为基础，验证了自碰撞检测系统的有效性。昀后，总结本文所做工作，分析不足之处，并提出今后的研究重点。主题词：仿人机器人在线运动规划自碰撞检测精确性实时性D-H坐标系VisualC++OpenGL“KDW-5”仿真平台最优化方法惩罚函数启发式函数二叉树加速策略改进的OBB层次包围树的碰撞检测算法自碰撞检测系统国防科学技术大学研究生院硕士学位论文第iii页ABSTRACTRecently,duetothedevelopmentofstablewalkingcontroltechnologyinthefieldofhumanoidrobot,basedonwholebodysensorsmotionmethodisbecomingtheactivestudyinghot.Comparedwiththeoff-lineplanningmethod,humanoidrobotbasedonwholebodysensorsmotionmethodhasmoreflexiblemotions,whichbringsabouttheproblemofselfcollisiondetection.However,thetraditionalcollidedetectionmethodisaprimitivecomputing,whichmakethegeometryprimitivesamongthetwogeometryobjectstwo-twooverlaptest.Thismethodcan’tsatisfythereal-timeofhumanoidrobotwiththeon-linemotionplanning.Inthisdissertation,withtherequirementoftheselfcollisiondetectionamongtheon-linemotionplanningofthe“KDW-5”inlaboratoryandthebasisofitsmechanicalconfiguration,themethodbasedonboundingvolumehierarchiesindetailsisanalyzed.CollidedetectionmethodofenhancedOBBboundingvolumehierarchiesisproposed.Thepreciseandreal-timeofthisenhancedmethodisvalidatedwithexperiments.Thesystemoftheselfcollidedetectionofhumanoidrobotisdesignedandcompleted,anditsfeasibilityisvalidatedwithexperiments.Firstly,relatedkinematictheoriesareanalizedandthemechanicalconfigurationofthe“KDW-5”isintroduced.Basedthemforwardkinematicmodelofthe“KDW-5”usingD-Hcoordinatesisbuilt.Ahumanoidsimulationplatformwhichisusedtovalidatethefeasibilityandprovideasimulationplatformandthecomputingenvironmentoftheselfcollisiondetectionsystemof“KDW-5”isconstructedbasedVisualC++,OpenGLandtheforwardkinematicmodel.Secondly,withtherequirementoftheselfcollisiondetectionamongtheon-linemotionplanningofthe“KDW-5”,thecollisiondetectionalgorithmsbasedontheboundingvolumehierarchiesareanalizedindetailed.Foronething,thetypesoftheboundingvolumeareintroduced.Foranotherthing,fromthreeaspectsoftheconstruction,overlaptestandtheupdatingofboundingvolumehierarchies,thecollisiondetectionalgorithmsbasedontheboundingvolumehierarchiesareanalizedindetailed,whichisthebasisofthefollowingenhancedalgorithm.Thirdly,theemphasisofthedissertationisthat,withthecentreofthetherequirementoftheselfcollisiondetectionamongtheon-linemotionplanningofthe“KDW-5”,proposingthealgorithmofenhancedOBBboundingvolumehierarchies.Atthebeginning,thedefinitionandcomputingmethodoftheOBBareintroduced.Usingtheoptimazitionmethod,punitivefunctionandheuristicfunction,allyingthefourheuristicfunctiongofMinChildenVolumeSum,MinBiggerChildVolumeandMaxLongestSide,constructthebinarytreeoftheenhancedOBBboundingvolume国防科学技术大学研究生院硕士学位论文第iv页hierarchies,whichoptimizethestructureofthebinarytreeand,moreimportantly,savethecomputetimeofthecollisiondetection.Withtwoaccelerationstrategies,thereal-timeofthealgorithmofOBBboundingvolumehierarchiesisimproved.Basedonthecharacterswhicharehighfrequency,spacecoherenceandlocalityofthelawofmotionofthehumanoidrobot,threeaccelerationstrategiesoftheupdatingoftheenhancedalgorithmofOBBboundingvolumehierarchiesareproposed.Withthreetestingenvironmentsoftheexperiment,theefficiencyoftheenhancedalgorithmofOBBboundingvolumehierarchiesisvalidatedwhichisthebasisandcoreofthesystemofselfcollisiondetectionof“KDW-5”.Fourthly，designandaccomplishthesystemofselfcollisiondetectionof“KDW-5”.Atthebeginning,thestructureofthecontrolsystemofthe“KDW-5”anditsmainpartsareintroduced.Theimplicationandimportanceofthemoduleofthecollisiondetectionareanalized.Theoverlaptestingmoduleandcollisionresponsemodulearedesignindetails.Usingthesimulationplatformof“KDW-5”,basedontheenhancedalgorithmofOBBboundingvolumehierarchies,thefeasibilityofthesystemofselfcollisiondetectionisvalidated.Finally,themaincontentofthisdissertationissummarizedandkeypointsoffutureresearcharedi