
Accession Number : ADA311383
Title : Research on Motion Planning of Autonomous Mobile Robot.
Descriptive Note : Master's thesis,
Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA
Personal Author(s) : Papadatos, Athanassios
PDF Url : ADA311383
Report Date : MAR 1996
Pagination or Media Count : 117
Abstract : The path planning algorithm in Yamabico is based on a variation of Dijkstra's algorithm which has time complexity of O(n2). This algorithm works well in a dynamic environment, but a faster algorithm, called the AllPairs Minimum Cost Paths algorithm, works even faster, O(1), in the case of a static environment. The computational complexity of the AllPairs algorithm is O(n3), but if we know all pairs in advance, that is, the environment is static, we can preprocess them in advance, and use table lookup instead of Dijkstra's algorithm. Thus, we implemented a table lookup version for the static case, and kept Dijkstra's algorithm for the dynamic case. This results in both speed and flexibility. This thesis also investigated the Linear Fitting Algorithm for Sonar testing. Range and angle data, from sonar, was fit to a straight line, giving resolution of 1 to 2.5 cm when the robot is within 100 to 150 cm of the line.
Descriptors : *ALGORITHMS, *ROBOTS, *PATHS, *MOTION, *AUTONOMOUS NAVIGATION, TEST AND EVALUATION, LINEAR SYSTEMS, ANGLES, GLOBAL, COMPUTATIONS, ENVIRONMENTS, DYNAMICS, THESES, COSTS, PLANNING, MOBILE, SELF OPERATION, TABLES(DATA), STATICS, SONAR.
Subject Categories : Cybernetics
Navigation and Guidance
Distribution Statement : APPROVED FOR PUBLIC RELEASE