Browsing by Author "Hildebrand, Robert"

Now showing 1 - 11 of 11
  • Thumbnail Image
    Asymmetries in Potential for Partisan Gerrymandering
    Goedert, Nicholas; Hildebrand, Robert; Travis, Laurel; Pierson, Matthew (2024)
    This paper investigates the effectiveness of potential partisan gerrymandering of the U.S. House of Representatives across a range of states. We use a heuristic algorithm to generate district maps that optimize for multiple objectives, including compactness, partisan benefit, and competitiveness. While partisan gerrymandering is highly effective for both sides, we find that the majority of states are moderately biased toward Republicans when optimized for either compactness or partisan benefit, meaning that Republican gerrymanders have the potential to be more effective. However, we also find that more densely populated and more heavily Hispanic states show less Republican bias or even Democratic bias. Additionally, we find that in almost all cases we can generate reasonably compact maps with very little sacrifice to partisan objectives through a mixed objective function. This suggests that there is a strong potential for stealth partisan gerrymanders that are both compact and beneficial to one party. Nationwide, partisan gerrymandering is capable of swinging over one hundred seats in the U.S. House, even when compact districts are simultaneously sought.
  • Thumbnail Image
    An Autonomous Task Assignment Paradigm for Autonomous Robotic In-Space Assembly
    Hildebrand, Robert; Komendera, Erik; Moser, Joshua; Hoffman, Julia (Frontiers, 2022-02-25)
    The development of autonomous robotic systems is a key component in the expansion of space exploration and the development of infrastructures for in-space applications. An important capability for these robotic systems is the ability to maintain and repair structures in the absence of human input by autonomously generating valid task sequences and task to robot allocations. To this end, a novel stochastic problem formulation paired with a mixed integer programming assembly schedule generator has been developed to articulate the elements, constraints, and state of an assembly project and solve for an optimal assembly schedule. The developed formulations were tested with a set of hardware experiments that included generating an optimal schedule for an assembly and rescheduling during an assembly to plan a repair. This formulation and validation work provides a path forward for future research in the development of an autonomous system capable of building and maintaining in-space infrastructures.
  • Thumbnail Image
    Continuous Equality Knapsack with Probit-Style Objectives
    Fravel, Jamie; Hildebrand, Robert; Travis, Laurel (2022-11-04)
    We study continuous, equality knapsack problems with uniform separable, non-convex objective functions that are continuous, strictly increasing, antisymmetric about a point, and have concave and convex regions. For example, this model captures a simple allocation problem with the goal of optimizing an expected value where the objective is a sum of cumulative distribution functions of identically distributed normal distributions (i.e., a sum of inverse probit functions). We prove structural results of this model under general assumptions and provide two algorithms for efficient optimization: (1) running in linear time and (2) running in a constant number of operations given preprocessing of the objective function.
  • Thumbnail Image
    Discrete Approximations, Relaxations, and Applications in Quadratically Constrained Quadratic Programming
    Beach, Benjamin Josiah (Virginia Tech, 2022-05-02)
    We present works on theory and applications for Mixed Integer Quadratically Constrained Quadratic Programs (MIQCQP). We introduce new mixed integer programming (MIP)-based relaxation and approximation schemes for general Quadratically Constrained Quadratic Programs (QCQP's), and also study practical applications of QCQP's and Mixed-integer QCQP's (MIQCQP). We first address a challenging tank blending and scheduling problem regarding operations for a chemical plant. We model the problem as a discrete-time nonconvex MIQCP, then approximate this model as a MILP using a discretization-based approach. We combine a rolling horizon approach with the discretization of individual chemical property specifications to deal with long scheduling horizons, time-varying quality specifications, and multiple suppliers with discrete arrival times. Next, we study optimization methods applied to minimizing forces for poses and movements of chained Stewart platforms (SPs). These SPs are parallel mechanisms that are stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. The robot will be used in concert with several other types robots to perform complex assembly missions in space. We develop algorithms and optimization models that can efficiently decide on favorable poses and movements that reduce force loads on the robot, hence reducing wear on this machine, and allowing for a larger workspace and a greater overall payload capacity. In the third work, we present a technique for producing valid dual bounds for nonconvex quadratic optimization problems. The approach leverages an elegant piecewise linear approximation for univariate quadratic functions and formulate this approximation using mixed-integer programming (MIP). Combining this with a diagonal perturbation technique to convert a nonseparable quadratic function into a separable one, we present a mixed-integer convex quadratic relaxation for nonconvex quadratic optimization problems. We study the strength (or sharpness) of our formulation and the tightness of its approximation. We computationally demonstrate that our model outperforms existing MIP relaxations, and on hard instances can compete with state-of-the-art solvers. Finally, we study piecewise linear relaxations for solving quadratically constrained quadratic programs (QCQP's). We introduce new relaxation methods based on univariate reformulations of nonconvex variable products, leveraging the relaxation from the third work to model each univariate quadratic term. We also extend the NMDT approach (Castro, 2015) to leverage discretization for both variables in a bilinear term, squaring the resulting precision for the same number of binary variables. We then present various results related to the relative strength of the various formulations.
  • Thumbnail Image
    Embeddings for Disjunctive Programs with Applications to Political Districting and Rectangle Packing
    Fravel III, William James (Virginia Tech, 2024-11-08)
    This dissertations represents a composite of three papers which have been submitted for publication: The first chapter deals with a non-convex knapsack which is inspired by a simplified political districting problem. We present and derive a constant time solution to the problem via a reduced-dimensional reformulation, the Karash-Kuhn-Tucker optimality conditions, and gradient descent. The second chapter covers a more complete form of the political districting problem. We attempt to overcome the non-convex objective function and combinatorially massive solution space through a variety of linearization techniques and cutting planes. Our focus on dual bounds is novel in the space. The final chapter develops a framework for identifying ideal mixed binary linear programs and applies it to several rectangle packing formulations. These include both existing and novel formulations for the underlying disjunctive program. Additionally, we investigate the poor performance of branch-and-cut on the example problems.
  • Thumbnail Image
    Force-Controlled Pose Optimization and Trajectory Planning for Chained Stewart Platforms
    Beach, Benjamin; Chapin, William; Glassner, Samantha; Hildebrand, Robert; Komendera, Erik (Frontiers, 2023-11-24)
    Introduction: We study optimization methods for poses and movements of chained Stewart platforms (SPs) that we call an “Assembler” Robot. These chained SPs are parallel mechanisms that are stronger, stiffer, and more precise, on average, than their serial counterparts at the cost of a smaller range of motion. By linking these units in a series, their individual limitations are overcome while maintaining truss-like rigidity. This opens up potential uses in various applications, especially in complex space missions in conjunction with other robots. Methods: To enhance the efficiency and longevity of the Assembler Robot, we developed algorithms and optimization models. The main goal of these methodologies is to efficiently decide on favorable positions and movements that reduce force loads on the robot, consequently minimizing wear. Results: The optimized maneuvers of the interior plates of the Assembler result in more evenly distributed load forces through the legs of each constituent SP. This optimization allows for a larger workspace and a greater overall payload capacity. Our computations primarily focus on assemblers with four chained SPs. Discussion: Although our study primarily revolves around assemblers with four chained SPs, our methods are versatile and can be applied to an arbitrary number of SPs. Furthermore, these methodologies can be extended to general over-actuated truss-like robot architectures. The Assembler, designed to function collaboratively with several other robots, holds promise for a variety of space missions.
  • Thumbnail Image
    Online Machine Learning for Wireless Communications: Channel Estimation, Receive Processing, and Resource Allocation
    Li, Lianjun (Virginia Tech, 2023-07-03)
    Machine learning (ML) has shown its success in many areas such as computer vision, natural language processing, robot control, and gaming. ML also draws significant attention in the wireless communication society. However, applying ML schemes to wireless communication networks is not straightforward, there are several challenges need to addressed: 1). Training data in communication networks, especially in physical and MAC layer, are extremely limited; 2). The high-dynamic wireless environment and fast changing transmission schemes in communication networks make offline training impractical; 3). ML tools are treated as black boxes, which lack of explainability. This dissertation tries to address those challenges by selecting training-efficient neural networks, devising online training frameworks for wireless communication scenarios, and incorporating communication domain knowledge into the algorithm design. Training-efficient ML algorithms are customized for three communication applications: 1). Symbol detection, where real-time online learning-based symbol detection algorithms are designed for MIMO-OFDM and massive MIMO-OFDM systems by utilizing reservoir computing, extreme learning machine, multi-mode reservoir computing, and StructNet; 2) Channel estimation, where residual learning-based offline method is introduced for WiFi-OFDM systems, and a StructNet-based online method is devised for MIMO-OFDM systems; 3) Radio resource management, where reinforcement learning-based schemes are designed for dynamic spectrum access, as well as ORAN intelligent network slicing management. All algorithms introduced in this dissertation have demonstrated outstanding performance in their application scenarios, which paves the path for adopting ML-based solutions in practical wireless networks.
  • Thumbnail Image
    A Real-Time Computer Vision Based Framework For Urban Traffic Safety Assessment and Driver Behavior Modeling Using Virtual Traffic Lanes
    Abdelhalim, Awad Tarig (Virginia Tech, 2021-10-07)
    Vehicle recognition and trajectory tracking plays an integral role in many aspects of Intelligent Transportation Systems (ITS) applications; from behavioral modeling and car-following analyses to congestion prevention, crash prediction, dynamic signal timing, and active traffic management. This dissertation aims to improve the tasks of multi-object detection and tracking (MOT) as it pertains to urban traffic by utilizing the domain knowledge of traffic flow then utilize this improvement for applications in real-time traffic performance assessment, safety evaluation, and driver behavior modeling. First, the author proposes an ad-hoc framework for real-time turn count and trajectory reconstruction for vehicles passing through urban intersections. This framework introduces the concept of virtual traffic lanes representing the eight standard National Electrical Manufacturers Association (NEMA) movements within an intersection as spatio-temporal clusters utilized for movement classification and vehicle re-identification. The proposed framework runs as an additional layer to any multi-object tracker with minimal additional computation. The results obtained for a case study and on the AI City benchmark dataset indicate the high ability of the proposed framework in obtaining reliable turn count, speed estimates, and efficiently resolving the vehicle identity switches which occur within the intersection due to detection errors and occlusion. The author then proposes the utilization of the high accuracy and granularity trajectories obtained from video inference to develop a real-time safety-based driver behavior model, which managed to effectively capture the observed driving behavior in the site of study. Finally, the developed model was implemented as an external driver model in VISSIM and managed to reproduce the observed behavior and safety conflicts in simulation, providing an effective decision-support tool to identify appropriate safety interventions that would mitigate those conflicts. The work presented in this dissertation provides an efficient end-to-end framework and blueprint for trajectory extraction from road-side traffic video data, driver behavior modeling, and their applications for real-time traffic performance and safety assessment, as well as improved modeling of safety interventions via microscopic simulation.
  • Thumbnail Image
    Robust and Equitable Public Health Screening Strategies, with Application to Genetic and Infectious Diseases
    El Hajj, Hussein Mohammad (Virginia Tech, 2021-06-07)
    Public health screening plays an important role in the overall healthcare system. As an example, consider newborn screening, a state-level initiative that screens newborns for life-threatening genetic disorders for which early treatment can substantially improve health outcomes. Another topical example is in the realm of infectious disease screening, e.g., screening for COVID-19. The common features of both public health screening problems include large testing populations and resource limitations that inhibit screening efforts. Cost is a major barrier to the inclusion of genetic disorders in newborn screening, and thus screening must be both highly accurate and efficient; and for COVID-19, limited testing kits, and other shortages, have been major barriers to screening efforts. Further, for both newborn screening and infectious disease screening, equity (reducing health disparities among different sub-populations) is an important consideration. We study the testing process design for newborn screening for genetic diseases, considering cystic fibrosis as a model disorder. Our optimization-based models take into account disease-related parameters, subject risk factors, test characteristics, parameter uncertainty, and limited testing resources so as to design equitable, accurate, and robust screening processes that classify newborns as positive or negative for cystic fibrosis. Our models explicitly consider the trade-off between false-negatives, which lead to missed diagnoses, and the required testing resources; and the trade-off between the accuracy and equity of screening. We also study the testing process design for infectious disease screening, considering COVID-19 as a model disease. Our optimization-based models account for key subject risk factors that are important to consider, including the likelihood of being disease-positive, and the potential harm that could be averted through testing and the subsequent interventions. Our objectives include the minimization of harm (through detection and mitigation) or maximization of testing coverage. These are complex problems. We develop novel mathematical models and characterize key structural properties of optimal solutions. This, in turn, allows the development of effective and efficient algorithms that exploit these structural properties. These algorithms are either polynomial- or pseudo-polynomial-time algorithms, and are able to solve realistic-sized problems efficiently. Our case studies on cystic fibrosis screening and COVID-19 screening, based on realistic data, underscore the value of the proposed optimization-based approaches for public health screening, compared to current practices. Our findings have important implications for public policy.
  • Thumbnail Image
    Task Modeling, Sequencing, and Allocation for In-Space Autonomous Assembly by Robotic Systems
    Moser, Joshua Nickolas (Virginia Tech, 2022-07-18)
    As exploration in space increases through the use of larger telescopes, more sophisticated structures, and physical exploration, the use of autonomous robots will become instrumental to build and maintain the infrastructures required for this exploration. These systems must be autonomous to deal with the infeasibility of teleoperation due signal delay and task complexity. The reality of using robots in the real world without direct human input will require the autonomous systems to have the capability of responding to errors that occur in an assembly scenario on their own. As such, a system must be in place to allow for the sequencing and allocation of tasks to the robotic workforce autonomously, giving the ability to re-plan in real world stochastic environments. This work presents four contributions towards a system allowing for the autonomous sequencing and allocation of tasks for in-space assembly problems. The first contribution is the development of the Stochastic Assembly Problem Definition (SAPD) to articulate all of the features in an assembly problem that are applicable to the task sequencing and allocation. The second contribution is the formulation of a mixed integer program to solve for assembly schedules that are optimal or a quantifiable measurement from optimal. This contribution is expanded through the development of a genetic algorithm formulation to utilize the stochastic information present in the assembly problem. This formulation extends the state-of-the-art techniques in genetic algorithms to allow for the inclusion of new constraints required for the in-space assembly domain. The third contribution addresses how to estimate a robot's ability to complete a task if the robot must be assigned to a task it was previously not expected to work on. This is accomplished through the development of four metrics and analyzed through the use of screw theory kinematics. The final contribution focuses on a set of metrics to guide the selection of a good scheduling method for different assembly situations. The experiments in this work demonstrate how the developed theory can be utilized and shows the scheduling systems producing the best or close to the best schedules for assemblies. It also shows how the metrics used to quantify and estimate robot ability are applied. The theory developed in this work provides another step towards autonomous systems that are capable of assembling structures in-space without the need for human input.
  • Thumbnail Image
    Two-Stage Stochastic Mixed Integer Nonlinear Programming: Theory, Algorithms, and Applications
    Zhang, Yingqiu (Virginia Tech, 2021-09-30)
    With the rapidly growing need for long-term decision making in the presence of stochastic future events, it is important to devise novel mathematical optimization tools and develop computationally efficient solution approaches for solving them. Two-stage stochastic programming is one of the powerful modeling tools that allows probabilistic data parameters in mixed integer programming, a well-known tool for optimization modeling with deterministic input data. However, akin to the mixed integer programs, these stochastic models are theoretically intractable and computationally challenging to solve because of the presence of integer variables. This dissertation focuses on theory, algorithms and applications of two-stage stochastic mixed integer (non)linear programs and it has three-pronged plan. In the first direction, we study two-stage stochastic p-order conic mixed integer programs (TSS-CMIPs) with p-order conic terms in the second-stage objectives. We develop so called scenario-based (non)linear cuts which are added to the deterministic equivalent of TSS-CMIPs (a large-scale deterministic conic mixed integer program). We provide conditions under which these cuts are sufficient to relax the integrality restrictions on the second-stage integer variables without impacting the integrality of the optimal solution of the TSS-CMIP. We also introduce a multi-module capacitated stochastic facility location problem and TSS-CMIPs with structured CMIPs in the second stage to demonstrate the significance of the foregoing results for solving these problems. In the second direction, we propose risk-neutral and risk-averse two-stage stochastic mixed integer linear programs for load shed recovery with uncertain renewable generation and demand. The models are implemented using a scenario-based approach where the objective is to maximize load shed recovery in the bulk transmission network by switching transmission lines and performing other corrective actions (e.g. generator re-dispatch) after the topology is modified. Experiments highlight how the proposed approach can serve as an offline contingency analysis tool, and how this method aids self-healing by recovering more load shedding. In the third direction, we develop a dual decomposition approach for solving two-stage stochastic quadratically constrained quadratic mixed integer programs. We also create a new module for an open-source package DSP (Decomposition for Structured Programming) to solve this problem. We evaluate the effectiveness of this module and our approach by solving a stochastic quadratic facility location problem.