Solving minimum constraint removal (MCR) problem using a social-force-model-based ant colony algorithm

The minimum constraint removal (MCR) motion planning problem aims to remove the minimum geometric constraints necessary for removing a free path that connects the starting point and the target point. In essence, discrete MCR problems are non-deterministic polynomial-time (NP)-hard problems; there is a “combinatorial explosion” phenomenon in solving such problems on a large scale. Therefore, we are searching for highly efficient approximate solutions. In the present study, an ant colony algorithm was used to solve these problems. The ant colony algorithm was improved based on the social force model during the solving process, such that it was no longer easy for the algorithm to fall into local extreme, and the algorithm was therefore suitable for solving the MCR problem. The results of the simulation experiments demonstrated that the algorithm used in the present study was superior to the exact algorithm and the greedy algorithm in terms of solution quality and running time.