Finding the shortest route is certainly one of the most topics for navigation and telecom- munications, which finds occurrence in many daily activities. Design reliable Shortest Path Algorithms play, therefore, a crucial role, for instance, in determining the shortest route between two geographical locations; in survival network design; in social net- works, such as finding the shortest degree of separation between two persons; in mil- itary, and specifically in unmanned aerial vehicles. What makes more complex and harder this problem is that often the shortest path with respect the distance is not al- ways the fastest one with regards the time [1]. This is due because very often it has to be solved in real-time, and under demands of limited memory and CPU resources [2]. This, of course, makes harder the successfully application of classical heuristic method- ologies, primarily on large maps. It is worth emphasizing that path finding is one of the most important issue, and difficult task in mobile robotics: finding a reasonable collision-free path for moving from a start location to a destination in an environment with obstacles. One interesting and challenging problem in computer science and, primarily, in robotics is to find the shortest path for moving from a starting point to a target one inside a labyrinth in the shortest possible time. The labyrinth is a well known puzzle game whose main aim is therefore to discover the most efficient and shortest route among many at the shortest possible time in reaching the target destination. It simply consists of a collection of paths, each of them with turns, and with pathways and walls fixed, from which determine the most appropriate one. Since the search time in this problem is an important evaluation measure to take into account becomes crucial develop an efficient algorithm able to reach the best possible solution in a reasonable time. This real-time search constraint, together to the handling of large data, justifies the use of metaheuristics even if the problem can be polynomial [3]. Due to these constraints, for example, the use of polynomial algorithms, such as the Dijkstra algorithm, might be time consuming. In light of this, in this work we present a labyrinth solver based on an ant colony algorithm, simply called ACOLABS (Ant COlony for LAByrinth Solver), able to find suitable solutions in reasonable times. Ant Colony Optimization (ACO) represents aconsolidate algorithmic technique inspired by the behavior of real ant colonies, which has proven to be efficient and reliable in solving several combinatorial problems, with main reference to routing problems. ACOLABS has been performed on several labyrinth scenarios, showed in figure 1 (from the simple to the more complex), and on different complexities. Finally, in figure 2 (left plot) is graphically shown the exploration phase, during which each ant explores different promising regions in the search space, until to discover the right and best path (right plot). With red circles in the left figure are highlighted those ants that are exploring the right path.
ACOLABS: an Ant Colony for Labyrinth Solving
2019
Abstract
Finding the shortest route is certainly one of the most topics for navigation and telecom- munications, which finds occurrence in many daily activities. Design reliable Shortest Path Algorithms play, therefore, a crucial role, for instance, in determining the shortest route between two geographical locations; in survival network design; in social net- works, such as finding the shortest degree of separation between two persons; in mil- itary, and specifically in unmanned aerial vehicles. What makes more complex and harder this problem is that often the shortest path with respect the distance is not al- ways the fastest one with regards the time [1]. This is due because very often it has to be solved in real-time, and under demands of limited memory and CPU resources [2]. This, of course, makes harder the successfully application of classical heuristic method- ologies, primarily on large maps. It is worth emphasizing that path finding is one of the most important issue, and difficult task in mobile robotics: finding a reasonable collision-free path for moving from a start location to a destination in an environment with obstacles. One interesting and challenging problem in computer science and, primarily, in robotics is to find the shortest path for moving from a starting point to a target one inside a labyrinth in the shortest possible time. The labyrinth is a well known puzzle game whose main aim is therefore to discover the most efficient and shortest route among many at the shortest possible time in reaching the target destination. It simply consists of a collection of paths, each of them with turns, and with pathways and walls fixed, from which determine the most appropriate one. Since the search time in this problem is an important evaluation measure to take into account becomes crucial develop an efficient algorithm able to reach the best possible solution in a reasonable time. This real-time search constraint, together to the handling of large data, justifies the use of metaheuristics even if the problem can be polynomial [3]. Due to these constraints, for example, the use of polynomial algorithms, such as the Dijkstra algorithm, might be time consuming. In light of this, in this work we present a labyrinth solver based on an ant colony algorithm, simply called ACOLABS (Ant COlony for LAByrinth Solver), able to find suitable solutions in reasonable times. Ant Colony Optimization (ACO) represents aconsolidate algorithmic technique inspired by the behavior of real ant colonies, which has proven to be efficient and reliable in solving several combinatorial problems, with main reference to routing problems. ACOLABS has been performed on several labyrinth scenarios, showed in figure 1 (from the simple to the more complex), and on different complexities. Finally, in figure 2 (left plot) is graphically shown the exploration phase, during which each ant explores different promising regions in the search space, until to discover the right and best path (right plot). With red circles in the left figure are highlighted those ants that are exploring the right path.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
