{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/42332"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/42332","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"Spatial and temporal path planning","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Slack, Marc G."],"institution":"Virginia Tech","degree_name":"Master of Science","degree_level":"masters","degree_discipline":"Computer Science","degree_department":"Computer Science","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1987,"date_issued":"1987","date_published":"1987","updated_at":"2026-07-22T22:19:22Z","subjects":[],"languages":[],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-04272010-020255"],"render_values":[{"text":"etd-04272010-020255","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/10919/42332","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Computer Science"]},{"key":"dc:creator","label":"Author","values":["Slack, Marc G."]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2014-03-14T21:34:59Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2014-03-14T21:34:59Z","2010-04-27"]},{"key":"dc:date.issued","label":"Date","values":["1987"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Tech"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Master of Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["etd-04272010-020255"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/42332"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["Master of Science"]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["BTD"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Spatial and temporal path planning"]}]}],"canonical_facts":{"dc:contributor.department":["Computer Science"],"dc:creator":["Slack, Marc G."],"dc:date.accessioned":["2014-03-14T21:34:59Z"],"dc:date.available":["2014-03-14T21:34:59Z","2010-04-27"],"dc:date.issued":["1987"],"dc:description.abstract":["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."],"dc:description.degree":["Master of Science"],"dc:format.medium":["BTD"],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["etd-04272010-020255"],"dc:identifier.uri":["http://hdl.handle.net/10919/42332"],"dc:publisher":["Virginia Tech"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["Spatial and temporal path planning"],"dc:type":["Thesis"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["masters"],"thesis:degree_name":["Master of Science"],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:22Z"}