Solving minimum constraint removal (MCR) problem using a social-force-model-based ant colony algorithm |
| |
Affiliation: | 1. Department of Chemical Engineering and Petroleum, School of Engineering, Universidade Federal Fluminense, Rua Passo da Pátria, 156, CEP: 24210240, Niterói, RJ, Brazil;2. Chemical Engineering Program - PEQ/COPPE, Universidade Federal do Rio de Janeiro, Av. Horácio Macedo 2030, Centro de Tecnologia, Bloco G, Sala G-116, Cidade Universitária, Ilha do Fundão, Cx.P. 68502, CEP: 21941-914, Rio de Janeiro, RJ, Brazil |
| |
Abstract: | 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. |
| |
Keywords: | Ant colony algorithm Discrete MCR Motion planning problem Robot path planning Social force model |
本文献已被 ScienceDirect 等数据库收录! |
|