@Article{BrossetClaramunt2010,
author = {Brosset, David and Claramunt, Christophe},
title = {An experimental ant colony approach for the geolocation of verbal route descriptions},
journal = {Knowledge-Based Systems},
year = {2010},
volume = {24},
pages = {484-491}
}
This paper tries to bridge verbal descriptions of routes with biologically-inspired algorithms to produce paths according to instructions given as input in an open environment (i.e. not constrained by specific roads).[484]
Navigation knowledge concepts are introduced, with an emphasis on the importance of verbs and landmarks in directions.[485]
Stochastic algorithms are presented as an approach to efficiently find paths through large search spaces.[484]
Ant Colony System (ACS) is described: the algorithms work by sending out many agents with very simple behaviors, moving mostly at random and leaving trails behind them, marking the environment with their path. Another generation of agents will then do the same task, with the trails still present, and good trails will be picked up by the new agents, inciting them to follow them. Incrementally, due to their random movement and their attraction toward previous solutions, good solutions will be found by the agents after a number of iterations.[484]
The routes are described according to a model inspired by foot orienteering, where a series of control points are to be found by trainees after they have been given instructions describing actions that should be taken at certain points.[485]
Routes are defined as sets of nodes and directed edges associated respectively to locations and actions. Locations can be anywhere but will commonly be near landmarks and actions will commonly consist of a relative or cardinal orientation.[485]
The algorithm used in this paper operates in two phases: initialization and execution.[486]
A point is emphasized about the aim of the algorithm: optimizing the length of a route is not its goal. It is rather the generation of path which follows adequately verbal descriptions (i.e. directions).[486]
The initialization part of the algorithm generates the search space with the landmarks of the environment as input. It create layers of decision points, which are initially produced randomly then selected when near landmarks. The layers represent sets of possible nodes for the next step in a given route.[487]
A constraint is included in the system by selecting points which are near landmarks, increasing the general relevance of landmarks when it will come to pathfinding.[486]
The execution part iterates through the production of paths and their evaluation.[487]
Paths are produced by many individual agents (referred to as ants, in the paper) moving from decision point to decision point in a stochastic manner, influenced by trails of pheromone previously left by agents from previous iterations. The strength of the influence and the rate of evaporation of pheromones are formally defined so as to allow novel solutions to arise, avoiding premature local convergences.[487]
Evaluating the paths is done by taking each of its segments and increasing the pheromone value of those segments if they conform to the route description initially given as input.[488]
The search for a path is constrained by every direction in the route description, making them highly relevant in the process of obtaining a satisfying solution.[486]
Parameters are discussed in the context of many tests done with similar data, indicating useful values for the number of ants and the rate of evaporation of pheromone.[488]
Results show that convergence is seen in the solution paths obtained after 100 iterations. It is noted that many paths appears, all equally fit but all different in terms of distance travelled, final destination, and nodes encountered.[489]
The length of the route description influences the results such that a route including more actions will produce less final solutions, even though the initial number of candidates was higher.[489]
The Ant Colony System is compared to a Genetic Algorithm implementing selection, crossover and mutation operators. While similar in terms of final solutions, the Ant Colony System is seen to converge faster.[490]
Since many solutions are often offered by the algorithm, it is suggested that they should be considered as a first step in a route finding problem, human experts being then able to choose which of the solutions is the more appropriate given the initial route description.[490]
Future plans for this line of research includes adding environmental information influencing the evaluation of paths, such as barriers, and experiments involving comparisons between paths found by orienteers and their computational counterparts.[490]