Navigation & Localization

@inproceedings{50155,
title = {Avoidance Critical Probabilistic Roadmaps for Motion Planning in Dynamic Environments},
author = {Felipe Felix Arias and Brian Andrew Ichter and Aleksandra Faust and Nancy M. Amato},
year = {2021},
booktitle = {IEEE International Conference on Robotics and Automation (ICRA)}
}

Motion planning among dynamic obstacles is an essential capability towards navigation in the real-world. Sampling-based motion planning algorithms find solutions by approximating the robot’s configuration space through a graph representation, predicting or computing obstacles’ trajectories, and finding feasible paths via a pathfinding algorithm. In this work, we seek to improve the performance of these subproblems by identifying regions critical to dynamic environment navi- gation and leveraging them to construct sparse probabilistic roadmaps. Motion planning and pathfinding algorithms should allow robots to prevent encounters with obstacles, irrespective of their trajectories, by being conscious of spatial context cues such as the location of chokepoints (e.g., doorways). Thus, we propose a self-supervised methodology for learning to identify regions frequently used for obstacle avoidance from local environment features. As an application of this concept, we leverage a neural network to generate hierarchical probabilistic roadmaps termed Avoidance Critical Probabilistic Roadmaps (ACPRM). These roadmaps contain motion structures that enable efficient obstacle avoidance, reduce the search and planning space, and increase a roadmap’s reusability and coverage. ACPRMs are demonstrated to achieve up to five orders of magnitude improvement over grid-sampling in the multi-agent setting and up to ten orders of magnitude over a competitive baseline in the multi-query setting.

@INPROCEEDINGS{6906602, author={A. {Agha-mohammadi} and S. {Agarwal} and A. {Mahadevan} and S. {Chakravorty} and D. {Tomkins} and J. {Denny} and N. M. {Amato}}, booktitle={2014 IEEE International Conference on Robotics and Automation (ICRA)}, title={Robust online belief space planning in changing environments: Application to physical mobile robots}, year={2014}, volume={}, number={}, pages={149-156}, doi={10.1109/ICRA.2014.6906602}}

Motion planning in belief space (under motion and sensing uncertainty) is a challenging problem due to the computational intractability of its exact solution. The Feedback-based Information RoadMap (FIRM) framework made an important theoretical step toward enabling roadmap-based planning in belief space and provided a computationally tractable version of belief space planning. However, there are still challenges in applying belief space planners to physical systems, such as the discrepancy between computational models and real physical models. In this paper, we propose a dynamic replanning scheme in belief space to address such challenges. Moreover, we present techniques to cope with changes in the environment (e.g., changes in the obstacle map), as well as unforeseen large deviations in the robot's location (e.g., the kidnapped robot problem). We then utilize these techniques to implement the first online replanning scheme in belief space on a physical mobile robot that is robust to changes in the environment and large disturbances. This method demonstrates that belief space planning is a practical tool for robot motion planning.

@INPROCEEDINGS{4209224,
author={Morales, Marco and Pearce, Roger and Amato, Nancy M.},
booktitle={Proceedings 2007 IEEE International Conference on Robotics and Automation},
title={Analysis of the Evolution of C-Space Models built through Incremental Exploration},
year={2007},
volume={},
number={},
pages={1029-1034},
doi={10.1109/ROBOT.2007.363120}}

Many sampling methods for motion planning explore the robot's configuration space (C-space) starting from a set of configuration(s) and incrementally explore surrounding areas to produce a growing model of the space. Although there is a common understanding of the strengths and weaknesses of these techniques, metrics for analyzing the incremental exploration process and for evaluating the performance of incremental samplers have been lacking. We propose the use of local metrics that provide insight into the complexity of the different regions in the model and global metrics that describe the process as a whole. These metrics only require local information and can be efficiently computed. We illustrate the use of our proposed metrics to analyze representative incremental strategies including the rapidly-exploring random trees, expansive space trees, and the original randomized path planner. We show how these metrics model the efficiency of C-space exploration and help to identify different modeling stages. In addition, these metrics are ideal for adapting space exploration to improve performance.

@INPROCEEDINGS{1242025,
author={ {Jinsuck Kim} and R. A. {Pearce} and N. M. {Amato}},
booktitle={2003 IEEE International Conference on Robotics and Automation (Cat. No.03CH37422)}, title={Feature-based localization using scannable visibility sectors},
year={2003},
volume={2},
number={},
pages={2854-2859 vol.2},
doi={10.1109/ROBOT.2003.1242025}}

This paper presents methods for navigating and localizing mobile robots in a known indoor environment. We introduce a restricted visibility concept called a scannable sector that can aid many existing navigation and localization algorithms. The scannable sectors are based on the physical characteristics of the environment and the limitations of the localization sensors used. We describe a complete navigation system that includes a scannable sector based localizer, sonar sensors, and a probabilistic roadmap path planner. Simulation and hardware results using a real robot with sonar sensors show the potential of our approach.

@INPROCEEDINGS{933208, author={ {Jinsuck Kim} and N. M. {Amato} and {Sooyong Lee}}, booktitle={Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation (Cat. No.01CH37164)}, title={An integrated mobile robot path (re)planner and localizer for personal robots}, year={2001}, volume={4}, number={}, pages={3789-3794 vol.4}, doi={10.1109/ROBOT.2001.933208}}

We describe a method for navigation in a known indoor environment, such as a home or office, that requires only inexpensive range sensors. Our framework includes a high-level planner which integrates and coordinates path planning and localization modules with the aid of a module for computing regions which are expected, with high probability, to contain the robot at any given time. The localization method is based on simple geometric properties of the environment which are computed during a preprocessing stage. The roadmap-based path planner enables one to select routes, and subgoals along those routes, that will facilitate localization and other optimization criteria. In addition, our framework enables one to quickly plan new routes, dynamically, based on the current position as computed by intermediate localization operations. We present simulation and hardware experimental results that illustrate the practicality and potential of our approach.