蔡莉莎，曾维鹏，吴恒玉

（海南软件职业技术学院海南琼海571400）



基于SAT的路径规划系统的设计

蔡莉莎，曾维鹏，吴恒玉

（海南软件职业技术学院海南琼海571400）

摘要：本文主要介绍了基于SAT路径规划算法以及路径规划系统的设计方案。通过移动机器人抓取积木为例，介绍了基于SAT路径规划算法包括的规划问题的命题表示方法以及如何使用SAT求解器对规划命题进行求解。该系统较传统的路径规划系统而言，路径规划解提取速度较快，无需传感器的反复检测初始状态及目标状态，规划效率较高。

关键词：可满足算法；路径规划系统；MjnjSAT求解器；控制器

随着人工智能技术的发展，在很多恶略环境下，人们使用移动机器人取代人类完成一些难度高、危险系数大的任务。然而移动机器人是否能顺利完成任务取决于其是否能顺利抵达目的地，因此移动机器人自身需要具有路径规划的功能。

传统的机器人路径规划方法都是使用单片机作为核心器件，机器人上配备的传感器对周围环境的探测，通过实时处理传感器反馈的信息求得机器人运动的路径点，从而快速寻求一条安全的运动轨线判断并自动躲避障碍物顺利抵达目的地［1］。传统方法的缺点是在行走的过程中会出现走“弯路”的现象，搜索效率低。

由于SAT求解技术在知识表达以及计算速度等方面具有明显优势，因此基于SAT的规划方法被使用在移动机器人的路径规划系统上［2］。

1　算法的相关知识

定义1（可满足性问题）判定一个公式是否存在一组变量使其逻辑命题为真，如果存在说明该逻辑命题为可满足。……