Browsing by Author "Slack, Marc G."
Now showing 1 - 4 of 4
Results Per Page
Sort Options
- Path Planning Through Time and Space in Dynamic DomainsSlack, Marc G.; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987-05-01)Realistic robot problems involve navigating the robot through time as well as space. The obstacles that a robot must avoid and the pathways on which it travels are subject to changes throughout time. These changes can occur in a predictable or unpredictable fashion. This paper presents an integrated route planning and spatial representation system that allows paths to be calculated in dynamic domains. The path planner finds the "best route" through a given n-dimensional space. The "best route" is defined as the path through space-time with the best score as determined by a set of user-defined evaluation
- Situationally driven local navigation for mobile robotsSlack, Marc G. (Virginia Tech, 1990)For mobile robots to autonomously accommodate dynamically changing navigation tasks in a goal-directed fashion, they must employ navigation plans. Any such plan must provide for the robot’s immediate and continuous need for guidance while remaining highly flexible in order to avoid costly computation each time the robot’s perception of the world changes. Due to the world’s uncertainties, creation and maintenance of navigation plans cannot involve arbitrarily complex processes, as the robot’s perception of the world will be in constant flux, requiring modifications to be made quickly if they are to be of any use. This work introduces Navigation Templates (or NaTs) which are building blocks for the construction and maintenance of rough navigation plans which capture the relationship that objects in the world have to the current navigation task. By encoding only the critical relationship between the objects in the world and the navigation task, a NaT-based navigation plan is highly flexible; allowing new constraints to be quickly incorporated into the plan and existing constraints to be updated or deleted from the plan. To satisfy the robot’s need for immediate local guidance, the NaTs forming the current navigation plan are passed to a transformation function. The transformation function analyzes the plan with respect to the robot’s current location to quickly determine (a few times a second) the locally preferred direction of travel. This dissertation presents NaTs and the transformation function as well as the needed support systems to demonstrate the usefulness of the technique for controlling the actions of a mobile robot operating in an uncertain world. ¹ This work was supported in part by a grant from the Jet Propulsion Laboratory under a contract from the National Aeronautics and Space Administration, and by a grant from the Naval Surface Weapons Center.
- Spatial and temporal path planningSlack, Marc G. (Virginia Tech, 1987)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.
- Spatial and Temporal Path PlanningSlack, Marc G.; Miller, David P. (Department of Computer Science, Virginia Polytechnic Institute & State University, 1987)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, 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^2)$ time.