Dissertation
Dissertation > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > General issues > Theories, methods > Algorithm Theory

Research on Navigation System Related Technology for Moving Objects under Dynamic Environment

Author WuZhiGang
Tutor ZuoDeCheng
School Harbin Institute of Technology
Course Computer Science and Technology
Keywords Moving objects navigation system Range probability querying Dynamic path planning Ant algorithm
CLC TP301.6
Type Master's thesis
Year 2008
Downloads 51
Quotes 0
Download Dissertation

In recent years, because of the rapid development of wireless communication, wearable computers and mobile computing technology, mobile objects have been used in more and more areas. On the other hand, since the rapid development of GPS and sensor technology, navigation system whose main target is to give the location-related service has been widely used. This paper will focus on two most important parts of the navigation system:Path planning and location query.In dynamic environment, due to the limit of communication bandwidth, moving objects themselves, database storage space and other factors, it is impossible to track moving objects in real time and store their exact location at all times, we can only record some information at specific time. For the range location query, the paper’s goal is to estimate the location of mobile information and then give a probability answer. This paper presents a specific model, index structure and the corresponding querying algorithm.Classic path planning algorithms are mainly used in static environment. For dynamic environment, if the environment is changed, we could only update the environment information and rerun the algorithm again, this is inefficient: the second run of the algorithm cannot use the information acquired by the first run, their running time is almost equal. In nature,ant colony can find a best path under frequently changed environment, similarly, the ant algorithm has inherent robustness and can also find an optimal path. But the ant colony optimization algorithm has many deficiencies, such as using relatively long time, slow speed of convergence as the result of negative feedback effects of the congested section. In order to overcome these shortcomings, this paper proposes a path planning algorithm framework under dynamic environment: It not only retains the useful information of last run, which avoids re-running the algorithm and saves a lot of time, and also introduces the "local-shaking" technology. If there is a traffic jam on some parts of the best path found by the last running of the algorithm, the "local-shaking" technology reduces its phenomenon concentration, so the convergence rate is improved. The last part of the paper makes a simulation and proves that the algorithm proposed by this paper is feasible and useful; it does improve the performance of the original ant colony algorithm under certain dynamic environment.

Related Dissertations
More Dissertations