Browsing by Subject "Motion planning"
Now showing 1 - 7 of 7
Results Per Page
Sort Options
Item Analysis and synthesis of collaborative opportunistic navigation systems(2014-05) Kassas, Zaher; Humphreys, Todd Edwin; Arapostathis, Ari, 1954-Navigation is an invisible utility that is often taken for granted with considerable societal and economic impacts. Not only is navigation essential to our modern life, but the more it advances, the more possibilities are created. Navigation is at the heart of three emerging fields: autonomous vehicles, location-based services, and intelligent transportation systems. Global navigation satellite systems (GNSS) are insufficient for reliable anytime, anywhere navigation, particularly indoors, in deep urban canyons, and in environments under malicious attacks (e.g., jamming and spoofing). The conventional approach to overcome the limitations of GNSS-based navigation is to couple GNSS receivers with dead reckoning sensors. A new paradigm, termed opportunistic navigation (OpNav), is emerging. OpNav is analogous to how living creatures naturally navigate: by learning their environment. OpNav aims to exploit the plenitude of ambient radio frequency signals of opportunity (SOPs) in the environment. OpNav radio receivers, which may be handheld or vehicle-mounted, continuously search for opportune signals from which to draw position and timing information, employing on-the-fly signal characterization as necessary. In collaborative opportunistic navigation (COpNav), multiple receivers share information to construct and continuously refine a global signal landscape. For the sake of motivation, consider the following problem. A number of receivers with no a priori knowledge about their own states are dropped in an environment comprising multiple unknown terrestrial SOPs. The receivers draw pseudorange observations from the SOPs. The receivers' objective is to build a high-fidelity signal landscape map of the environment within which they localize themselves in space and time. We then ask: (i) Under what conditions is the environment fully observable? (ii) In cases where the environment is not fully observable, what are the observable states? (iii) How would receiver-controlled maneuvers affect observability? (iv) What is the degree of observability of the various states in the environment? (v) What motion planning strategy should the receivers employ for optimal information gathering? (vi) How effective are receding horizon strategies over greedy for receiver trajectory optimization, and what are their limitations? (vii) What level of collaboration between the receivers achieves a minimal price of anarchy? This dissertation addresses these fundamental questions and validates the theoretical conclusions numerically and experimentally.Item Distributed motion planning algorithms for a collection of vehicles(Texas A&M University, 2004-09-30) Pargaonkar, Sudhir SharadraoUnmanned Vehicles (UVs) currently perform a variety of tasks critical to a military mission. In future, they are envisioned to have the ability to accomplish a mission co-operatively and effectively with limited fuel onboard. In particular, they must search for targets, classify the potential targets detected, attack the classified targets and perform an assessment of the damage done to the targets. In some cases, UVs are themselves munitions. The targets considered in this thesis are stationary. The problem considered in this thesis, referred to as the UV problem, is the allotment of tasks to each UV along with the sequence in which they must be performed so that a maximum number of tasks are accomplished collectively. The maneuverability constraints on the UV are accounted for by treating them as Dubin's vehicles. Since the UVs considered are disposable with life spans governed by their fuel capacity, it is imperative to use their life as efficiently as possible. Thus, we need to develop a fuel-optimal (equivalently, distance optimal) motion plan for the collection of UVs. As the number of tasks to be performed and the number of vehicles performing these tasks grow, the number of ways in which the set of tasks can be distributed among the UVs increases combinatorially. The tasks a UV is required to perform are also subject to timing constraints. A UV cannot perform certain tasks before completing others. We consider a simplified version of the UV problem and do not take into account the timing constraints on the tasks to be performed on targets. We use linear programming and graph theory to find a solution to this simplified UV problem; in the graph theory approach, we develop an algorithm which is a generalization of the solution procedures available to solve the Traveling Salesman Problem (TSP). We provide an example UV problem illustrating the solution procedure developed in this thesis.Item Generalized Sampling-Based Feedback Motion Planners(2012-02-14) Kumar, SandipThe motion planning problem can be formulated as a Markov decision process (MDP), if the uncertainties in the robot motion and environments can be modeled probabilistically. The complexity of solving these MDPs grow exponentially as the dimension of the problem increases and hence, it is nearly impossible to solve the problem even without constraints. Using hierarchical methods, these MDPs can be transformed into a semi-Markov decision process (SMDP) which only needs to be solved at certain landmark states. In the deterministic robotics motion planning community, sampling based algorithms like probabilistic roadmaps (PRM) and rapidly exploring random trees (RRTs) have been successful in solving very high dimensional deterministic problem. However they are not robust to system with uncertainties in the system dynamics and hence, one of the primary objective of this work is to generalize PRM/RRT to solve motion planning with uncertainty. We first present generalizations of randomized sampling based algorithms PRM and RRT, to incorporate the process uncertainty, and obstacle location uncertainty, termed as "generalized PRM" (GPRM) and "generalized RRT" (GRRT). The controllers used at the lower level of these planners are feedback controllers which ensure convergence of trajectories while mitigating the effects of process uncertainty. The results indicate that the algorithms solve the motion planning problem for a single agent in continuous state/control spaces in the presence of process uncertainty, and constraints such as obstacles and other state/input constraints. Secondly, a novel adaptive sampling technique, termed as "adaptive GPRM" (AGPRM), is proposed for these generalized planners to increase the efficiency and overall success probability of these planners. It was implemented on high-dimensional robot n-link manipulators, with up to 8 links, i.e. in a 16-dimensional state-space. The results demonstrate the ability of the proposed algorithm to handle the motion planning problem for highly non-linear systems in very high-dimensional state space. Finally, a solution methodology, termed the "multi-agent AGPRM" (MAGPRM), is proposed to solve the multi-agent motion planning problem under uncertainty. The technique uses a existing solution technique to the multiple traveling salesman problem (MTSP) in conjunction with GPRM. For real-time implementation, an ?inter-agent collision detection and avoidance? module was designed which ensures that no two agents collide at any time-step. Algorithm was tested on teams of homogeneous and heterogeneous agents in cluttered obstacle space and the algorithm demonstrate the ability to handle such problems in continuous state/control spaces in presence of process uncertainty.Item Improved manipulator configurations for grasping and task completion based on manipulability(2010-12) Williams, Joshua Murry; Pryor, Mitchell Wayne; Landsberger, SheldonWhen a robotic system executes a task, there are a number of responsibilities that belong to either the operator and/or the robot. A more autonomous system has more responsibilities in the completion of a task and must possess the decision making skills necessary to adequately deal with these responsibilities. The system must also handle environmental constraints that limit the region of operability and complicate the execution of tasks. There are decisions about the robot’s internal configuration and how the manipulator should move through space, avoid obstacles, and grasp objects. These motions usually have limits and performance requirements associated with them. Successful completion of tasks in a given environment is aided by knowledge of the robot’s capabilities in its workspace. This not only indicates if a task is possible but can suggest how a task should be completed. In this work, we develop a grasping strategy for selecting and attaining grasp configurations for flexible tasks in environments containing obstacles. This is done by sampling for valid grasping configurations at locations throughout the workspace to generate a task plane. Locations in the task plane that contain more valid configurations are stipulated to have higher dexterity and thus provide greater manipulability of targets. For valid configurations found in the plane, we develop a strategy for selecting which configurations to choose when grasping and/or placing an object at a given location in the workspace. These workspace task planes can also be utilized as a design tool to configure the system around the manipulator’s capabilities. We determine the quality of manipulator positioning in the workspace based on manipulability and locate the best location of targets for manipulation. The knowledge of valid manipulator configurations throughout the workspace can be used to extend the application of task planes to motion planning between grasping configurations. This guides the end-effector through more dexterous workspace regions and to configurations that move the arm away from obstacles. The task plane technique employed here accurately captures a manipulator’s capabilities. Initial tests for exploiting these capabilities for system design and operation were successful, thus demonstrating this method as a viable starting point for incrementally increasing system autonomy.Item Motion Planning for Unmanned Aerial Vehicles with Resource Constraints(2012-10-19) Sundar, KaarthikSmall Unmanned Aerial Vehicles (UAVs) are currently used in several surveillance applications to monitor a set of targets and collect relevant data. One of the main constraints that characterize a small UAV is the maximum amount of fuel the vehicle can carry. In the thesis, we consider a single UAV routing problem where there are multiple depots and the vehicle is allowed to refuel at any depot. The objective of the problem is to find a path for the UAV such that each target is visited at least once by the vehicle, the fuel constraint is never violated along the path for the UAV, and the total length of the path is a minimum. Mixed integer, linear programming formulations are proposed to solve the problem optimally. As solving these formulations to optimality may take a large amount of time, fast and efficient construction and improvement heuristics are developed to find good sub-optimal solutions to the problem. Simulation results are also presented to corroborate the performance of all the algorithms. In addition to the above contributions, this thesis develops an approximation algorithm for a multiple UAV routing problem with fuel constraints.Item Multi-robot Caravanning(2013-11-06) Mahadevan, AdityaWe study multi-robot caravanning, which is loosely defined as the problem of a heterogeneous team of robots visiting specific areas of an environment (waypoints) as a group. After formally defining this problem, we propose a novel solution that requires minimal communication and scales with the number of waypoints and robots. Our approach restricts explicit communication and coordination to occur only when robots reach waypoints, and relies on implicit coordination when moving between a given pair of waypoints. At the heart of our algorithm is the use of leader election to e?ciently exploit the unique environmental knowledge available to each robot in order to plan paths for the group, which makes it general enough to work with robots that have heterogeneous representations of the environment. We implement our approach both in simulation and on a physical platform, and characterize the performance of the approach under various scenarios. We demonstrate that our approach can successfully be used to combine the planning capabilities of di?erent agents.Item Phase space planning for robust locomotion(2013-08) Zhao, Ye, active 2013; Sentis, LuisManeuvering through 3D structures nimbly is pivotal to the advancement of legged locomotion. However, few methods have been developed that can generate 3D gaits in those terrains and fewer if none can be generalized to control dynamic maneuvers. In this thesis, foot placement planning for dynamic locomotion traversing irregular terrains is explored in three dimensional space. Given boundary values of the center of mass' apexes during the gait, sagittal and lateral Phase Plane trajectories are predicted based on multi-contact and inverted pendulum dynamics. To deal with the nonlinear dynamics of the contact motions and their dimensionality, we plan a geometric surface of motion beforehand and rely on numerical integration to solve the models. In particular, we combine multi-contact and prismatic inverted pendulum models to resolve feet transitions between steps, allowing to produce trajectory patterns similar to those observed in human locomotion. Our contributions lay in the following points: (1) the introduction of non planar surfaces to characterize the center of mass' geometric behavior; (2) an automatic gait planner that simultaneously resolves sagittal and lateral feet placements; (3) the introduction of multi-contact dynamics to smoothly transition between steps in the rough terrains. Data driven methods are powerful approaches in absence of accurate models. These methods rely on experimental data for trajectory regression and prediction. Here, we use regression tools to plan dynamic locomotion in the Phase Space of the robot's center of mass and we develop nonlinear controllers to accomplish the desired plans with accuracy and robustness. In real robotic systems, sensor noise, simplified models and external disturbances contribute to dramatic deviations of the actual closed loop dynamics with respect to the desired ones. Moreover, coming up with dynamic locomotion plans for bipedal robots and in all terrains is an unsolved problem. To tackle these challenges we propose here two robust mechanisms: support vector regression for data driven model fitting and contact planning, and trajectory based sliding mode control for accuracy and robustness. First, support vector regression is utilized to learn the data set obtained through numerical simulations, providing an analytical solution to the nonlinear locomotion dynamics. To approximate typical Phase Plane behaviors that contain infinite slopes and loops, we propose to use implicit fitting functions for the regression. Compared to mainstream explicit fitting methods, our regression method has several key advantages: 1) it models high dimensional Phase Space states by a single unified implicit function; 2) it avoids trajectory over-fitting; 3) it guarantees robustness to noisy data. Finally, based on our regression models, we develop contact switching plans and robust controllers that guarantee convergence to the desired trajectories. Overall, our methods are more robust and capable of learning complex trajectories than traditional regression methods and can be easily utilized to develop trajectory based robust controllers for locomotion. Various case studies are analyzed to validate the effectiveness of our methods including single and multi step planning in a numerical simulation and swing foot trajectory control on our Hume bipedal robot.