A. James Clark School of Engineering

Permanent URI for this communityhttp://hdl.handle.net/1903/1654

The collections in this community comprise faculty research works, as well as graduate theses and dissertations.

Browse

Subject: search.filters.subject.path planning

Search Results

Now showing 1 - 6 of 6
  • Thumbnail Image
    Item
    Multipass Target Search in Natural Environments
    (MDPI, 2017-11-02) Kuhlman, Michael J.; Otte, Michael W.; Sofge, Donald; Gupta, Satyandra K.
    Consider a disaster scenario where search and rescue workers must search difficult to access buildings during an earthquake or flood. Often, finding survivors a few hours sooner results in a dramatic increase in saved lives, suggesting the use of drones for expedient rescue operations. Entropy can be used to quantify the generation and resolution of uncertainty. When searching for targets, maximizing mutual information of future sensor observations will minimize expected target location uncertainty by minimizing the entropy of the future estimate. Motion planning for multi-target autonomous search requires planning over an area with an imperfect sensor and may require multiple passes, which is hindered by the submodularity property of mutual information. Further, mission duration constraints must be handled accordingly, requiring consideration of the vehicle’s dynamics to generate feasible trajectories and must plan trajectories spanning the entire mission duration, something which most information gathering algorithms are incapable of doing. If unanticipated changes occur in an uncertain environment, new plans must be generated quickly. In addition, planning multipass trajectories requires evaluating path dependent rewards, requiring planning in the space of all previously selected actions, compounding the problem. We present an anytime algorithm for autonomous multipass target search in natural environments. The algorithm is capable of generating long duration dynamically feasible multipass coverage plans that maximize mutual information using a variety of techniques such as 𝜖-admissible heuristics to speed up the search. To the authors’ knowledge this is the first attempt at efficiently solving multipass target search problems of such long duration. The proposed algorithm is based on best first branch and bound and is benchmarked against state of the art algorithms adapted to the problem in natural Simplex environments, gathering the most information in the given search time.
  • Thumbnail Image
    Item
    Trajectory Planning for Autonomous Vehicles Performing Information Gathering Tasks
    (2018) Kuhlman, Michael Joseph; Gupta, Satyandra K; Mechanical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation investigates mission scenarios for autonomous vehicles in which the objective is to gather information. This includes minimizing uncertainty of a target's estimated location, generating coverage plans to cover an area, or persistent monitoring tasks such as generating informative patrol routes. Information gathering tasks cannot be solved with shortest path planning algorithms since the rewards are path-dependent. Further, in order to deploy such algorithms effectively in the real world, generated plans must safely avoid obstacles, account for the motion uncertainty (e.g. due to swift currents), and constraints on the vehicle's dynamics such as maximum speed/acceleration. This work extends state-of-the-art information gathering algorithms by generating dynamically feasible trajectories for autonomous vehicles that are able to exploit the environment to find higher quality solutions, reducing mission costs. We also reduce mission risk without sacrificing the amount of information gathered. The focus of this dissertation will be to solve three related information gathering tasks that require generating dynamically feasible trajectories for reliable plan execution. When searching for targets, minimizing target location uncertainty with autonomous vehicles improves the effectiveness of ground relief crews. We investigate the use of mutual information for efficiently generating long duration multi-pass trajectories to minimize target location uncertainty in natural environments. We develop epsilon-admissible heuristics to create the epsilon-admissible Branch and Bound algorithm to gather the most information. Next, we investigate coordination techniques for underwater vehicle teams conducting large-scale geospatial tasks such as adaptive sampling or coverage planning. It is advantageous to exploit the currents of the ocean to increase endurance, which requires accounting for forecast uncertainty. We adapt Monte Carlo Tree Search and Cross Entropy Method to maximize path-dependent reward, and introduce an iterative greedy solver that outperforms state-of-the-art planners. Finally, we investigate persistent monitoring tasks such as sentry patrol routes and monitoring of harmful algae blooms in a littoral environment. Such an automated planner needs to generate collision-free coverage paths by moving waypoints to locations that both minimize path traversal costs and maximize the amount of information gathered along the path. We extend previous Lloyd's based algorithms by factoring in the ocean currents and introduce greedy methods that minimize mission risk while maximizing information gathered.
  • Thumbnail Image
    Item
    Multipass Target Search in Natural Environments
    (MDPI, 2017-11-02) Kuhlman, Michael J.; Otte, Michael W.; Sofge, Donald; Gupta, Satyandra K.
    Consider a disaster scenario where search and rescue workers must search difficult to access buildings during an earthquake or flood. Often, finding survivors a few hours sooner results in a dramatic increase in saved lives, suggesting the use of drones for expedient rescue operations. Entropy can be used to quantify the generation and resolution of uncertainty. When searching for targets, maximizing mutual information of future sensor observations will minimize expected target location uncertainty by minimizing the entropy of the future estimate. Motion planning for multi-target autonomous search requires planning over an area with an imperfect sensor and may require multiple passes, which is hindered by the submodularity property of mutual information. Further, mission duration constraints must be handled accordingly, requiring consideration of the vehicle’s dynamics to generate feasible trajectories and must plan trajectories spanning the entire mission duration, something which most information gathering algorithms are incapable of doing. If unanticipated changes occur in an uncertain environment, new plans must be generated quickly. In addition, planning multipass trajectories requires evaluating path dependent rewards, requiring planning in the space of all previously selected actions, compounding the problem. We present an anytime algorithm for autonomous multipass target search in natural environments. The algorithm is capable of generating long duration dynamically feasible multipass coverage plans that maximize mutual information using a variety of techniques such as e-admissible heuristics to speed up the search. To the authors’ knowledge this is the first attempt at efficiently solving multipass target search problems of such long duration. The proposed algorithm is based on best first branch and bound and is benchmarked against state of the art algorithms adapted to the problem in natural Simplex environments, gathering the most information in the given search time.
  • Thumbnail Image
    Item
    Path planning, flow estimation, and dynamic control for underwater vehicles
    (2017) Lagor Jr., Francis Dennis; Paley, Derek A; Aerospace Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    Underwater vehicles such as robotic fish and long-endurance ocean-sampling platforms operate in challenging fluid environments. This dissertation incorporates models of the fluid environment in the vehicles' guidance, navigation, and control strategies while addressing uncertainties associated with estimates of the environment's state. Coherent flow structures may be on the same spatial scale as the vehicle or substantially larger than the vehicle. This dissertation argues that estimation and control tasks across widely varying spatial scales, from vehicle-scale to long-range, may be addressed using common tools of empirical observability analysis, nonlinear/non-Gaussian estimation, and output-feedback control. As an application in vehicle-scale flow estimation and control, this dissertation details the design, fabrication, and testing of a robotic fish with an artificial lateral-line inspired by the lateral-line flow-sensing organ present in fish. The robotic fish is capable of estimating the flow speed and relative angle of the oncoming flow. Using symmetric and asymmetric sensor configurations, the robot achieves the primitive fish behavior called rheotaxis, which describes a fish's tendency to orient upstream. For long-range flow estimation and control, path planning may be accomplished using observability-based path planning, which evaluates a finite set of candidate control inputs using a measure related to flow-field observability and selects an optimizer over the set. To incorporate prior information, this dissertation derives an augmented observability Gramian using an optimal estimation strategy known as Incremental 4D-Var. Examination of the minimum eigenvalue of an empirical version of this Gramian yields a novel measure for path planning, called the empirical augmented unobservability index. Numerical experiments show that this measure correctly selects the most informative paths given the prior information. As an application in long-range flow estimation and control, this dissertation considers estimation of an idealized pair of ocean eddies by an adaptive Lagrangian sensor (i.e., a platform that uses its position data as measurements of the fluid transport, after accounting for its own control action). The adaptive sampling is accomplished using the empirical augmented unobservability index, which is extended to non-Gaussian posterior densities using an approximate expected-cost calculation. Output feedback recursively improves estimates of the vehicle position and flow-field states.
  • Thumbnail Image
    Item
    Precise steering of particles in electroosmotically actuated microfluidic devices
    (2010) Chaudhary, Satej; Shapiro, Benjamin; Aerospace Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    In this thesis, we show how to combine microfluidics and feedback control to independently steer multiple particles with micrometer accuracy in two dimensions. The particles are steered by creating a fluid flow that carries all the particles from where they are to where they should be at each time step. Our control loop comprises sensing, computation, and actuation to steer particles along user-input trajectories. Particle positions are identified in real-time by an optical system and transferred to a control algorithm that then determines the electrode voltages necessary to create a flow field to carry all the particles to their next desired locations. The process repeats at the next time instant. Our method achieves inexpensive steering of particles by using conventional electroosmotic actuation in microfluidic channels. This type of particle steering has significant advantages over other particle steering methods, such as laser tweezers. (Laser tweezers cannot steer reflective particles, or particles where the index of refraction is lower than (or for more sophisticated optical vortex holographic tweezers does not differ substantially from) that of the surrounding medium.). In this thesis, we address three specific aspects of this technology. First, we develop the control algorithms for steering multiple particles independently and validate our control techniques using simulations with realistic sources of initial position errors and system uncertainties. Second, we develop optimal path planning methods to efficiently steer particles between given initial and final positions. Third, we design high performance microfluidic devices that are capable of simultaneously steering five particles in experiment.
  • Thumbnail Image
    Item
    Real-Time Terminal Area Trajectory Planning for Runway Independent Aircraft
    (2006-01-24) Xue, Min; Atkins, Ella M; Aerospace Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    The increasing demand for commercial air transportation results in delays due to traffic queues that form bottlenecks along final approach and departure corridors. In urban areas, it is often infeasible to build new runways, and regardless of automation upgrades traffic must remain separated to avoid the wakes of previous aircraft. Vertical or short takeoff and landing aircraft as Runway Independent Aircraft (RIA) can increase passenger throughput at major urban airports via the use of vertiports or stub runways. The concept of simultaneous non-interfering (SNI) operations has been proposed to reduce traffic delays by creating approach and departure corridors that do not intersect existing fixed-wing routes. However, SNI trajectories open new routes that may overfly noise-sensitive areas, and RIA may generate more noise than traditional jet aircraft, particularly on approach. In this dissertation, we develop efficient SNI noise abatement procedures applicable to RIA. First, we introduce a methodology based on modified approximated cell-decomposition and Dijkstra's search algorithm to optimize longitudinal plane (2-D) RIA trajectories over a cost function that minimizes noise, time, and fuel use. Then, we extend the trajectory optimization model to 3-D with a k-ary tree as the discrete search space. We incorporate geography information system (GIS) data, specifically population, into our objective function, and focus on a practical case study: the design of SNI RIA approach procedures to Baltimore-Washington International airport. Because solutions were represented as trim state sequences, we incorporated smooth transition between segments to enable more realistic cost estimates. Due to the significant computational complexity, we investigated alternative more efficient optimization techniques applicable to our nonlinear, non-convex, heavily constrained, and discontinuous objective function. Comparing genetic algorithm (GA) and adaptive simulated annealing (ASA) with our original Dijkstra's algorithm, ASA is identified as the most efficient algorithm for terminal area trajectory optimization. The effects of design parameter discretization are analyzed, with results indicating a SNI procedure with 3-4 segments effectively balances simplicity with cost minimization. Finally, pilot control commands were implemented and generated via optimization-base inverse simulation to validate execution of the optimal approach trajectories.