凸优化与A^*算法结合的路径避障算法

Convex optimization and A-star algorithm combined path planning and obstacle avoidance algorithm

为提高足式移动机器人的避障能力和路径规划效率,提出一种凸优化与A^*算法结合的路径避障算法.首先,基于半定规划的迭代区域膨胀方法IRI-SDP(iterative regional inflation by semi-definite programming),通过交替使用两种凸优化算法快速计算出地面环境中无障碍凸多边形及其最大面积内切椭圆,用于移动机器人的局部避障和任务动作规划;然后,结合经典的A*算法,建立机器人局部和世界坐标系、机器人质心轨迹转换模型、碰撞模型和启发式代价函数,在全局环境中寻找最优成本最小的路径;最后,通过仿真实验验证该算法的有效性.

To improve the obstacle avoidance ability and path planning efficiency of mobile legged robots,a convex optimization and A-star algorithm combined path planning and obstacle avoidance algorithm is proposed.Firstly,a method of iterative regional inflation by semi-definite programming(IRI-SDP)is presented to quickly compute out a large convex polygon of obstacle-free and its largest inscribed ellipse in the given ground environment through alternating two convex optimizations.The obstacle-free region is utilized for obstacle avoidance and task motion planning locally.Then,combining with the classical A-star algorithm via establishing the local and world coordinate system of mobile robots,the transfer model of the mass center of mobile robots,the impact model and the heuristics cost function,the optimal minimum-cost path in the global environment can be found.Finally,simulation results validate the effectiveness of proposed method.