Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Recurso digital |
| Language: | English |
| Published: |
Zenodo
2025
|
| Subjects: | |
| Online Access: | https://doi.org/10.1007/s12065-019-00331-5 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866902336127893504 |
|---|---|
| author | Sadeghi Bigham, Bahram Noorizadeh, Fariba Khodayifar, Salman |
| author_facet | Sadeghi Bigham, Bahram Noorizadeh, Fariba Khodayifar, Salman |
| contents | <p>The minimum constraint removal (MCR) is one of the most important problems in motion planning and computational geometry. In this problem, there is no feasible path for a robot to move from the starting point towards the goal. Therefore, in order to find a collision-free path, the minimum constraints should be removed. The MCR problem is NP − hard when constraints have arbitrary shapes or are in shape of convex polygons. Since it is not possible to solve the problem by deterministic algorithms in an acceptable time for the problem with big data, scientists have tried to solve it by approximation methods. In this paper, we present a deterministic (not approximation) algorithm that solve the problem in a polynomial time. The simplification we used here is about the type of data (neither about the accuracy of the solution, nor about the size of data set). In this paper, a special case of this problem is presented, in which all the constraints are axis-aligned-unit squares and the obstacles have only local effects. Local effect means there are no two cells which have the same label sets. We propose an algorithm for this variant of the problem which can be used for big data. The proposed algorithm has O(n3) time complexity in the worst case.</p> |
| format | Recurso digital |
| id | zenodo_https___doi_org_10_1007_s12065-019-00331-5 |
| institution | Zenodo |
| language | eng |
| publishDate | 2025 |
| publisher | Zenodo |
| record_format | zenodo |
| spellingShingle | A polynomial time algorithm for big data in a special case of minimum constraint removal problem Sadeghi Bigham, Bahram Noorizadeh, Fariba Khodayifar, Salman Motion planning Big data Computational geometry Minimum constraint removal Resilience <p>The minimum constraint removal (MCR) is one of the most important problems in motion planning and computational geometry. In this problem, there is no feasible path for a robot to move from the starting point towards the goal. Therefore, in order to find a collision-free path, the minimum constraints should be removed. The MCR problem is NP − hard when constraints have arbitrary shapes or are in shape of convex polygons. Since it is not possible to solve the problem by deterministic algorithms in an acceptable time for the problem with big data, scientists have tried to solve it by approximation methods. In this paper, we present a deterministic (not approximation) algorithm that solve the problem in a polynomial time. The simplification we used here is about the type of data (neither about the accuracy of the solution, nor about the size of data set). In this paper, a special case of this problem is presented, in which all the constraints are axis-aligned-unit squares and the obstacles have only local effects. Local effect means there are no two cells which have the same label sets. We propose an algorithm for this variant of the problem which can be used for big data. The proposed algorithm has O(n3) time complexity in the worst case.</p> |
| title | A polynomial time algorithm for big data in a special case of minimum constraint removal problem |
| topic | Motion planning Big data Computational geometry Minimum constraint removal Resilience |
| url | https://doi.org/10.1007/s12065-019-00331-5 |