Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
9 results
Search Results
Item FAST FEASIBLE MOTION PLANNING WITHOUT TWO-POINT BOUNDARY VALUE SOLUTION(2023) Nayak, Sharan Harish; Otte, Michael; Aerospace Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Autonomous robotic systems have seen extensive deployment across domains such as manufacturing, industrial inspection, transportation, and planetary surface exploration. A crucial requirement for these systems is navigating from an initial to a final position, while avoiding potential collisions with obstacles en route. This challenging task of devising collision-free trajectories, formally termed as motion planning, is of prime importance in robotics. Traditional motion planning approaches encounter scalability challenges when planning in higher-dimensional state-spaces. Moreover, they rarely consider robot dynamics during the planning process. To address these limitations, a class of probabilistic planning methods called Sampling-Based Motion Planning (SBMP) has gained prominence. SBMP strategies exploit probabilistic techniques to construct motion planning solutions. In this dissertation, our focus turns towards feasible SBMP algorithms that prioritize rapidly discovering solutions while considering robot kinematics and dynamics. These algorithms find utility in quickly solving complex problems (e.g., Alpha puzzle) where obtaining any feasible solution is considered as an achievement. Furthermore, they find practical use in computationally constrained systems and in seeding time-consuming optimal solutions. However, many existing feasible SBMP approaches assume the ability to find precise trajectories that exactly connect two states in a robot's state space. This challenge is framed as the Two-Point Boundary Value Problem (TPBVP). But finding closed-form solutions for the TPBVP is difficult, and numerical approaches are computationally expensive and prone to precision and stability issues. Given these complexities, this dissertation's primary focus resides in the development of SBMP algorithms for different scenarios where solving the TPBVP is challenging. Our work addresses four distinct scenarios -- two for single-agent systems and two for multi-agent systems. The first single-agent scenario involves quickly finding a feasible path from the start to goal state, using bidirectional search strategies for fast solution discovery. The second scenario focuses on performing prompt motion replanning when a vehicle's dynamical constraints change mid-mission. We leverage the heuristic information from the original search tree constructed using the vehicle's nominal dynamics to speed up the replanning process. Both these two scenarios unfold in static environments with pre-known obstacles. Transitioning to multi-agent systems, we address the feasible multi-robot motion planning problem where a robot team is guided towards predefined targets in a partially-known environment. We employ a dynamic roadmap updated from the current known environment to accelerate agent planning. Lastly, we explore the problem of multi-robot exploration in a completely unknown environment applied to the CADRE mission. We demonstrate how our proposed bidirectional search strategies can facilitate efficient exploration for robots with significant dynamics. The effectiveness of our algorithms is validated through extensive simulation and real-world experiments.Item Exact and Heuristic Methods for Emerging Vehicle Routing Problems(2022) Oden, Eric John; Golden, Bruce; Raghavan, S.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The rise of global supply chains and e-commerce in recent decades have intensified the relevance of the transportation industry to both the individual and the economy. With rising consumer expectations and slim profit margins, the various sectors within the transportation industry rely on the development of carefully designed routes to remain competitive. Despite the wealth of research on route design, and the responsiveness of the research community to practical considerations, there remain gaps between the work done in practice and that appearing in the literature. Correspondingly, the work in this dissertation is directly in response to conversations had with contacts from real-world companies within the transportation domain. We consider problems presented, verbally, by companies representing three distinct segments of the industry: freight routing, last-mile delivery, and on-demand passenger transport. Each problem is centered around an innovative strategy with the potential to dramatically disrupt its corresponding domain. First, we consider the Shared Truckload (STL) freight shipping model, an alternative to the dominant Less-than-Truckload (LTL) model. Both models pool shipments from multiple customers into a single trailer, but, in the latter, consolidation is facilitated by a hub-and-spoke routing network, whereas, in the the former, freight moves directly from origin to destination. This strategy minimizes travel times and the risk of damage. We then investigate a novel strategy to facilitate last-mile, last-minute delivery, through coordinating a fleet of trucks and a fleet of smaller vehicles, referred to as shuttles. In order to accommodate requests which come in after trucks have been dispatched, shuttles are allowed to pick up packages from a depot and intercept trucks along their routes. This strategy can enable a shipper to make highly competitive service guarantees. Finally, we consider the emerging field of Urban Air Mobility (UAM), a vision of air taxis conveying passengers at lower altitudes throughout urban areas as an efficient alternative to gridlock traffic. In particular, we consider a UAM service company in the early stages of its development, where the chief goal is to maximize market share. These innovations represent significant deviations from the status quo in their respective fields, and, thus, the existing research for each is slim, if existent. Therefore, we introduce precise mathematical formulations of each of the problems to the research community. We then develop both exact and heuristic approaches to solve the problems, and carry out extensive computational studies comparing the solution methodologies. Furthermore, for each of the problems, we offer a sensitivity analysis and managerial insights. Among our contributions are original algorithms based on solving a set-partitioning formulations via column generation, a highly successful paradigm for solving large linear programs. Among the advantages of this approach is the ability to include highly general route costs and constraints. We illustrate this expressiveness by demonstrating its application to each of the three highly distinct problems we consider.Item Mathematical Programming and Heuristic Approaches for Three Novel Vehicle Routing Problems(2022) Luo, Yuchen; Golden, Bruce; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Vehicle routing problems (VRPs) arise in key real-world domains including mail delivery, police patrol, and snow plowing. Due to the inherent complexity of the VRP, no algorithm currently exists that can solve the VRP exactly in polynomial time. In the meantime, high quality solutions are needed to tackle challenging issues such as rising mail and package delivery costs and surging crime rates. In this dissertation, we design efficient routing solutions for three applications of the VRP. First, we consider the application of the hot spot police patrol, where hot spots refer to locations with high crime rates. We examine the routing problem for a patrol car that visits locations in a region and remains close to the center of the region modeling a high-crime neighborhood (HCN). We formulate this problem as the traveling salesman problem with a center (TSPC), in which we minimize an energy function including L (the length of a tour) and C (the distance from a tour to the center, defined by some metric). To address the TSPC, we propose a metric to measure C rather accurately and also introduce the idea of a triangular path, in which the patrol car no longer travels in a straight line between two nodes. We show that under identical circumstances, the tour with triangular paths remains closer to the center than a tour using all direct edges in both a Euclidean graph and a grid network. Second, we extend the hot spot police patrol to a fleet of patrol cars. Given the disorder and chaos in the HCN, we require at least one patrol car in the HCN at any given time during the patrol. We call this routing problem the hot spot coverage patrol problem (HSCPP). In the HSCPP, the importance of a patrol location is quantified by a prize and our objective is to maximize the sum of prizes collected by the patrol cars while obeying all operations requirements. We propose mathematical formulations and develop several solution approaches for the HSCPP. These solution approaches are based on integer programming and column generation. We then conduct a detailed computational study to compare these approaches using real crime data from Montgomery County, Maryland. We point out the best solution approaches in terms of optimality gap, runtime, and workload balancing. Third, we consider mail deliveries. To reduce the fleet size and carbon emissions of a postal service, we allow two mail carriers per truck. We call this problem the paired mail carrier problem (PMCP). Our objective is to minimize the route completion time while ensuring that each service stop is fully serviced and obeys all feasibility constraints. We develop a mixed integer programming formulation and two fast heuristics for the PMCP. We evaluate the impact of the paired mail carriers (PMC) setting on both a one-truck situation and a fleet (multiple trucks) situation, relative to the single mail carrier (SMC) setting. Overall, the PMC setting can not only accomplish over 50% more work within the same shift hours but can also lead to a 22% cost savings.Item Non-Investor Stakeholders and Earnings Benchmarks(2017) Wei, Sijing; Kimbrough, Michael D.; Business and Management: Accounting & Information Assurance; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)ABSTRACT A firm has numerous non-investor stakeholders, such as customers, employees, and potential business partners, who provide needed monetary and nonmonetary support to the firm. In Essay One, I provide empirical evidence on the previously untested theoretical prediction that these stakeholders’ views of a firm depend on its ability to meet relevant earnings benchmarks. Using published and proprietary reputation scores to capture stakeholder perceptions, I find in both levels and changes analyses that non-investor stakeholder perceptions are positively associated with a firm’s ability to beat relevant earnings benchmarks and that the relevant earnings benchmark for each stakeholder group varies based on the nature of its claim. Specifically, customer perceptions are positively associated with a firm’s ability to meet the profit benchmark. Potential business partner perceptions are positively associated with a firm’s ability to meet both the analyst forecast benchmark and the earnings growth benchmark. Employee perceptions are positively associated with a firm’s ability to meet the earnings growth benchmark. These findings highlight broader uses of and broader audiences for accounting information than previously documented. In Essay Two, I examine whether and how firms consider their non-investor stakeholders when prioritizing which earnings benchmarks to meet or beat. Using a sample of publicly traded firms from 1990 to 2015, I identify which non-investor stakeholder group (i.e. consumers, employees, or potential business partners) is most critical to a firm based on a stakeholder dependency score, which measures the extent to which a firm relies on a particular stakeholder group. I find that, regardless of which non-investor stakeholder group is most critical to the firm, firms beat the analyst forecast benchmark several times more frequently than they beat other benchmarks. Because the analyst forecast is the most important benchmark to the capital market, this finding indicates that managers place greater weight on investors’ preferences than on the preferences of their non-investor stakeholders when deciding which earnings benchmarks to meet or beat. Thus, capital market pressure appears to dominate the pressure from non-investor stakeholders. However, I also find that consumer-focused (employee-focused) firms meet or beat the profit benchmark (the increase benchmark) more often than non-consumer-focused firms (non-employee-focused firms) when the profit benchmark (the increase benchmark) is the most difficult to beat or when pre-managed earnings falls short of the associated benchmark. These results indicate that firms are more likely to meet or beat the specific earnings benchmark that is most relevant to a particular non-investor stakeholder group when that non-investor stakeholder group is most critical to the firm. These findings contribute to a better understanding of how managers incorporate non-investor stakeholders’ preferences in their decisions about which earnings benchmarks to meet or beat.Item Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results(2016) Wang, Xingyin; Golden, Bruce; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.Item Hierarchical Goal Networks: Formalisms and Algorithms for Planning and Acting(2015) Shivashankar, Vikas; Nau, Dana S; Computer Science; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In real-world applications of AI and automation such as in robotics, computer game playing and web-services, agents need to make decisions in unstructured environments that are open-world, dynamic and partially observable. In the AI and Robotics research communities in particular, there is much interest in equipping robots to operate with minimal human intervention in diverse scenarios such as in manufacturing plants, homes, hospitals, etc. Enabling agents to operate in these environments requires advanced planning and acting capabilities, some of which are not well supported by the current state of the art automated planning formalisms and algorithms. To address this problem, in my thesis I propose a new planning formalism that addresses some of the inadequacies in current planning frameworks, and a suite of planning and acting algorithms that operate under this planning framework. The main contributions of this thesis are: - Hierarchical Goal Network (HGN) Planning Formalism. This planning formalism combines aspects (and therefore harnesses advantages) of Classical Planning and Hierarchical Task Network (HTN) Planning, two of the most prominent planning formalisms currently in use. In particular, HGN planning algorithms, while retaining the efficiency and scalability advantages of HTNs, also allows incorporation of heuristics and other reasoning techniques from Classical Planning. - Planning Algorithms. Goal Decomposition Planner (GDP) and the Goal Decomposition with Landmarks (GoDeL) planner are two HGN planning algorithms that combines hierarchical decomposition with classical planning heuristics to outperform state-of-the-art HTN planners like SHOP and SHOP2. - Integration with Robotics. The Combined HGN and Motion Planning (CHaMP) algorithm integrates GoDeL with low-level motion and manipulation planning algorithms in Robotics to generate plans directly executable by robots. Given the need for autonomous agents to operate in open, dynamic and unstructured environments and the obvious need for high-level deliberation capabilities to enable intelligent behavior, the planning-and-acting systems that are developed as part of this thesis may provide unique insights into ways to realize these systems in the real world.Item Integer Programming-Based Heuristics for Vehicle Routing Problems(2010) Gulczynski, Damon John; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The vehicle routing problem (VRP) has been an active field of study by operations researchers for over 50 years. Many practical applications have been presented in the literature, and many solution techniques have been developed. We discuss, develop, and computationally test integer programming-based heuristics for several variants of the standard VRP. We use integer programming to model the split delivery VRP with minimum delivery amounts, the multi-depot split delivery VRP, the period VRP, the standard VRP, and the multi-depot VRP. We apply our heuristics to benchmark problems from the literature and generate many new problems with high-quality, visually-estimated solutions. Our heuristics produce high-quality solutions in a reasonable amount of computer time. Overall, our new IP-based heuristics are very competitive with the best methods found in the VRP literature to date.Item Parallel and Serial Algorithms for Vehicle Routing Problems(2008) Groer, Christopher Sebastian; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The vehicle routing problem (VRP) is a widely studied combinatorial optimization problem that has many applications. Due to its intrinsic difficulty and the size of problems encountered in practice, most solution methods for the VRP are heuristic in nature and lead to high quality, yet probably not optimal solutions. When one considers the additional constraints that can be encountered in practice, the need for high quality heuristic methods is clear. We present two new variations of the VRP suggested to us by industry contacts, the Consistent VRP and the Balanced Billing Cycle VRP. We develop solution algorithms that incorporate heuristic methods as well as integer programming. Additionally, we develop a highly effective cooperative parallel algorithm for the classical VRP that generates new best solutions to a number of well-studied benchmark instances. We present extensive computational results and describe the C/C++ library that we developed to solve these vehicle routing problems. We describe the features and design philosophy behind this library and discuss how the framework can be used to implement additional heuristic algorithms and incorporate additional constraints.Item Weight Annealing Heuristics for Solving Bin Packing and other Combinatorial Optimization Problems: Concepts, Algorithms and Computational Results(2006-10-23) Loh, Kok-Hua; Golden, Bruce L.; Decision and Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The application of weight annealing to combinatorial optimization problems is relatively new, compared to applications of well-known optimization techniques such as simulated annealing and tabu search. The weight annealing approach seeks to expand a neighborhood search by creating distortions in different parts of the search space. Distortion is controlled through weight assignment based on insights gained from one iteration of the search procedure to the next with a view towards focusing computational efforts on the poorly solved regions of the search space. The search for the global optimum should be accelerated and the solution quality should be improved with weight annealing. In this dissertation, we present key ideas behind weight annealing and develop algorithms that solve combinatorial optimization problems. Our weight annealing-based heuristics solve the one-dimensional bin packing problem and the two-dimensional bin packing problem with and without guillotine cutting and item orientation constraints. We also solve the maximum cardinality bin packing problem and the multidimensional multiple knapsack problem with our heuristics.