Spatial and temporal path planning

For robots to move out of the lab and into the real-world, they must be able to plan routes not only through space but through time as well. The introduction of a time factor to the planning process implies that robots must reason about other processes and agents that move through space independently of the robot's actions. This thesis presents an integrated route planner and spatial representation system for planning real-time paths through dynamic domains called Robonav. Robonav will find the safest 9 most efficient route through time and space as described by an evaluation function. Due to the design of the spatial representation and the mechanics of the algorithm, Robonav has an isomorphic mapping onto a machine with a highly parallel SIMD architecture. When Robonav is operated in a predictable domain, paths are found in O(p) time (where p is the length of a path). In unpredictable domains, where Robonav is operated in incremental mode, paths are found and executed in O(p²) time.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

masters

Discipline thesis:degree_discipline

Computer Science

Department dc:contributor.department

Computer Science

Grantor dc:publisher

Virginia Tech

Year dc:date.issued

1987

Author dc:creator

• Slack, Marc G.

Statement dc:rights

• In Copyright

Licence dc:rights.uri

• http://rightsstatements.org/vocab/InC/1.0/

Dc Identifier Other

etd-04272010-020255

OAI identifier oai:identifier

oai:vtechworks.lib.vt.edu:10919/42332