一种改进的多点景区路径规划蚁群算法外文翻译资料

An Improved Ant Colony Algorithm for Path Planning in One Scenic Area With Many Spots

Abstract

Disadvantages inherent to existing guidance systems for scenic areas can be reduced to a partial point traversal problem in the connected graph. This paper presents an intelligent, ant-colony-based path planning algorithm that is applicable to scenic areas. The proposed algorithm modifies the antsrsquo; ending tour to achieve partial point traversal of the connected graph by eliminating the restriction of the ant colony algorithm taboo table. A temporary weight matrix is introduced so that the algorithm avoids the repeated selection of smaller-weight paths, improving its overall efficiency. The experimental results show that the improved ant colony algorithm proposed in this paper is more effective and efficiency than other algorithms and more suitable to solve the path planning problem in one scenic area with many spots.

KeyWords: Path planning, improved ant colony algorithm, temporary weight, shortest path matrix, path weight length.

I. INTRODUCTION

The traditional path planning of scenic areas can be abstracted into a TSP problem which is a typical NP problem [1], [2]. Intelligent algorithms [3] such as genetic algorithms and particle swarm optimization [4] can be applied to large-scale, complex TSP problems [5]. In recent years, the ant colony algorithm, inspired by the behavior of real ant colonies, has been successfully applied to solve TSP problems [6], [7]. The ant colony algorithm is thus suitable for solving path planning problems as well [8]. The ant colony algorithm has garnered a great deal of research interest lately, particularly in regards to combining it with other algorithms to improve their performance [9]. However the traditional path planning [10] problem for scenic areas is so abstract that the ant colony algorithm does not practically apply. There are a few main reasons for this.

1) In the traditional path planning of scenic areas [11], the scenic area is abstracted as a simple graph that includes only particular scenic spots while the actual area as a whole is ignored. An actual scenic area should be represented by a complex graph with multiple types of points including the entrance, internal scenic spots, public service points, road forks, and so on.

2) The scenic area is directly abstracted as a complete graph with a direct pathway between any two scenic spots. In actuality, the scenic area can only be defined as a connected graph with such pathways between any two scenic spots [12] though the real pathway may not directly connect them.

3) The traditional path planning of scenic areas is not focused on the customersrsquo; real demands [13], [14]. When the scenic spots are numerous or the tourists only have limited time to visit specific spots, the traditional path planning algorithm does not reflect the manner in which they select scenic spots drawing their immediate interest.

4) The shortest tour path is defined as the best tour path. But in a real scenic area, some roads may be steep and difficult to pass for the children and the aged, moreover some roads may be crowded. So a better path planning algorithm should avoid the special roads and supply the suitable paths for tourists [15], [16].

Modern individuals tend to travel with more than one mobile device, they use an array of devices to gather information and plan their tour through scenic areas. Mobile devices, of course, have limited storage, limited computation power, and limited communication resources- in other words, they require a highly efficient and effective path planning algorithm. In this study, we designed a novel path planning algorithm for scenic areas based on the typical ant colony algorithm. Tourists could utilize this algorithm to customize their own tour paths to satisfy individual, dynamic requirements.

The remainder of this paper is organized as follows: Section II elaborates on related works and our contributions;Section III introduces the traditional ant colony algorithm in brief; Section IV proposes the improved ant colony algorithm for solving the path planning problem in weakly connected graphs; Section V presents the results of our experiments, and Section VI offers a conclusion.

II. RELATED WORKS

Graph-based algorithms are typically used for planning travel paths [17], [18]. The problem is NP-hard, however, so this leaves room only for lsquo;lsquo;good enoughrsquo;rsquo; solutions. Path planning also involves risk assessment, which is based on estimates at best due to the underlying complexities.

A path planning optimization method is proposed here to calculate the shortest collision-free path from source to destination by avoiding static as well as dynamic obstacles [19]. An appropriate technique is necessary to facilitate the optimization of paths. Existing algorithms for this purpose include the artificial potential field algorithm, neural network algorithm, genetic algorithm, grid algorithm, and ant colony algorithm [20]–[22]. Among these algorithms, the artificial potential field is convenient for the underlying real-time control, but is easily trapped into local optima thus lacking global information. The neural network is good at learning, but its net structure is oversize; further, its neuron thresholds change with time within multi-obstacle and dynamic environmental conditions. The genetic algorithm has a good global searching capability, but its search space is large and the model must be continually reestablished as the environment changes. The grid algorithm can elucidate optimal paths, but its efficiency is affected by environment and grid density.

The ant colony algorithm has been widely applied to travel path planning and yields good solutions with fewer predetermined param

剩余内容已隐藏，支付完成后下载完整资料

英语译文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[589853]，资料为PDF文档或Word文档，PDF文档可免费转换为Word