Multi-Robot Path-Planning Problem for a Heavy Traffic Control Application: A Survey
Journal Title: International Journal of Advanced Computer Science & Applications - Year 2016, Vol 7, Issue 6
Abstract
This survey looked at the methods used to solve multi-autonomous vehicle path-planning for an application of heavy traffic control in cities. Formally, the problem consisted of a graph and a set of robots. Each robot has to reach its destination in the minimum time and number of movements, considering the obstacles and other robots’ paths, hence, the problem is NP-hard. The study found that decoupled centralised approaches are the most relevant approaches for an autonomous vehicle path-planning problem for three reasons: (1) a city is a large environment and coupled centralised approaches scale weakly, (2) the overhead of a coupled decentralised approach to achieve the global optimal will affect the time and memory of the other robots, which is not important in a city configuration and (3) the coupled approaches suppose that the number of robots is defined before they start to find the paths and resolve collisions, while in a city, any car can start at any time and hence, each car should work individually and resolve collisions as they arise. In addition, the study reviewed four decoupled centralised techniques to solve the problem: multi-robot path-planning rapidly exploring random tree (MRRRT), push and swap (PAS), push and rotate (PAR) and the Bibox algorithm. The experiments showed that MRRRT is the best for exploring any search space and optimizing the solution. On the other hand, PAS, PAR and Bibox are better in terms of providing a complete solution for the problem and resolving collisions in significantly much less time, the analysis, however, shows that a wider class of solvable instances are excluded from PAS and PAR domain. In addition, Bibox solves a smaller class than the class solved by PAS and PAR in less time, in the worst case, and with a shorter path than PAS and PAR.
Authors and Affiliations
Ebtehal Alotaibi, Hisham Al-Rawi
Keywords
Related Articles
- EP ID EP133563
- DOI 10.14569/IJACSA.2016.070623
- Views 110
- Downloads 0
Cost Optimization of Cloud Computing Services in a Networked Environment
Cloud computing service providers' offer their customers' services maximizing their revenues, whereas customers wish to minimize their costs. In this paper we shall concentrate on consumers' point of view. Cloud computin...
Students’ Perceptions of the Effectiveness of Discussion Boards: What can we get from our students for a freebie point
In this paper, we investigate how the students think of their experience in a junior (300 level) computer science course that uses blackboard as the underlying course management system. Blackboard’s discussion boar...
Security Issues of a Recent RFID Multi Tagging Protocol
RFID is now a widespread method used for identifying people and objects. But, not all communication protocols can provide the same rigorous confidentiality to RFID technology. In return, unsafe protocols put individuals...
Performance Analysis of Artificial Neural Networks Training Algorithms and Transfer Functions for Medium-Term Water Consumption Forecasting
Artificial Neural Network (ANN) is a widely used machine learning pattern recognition technique in predicting water resources based on historical data. ANN has the ability to forecast close to accurate prediction given t...
Voice Detection in Traditionnal Tunisian Music using Audio Features and Supervised Learning Algorithms
The research presented in this paper aims to automatically detect the singing voice in traditional Tunisian music, taking into account the main characteristics of the sound of the voice in this particular music style. Th...