机器人路径规划是机器人导航技术中的一个重要基础问题,已取得了很多研究成果,目前大多数研究都指向如何躲避障碍物,并通过全局或者局部优化寻找无障碍物的最短路径。但是,在机器人的现实工作场景中,有时很难找到无障碍物阻挡的情况,同时,有些情况下可以移除或移动障碍物而不一定非要躲避障碍物。这两个实际情况,引发了机器人路径规划研究领域新的思考,最小约束去除（Minimum Constraint Removal,MCR）问题就是在此背景下所提出。最小约束去除（MCR）问题针对的是机器人在当前环境下无法找到无障碍路径的情况下,试图去寻找含有最小几何约束的路径为机器人所使用。MCR问题的意义在于,即便机器人必须要通过含有约束的路径,也要尽可能使路径中含有的约束最少,一旦找到这样的路径,无论是移除或移动路径中的障碍物还是穿越障碍区域,都将具有更高的效率。目前国内外的研究主要集中在MCR问题的数学建模及复杂性分析上。本文从三个方面针对MCR问题进行了研究,包括MCR问题计算复杂性分析,基于改进蚁群优化算法的MCR问题求解,MCR问题的多目标优化。创新性研究成果主要有:（1）现有证明离散MCR问题NP难的方法有集合覆盖方法,Horn子句可满足性方法。但是集合覆盖证明方法中用的图一般都是非平面的,通过顶点交集导出的图一般不连接,并且集合覆盖方法的解决方案不能轻易转换成MCR问题的解决方案。Horn子句可满足性方法将凸多边形最小约束去除问题转换为离散的、基于图的约束去除问题,但从该变换获得的图和障碍有着非常严格的限制,证明过程非常复杂。本文深人分析MCR问题与SAT问题结构的相似性,利用SAT问题极其简单的组合结构,将SAT问题多项式时间归约到MCR问题,进而给出了证明离散MCR问题NP难的一种新方法,该证明方法的数学形式与证明过程上更为简单直观。（2）现有求解离散MCR问题方法主要为精确搜索（Exact）算法与贪婪搜索（Greed）算法,但是Exact算法不适合大规模的问题求解,Greed不一定能够得到最优解。本文引入蚁群优化算法求解离散MCR。首先提出蚁群优化算法来求解离散MCR问题,求解过程中对启发函数的设置,信息素更新策略进行了改进,使其不再易于陷入局部极值。实验结果表明,算法在解的质量和收敛速度上优于Exact算法与Greed算法,为采用各种智能启发算法求解离散MCR问题提供了借鉴。其次提出一种基于社会力模型的蚁群优化算法（SACO）,算法设计中借鉴物理力学中的社会力模型,重新设计了基于社会力模型的加速度,启发函数,全局与局部信息素相结合更新策略,种群分类与目标顶点选择等步骤,使算法更适合MCR问题的求解。SACO算法在解的质量、收敛速度及运行时间上均优于Exact算法、Greed算法及ACO算法。（3）目前对MCR问题研究大多集中在需找最小障碍物约束集这个单目标上,孤立了机器人路径规划过程中的错综复杂关系,但是复杂环境下的MCR问题实际上是多目标的,基于此本文对MCR问题进行了多目标优化研究。首先构建了MCR问题的多目标模型,然后针对多目标MCR问题的特殊性,对传统NSGA-II中的分布性保持策略、精英保持策略等进行了相应特殊化改进处理,并融合MCR问题模型中的标号集合构建适应度函数。与SACO及Greedy算法的对比实验结果表明,INSGA-II算法在同样障碍数量的场景中更适于解决MCR问题,可为MCR问题研究者或决策者提供可供选择的解决方案。与传统的MOEA及NSGA算法的对比实验结果表明,INSGA-II运行时间更快,搜索空间广阔,解数量多,解分布性好。（4）为了验证上述算法在仿真环境及真实场景情况下应用的的可行性与有效性,本文在Gazebo仿真平台上进行了两组MCR应用仿真实验及真实环境基于Baxter机器人进行了两组MCR应用实验。有效验证改进的蚁群优化算法（SACO）及改进的多目标优化算法（INSGA-II）在解决MCR问题中的可行性及有效性,为MCR问题在实际中的应用提供了有益的探索。