Browsing by Subject "Motion Planning"
Now showing 1 - 8 of 8
Results Per Page
Sort Options
Item A Scalable Framework for Parallelizing Sampling-Based Motion Planning Algorithms(2014-04-29) Jacobs, Samson AdeMotion planning is defined as the problem of finding a valid path taking a robot (or any movable object) from a given start configuration to a goal configuration in an environment. While motion planning has its roots in robotics, it now finds application in many other areas of scientific computing such as protein folding, drug design, virtual prototyping, computer-aided design (CAD), and computer animation. These new areas test the limits of the best sequential planners available, motivating the need for methods that can exploit parallel processing. This dissertation focuses on the design and implementation of a generic and scalable framework for parallelizing motion planning algorithms. In particular, we focus on sampling-based motion planning algorithms which are considered to be the state-of-the-art. Our work covers the two broad classes of sampling-based motion planning algorithms--the graph-based and the tree-based methods. Central to our approach is the subdivision of the planning space into regions. These regions represent sub- problems that can be processed in parallel. Solutions to the sub-problems are later combined to form a solution to the entire problem. By subdividing the planning space and restricting the locality of connection attempts to adjacent regions, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We also describe how load balancing strategies can be applied in complex environments. We present experimental results that scale to thousands of processors on different massively parallel machines for a range of motion planning problems.Item Decision Making of Mobile Robot in the Presence of Risk on Its Surroundings(2012-02-14) Huh, SungMobile robots are used on many areas and its demand on extreme terrain, hazardous area, or life-threatening place is increasing to reduce the loss of life. A good decision making capability is essential for successful navigation of autonomous robot and it affect finding the shortest or optimal path within given condition. The wavefront algorithm is simple to apply, yet yield an optimal path for a robot to follow in many different configurations. Although the path created using wavefront algorithm is an optimal in the sense that every node has the same cost, the result is not the best result in global perspective because of the algorithm is inconsiderate on the surrounding condition. To solve this issue and create the best result on global perspective, risk factor analysis method was implemented on the wavefront algorithm to improve the performance. In this work, the relationship between the wavefront algorithm and dynamic programming will be explained to show that the wavefront algorithm obeys the principle of optimality. The simulation result displays better performance on safety, while keeping the travelling distance minimum, if the risk factor is used on the wavefront algorithm and the robot on actual test behave accordingly. This work will contribute on decision making of mobile robot using risk factor method to create a most desirable and safe path. In addition to that, it will demonstrate how the risk factor method can be applied to the mobile robot navigation.Item Feedback-based Information Roadmap (FIRM): Graph-based Estimation and Control of Robotic Systems Under Uncertainty(2014-05-07) Aghamohammadi, AliakbarThis dissertation addresses the problem of stochastic optimal control with imperfect measurements. The main application of interest is robot motion planning under uncertainty. In the presence of process uncertainty and imperfect measurements, the system's state is unknown and a state estimation module is required to provide the information-state (belief), which is the probability distribution function (pdf) over all possible states. Accordingly, successful robot operation in such a setting requires reasoning about the evolution of information-state and its quality in future time steps. In its most general form, this is modeled as a Partially-Observable Markov Decision Process (POMDP) problem. Unfortunately, however, the exact solution of this problem over continuous spaces in the presence of constraints is computationally intractable. Correspondingly, state-of-the-art methods that provide approximate solutions are limited to problems with short horizons and small domains. The main challenge for these problems is the exponential growth of the search tree in the information space, as well as the dependency of the entire search tree on the initial belief. Inspired by sampling-based (roadmap-based) methods, this dissertation proposes a method to construct a "graph" in information space, called Feedback-based Information RoadMap (FIRM). Each FIRM node is a probability distribution and each FIRM edge is a local controller. The concept of belief stabilizers is introduced as a way to steer the current belief toward FIRM nodes and induce belief reachability. The solution provided by the FIRM framework is a feedback law over the information space, which is obtained by switching among locally distributed feedback controllers. Exploiting such a graph in planning, the intractable POMDP problem over continuous spaces is reduced to a tractable MDP (Markov Decision Process) problem over the graph (FIRM) nodes. FIRM is the first graph generated in the information space that preserves the principle of optimality, i.e., the costs associated with different edges of FIRM are independent of each other. Unlike the forward search methods on tree-structures, the plans produced by FIRM are independent of the initial belief (i.e., plans are query-independent). As a result, they are robust and reliable. They are robust in the sense that if the system's belief deviates from the planned belief, then replanning is feasible in real-time, as the computed solution is a feedback over the entire belief graph. Computed plans are reliable in the sense that the probability of violating constraints (e.g., hitting obstacles) can be seamlessly incorporated into the planning law. Moreover, FIRM is a scalable framework, as the computational complexity of its construction is linear in the size of underlying graph as opposed to state-of-the-art methods whose complexity is exponential in the size of underlying graph. In addition to the abstract framework, we present concrete FIRM instantiations for three main classes of robotic systems: holonomic, nonholonomic, and non-pointstabilizable. The abstract framework opens new avenues for extending FIRM to a broader class of systems that are not considered in this dissertation. This includes systems with discrete dynamics or in general systems that are not well-linearizable, systems with non-Gaussian distributions, and systems with unobservable modes. In addition to the abstract framework and concrete instantiations of it, we propose a formal technique for replanning with FIRM based on a rollout-policy algorithm to handle changes in the environment as well as discrepancies between actual and computational models. We demonstrate the performance of the proposed motion planning method on different robotic systems, both in simulation and on physical systems. In the problems we consider, the system is subject to motion and sensing noise. Our results demonstrate a significant advance over existing approaches for motion planning in information space. We believe the proposed framework takes an important step toward making information space planners applicable to real world robotic applications.Item Local Randomization in Neighbor Selection Improves PRM Roadmap Quality(2012-08-27) Boyd, Bryan 1985-Probabilistic Roadmap Methods (PRMs) are one of the most used classes of motion planning methods. These sampling-based methods generate robot configurations (nodes) and then connect them to form a graph (roadmap) containing representative feasible pathways. A key step in PRM roadmap construction involves identifying a set of candidate neighbors for each node. Traditionally, these candidates are chosen to be the k-closest nodes based on a given distance metric. This work proposes a new neighbor selection policy called LocalRand(k, k'), that first computes the k' closest nodes to a specified node and then selects k of those nodes at random. Intuitively, LocalRand attempts to benefit from random sampling while maintaining the higher levels of local planner success inherent to selecting more local neighbors. A methodology for selecting the parameters k and k' is provided, and an experimental comparison for both rigid and articulated robots show that LocalRand results in roadmaps that are better connected than the traditional k-closest or a purely random neighbor selection policy. The cost required to achieve these results is shown to be comparable to the cost of k-closest.Item Metrics for sampling-based motion planning(2009-05-15) Morales Aguirre, Marco AntonioA motion planner finds a sequence of potential motions for a robot to transit from an initial to a goal state. To deal with the intractability of this problem, a class of methods known as sampling-based planners build approximate representations of potential motions through random sampling. This selective random exploration of the space has produced many remarkable results, including solving many previously unsolved problems. Sampling-based planners usually represent the motions as a graph (e.g., the Probabilistic Roadmap Methods or PRMs), or as a tree (e.g., the Rapidly exploring Random Tree or RRT). Although many sampling-based planners have been proposed, we do not know how to select among them because their different sampling biases make their performance depend on the features of the planning space. Moreover, since a single problem can contain regions with vastly different features, there may not exist a simple exploration strategy that will perform well in every region. Unfortunately, we lack quantitative tools to analyze problem features and planners performance that would enable us to match planners to problems. We introduce novel metrics for the analysis of problem features and planner performance at multiple levels: node level, global level, and region level. At the node level, we evaluate how new samples improve coverage and connectivity of the evolving model. At the global level, we evaluate how new samples improve the structure of the model. At the region level, we identify groups or regions that share similar features. This is a set of general metrics that can be applied in both graph-based and tree-based planners. We show several applications for these tools to compare planners, to decide whether to stop planning or to switch strategies, and to adjust sampling in different regions of the problem.Item Motion planning under uncertainty: application to an unmanned helicopter(Texas A&M University, 2006-10-30) Davis, Joshua DanielA methodology is presented in this work for intelligent motion planning in an uncertain environment using a non-local sensor, like a radar sensor, that allows the sensing of the environment non-locally. This methodology is applied to an unmanned helicopter navigating a cluttered urban environment. It is shown that the problem of motion planning in a uncertain environment, under certain assumptions, can be posed as the adaptive optimal control of an uncertain Markov Decision Process, characterized by a known, control dependent system, and an unknown, control independent environment. The strategy for motion planning then reduces to computing the control policy based on the current estimate of the environment, also known as the "certainty equivalence principle" in the adaptive control literature. The methodology allows the inclusion of a non-local sensor into the problem formulation, which significantly accelerates the convergence of the estimation and planning algorithms. Further, the motion planning and estimation problems possess special structure which can be exploited to reduce the computational burden of the associated algorithms significately. As a result of the methodology developed for motion planning in this thesis, an unmanned helicopter is able to navigate through a partially known model of the Texas A&M campus.Item Multi-directional Rapidly Exploring Random Graph (mRRG) for Motion Planning(2013-08-27) Nath, Shuvra KantiThe motion planning problem in robotics is to find a valid sequence of motions taking some movable object from a start configuration to a goal configuration in an environment. Sampling-based path planners are very popular for high-dimensional motion planning in complex environments. These planners build a graph (roadmap) by generating robot configurations (vertices), and connecting nearby pairs of configurations according to their transition feasibility. Tree-based sampling-based planners (e.g., Rapidly-Exploring Random Tree, or RRT) start growing a tree outward from an initial configuration of the robot. In this work, we propose a multi-directional Rapidly-Exploring Random Graph (mRRG) for robotic motion planning, a variant of the Rapidly-Exploring Random Graph (RRG). Instead of expanding a vertex in the tree in a single random direction during each iteration, mRRG expands in m random directions. Our results show that growing in multiple directions in this way produces roadmaps with more topologically distinct paths than previous methods. In an environment with dynamic obstacles, moving or new obstacles may invalidate a path from the start to the goal. Hence, roadmaps containing alternative pathways can be beneficial as they may avoid recalculation of new valid paths. One of the important phases in sampling-based methods involves finding candidate nearest neighbors to attempt to connect to a node. Generally, the entire graph is considered to search for the nearest neighbors. In this thesis, we propose a heuristic method for finding nearest neighbors based on the hop limit, i.e., the maximum number of edges allowed in the path from a vertex to its neighbor. The candidate nearest neighbors are found by considering only those vertices within the hop limit. We experimentally show that our hop limit neighbor finder significantly reduces neighbor searching time over the standard brute force approach when constructing roadmaps.Item Visualization tools for moving objects(Texas A&M University, 2006-04-12) Vargas Estrada, AimeeIn this work we describe the design and implementation of a general framework for visualizing and editing motion planning environments, problem instances, and their solutions. The motion planning problem consists of finding a valid path between a start and a goal configuration for a movable object. The workspace is, in traditional robotics and animation applications, composed of one or more objects (called obstacles) that cannot overlap with the robot. As even the simplest motion planning problems have been shown to be in- tractable, most practical approaches to motion planning use randomization and/or compute approximate solutions. While the tool we present allows the manipulation and evaluation of planner solutions and the animation of any path found by any plan- ner, it is specialized for a class of randomized planners called probabilistic roadmap methods (PRMs). PRMs are roadmap-based methods that generate a graph or roadmap where the nodes represent collision-free configurations and the edges represent feasible paths between those configurations. PRMs typically consist of two phases: roadmap con- struction, where a roadmap is built, and query, where the start and goal configura- tions are connected to the roadmap and then a path is extracted using graph search techniques.