This dissertation addresses the problem of channel assignment in multi-hop, multi-transceiver wireless networks. We investigate (1) how channels can be assigned throughout the network to ensure that the network is connected and (2) how the channel assignment can be adapted to suit the current traffic demands. We analyze a traffic-aware method for channel assignment that addresses both maintaining network connectivity and adapting the topology based on dynamic traffic demands. The traffic-aware approach has one component that assigns channels independently of traffic conditions and a second component that assigns channels in response to traffic conditions. The traffic-independent (TI) component is designed to allocate as few transceivers or radios as possible in order to maintain network connectivity, while limiting the aggregate interference induced by the topology. The traffic-driven (TD) component is then designed to maximize end-to-end flow rate using the resources remaining after the TI assignment is complete. By minimizing resources in the TI component, the TD component has more resources to adapt the topology to suit the traffic demands and support higher end-to-end flow rate. We investigate the fundamental tradeoff between how many resources are allocated to maintaining network connectivity versus how many resources are allocated to maximize flow rate. We show that the traffic-aware approach achieves an appropriately balanced resource allocation, maintaining a baseline network connectivity and adapting to achieve near the maximum theoretical flow rate in the scenarios evaluated. We develop a set of greedy, heuristic algorithms that address the problem of resource- minimized TI assignment, the first component of the traffic-aware assignment. We develop centralized and distributed schemes for nodes to assign channels to their transceivers. These schemes perform well as compared to the optimal approach in the evaluation. We show that both of these schemes perform within 2% of the optimum in terms of the maximum achievable flow rate. We develop a set of techniques for adapting the network's channel assignment based on traffic demands, the second component of the traffic-aware assignment. In our approach, nodes sense traffic conditions and adapt their own channel assignment independently to support a high flow rate and adapt when network demand changes. We demonstrate how our distributed TI and TD approaches complement each other in an event-driven simulation. / Ph. D.

Departments of Transportation (DOTs) are responsible for keeping their road network in a state of good repair while also aiming to reduce congestion through the implementation of different traffic control and demand management strategies. These strategies can result in changes in traffic volume distributions, which in turn affect the level of pavement deterioration due to traffic loading. To address this issue, this dissertation introduces an integrated simulation-optimization framework that accounts for the combined effects of pavement conditions and traffic management decision-making strategies. The research focuses on exploring the range of possible performance outcomes resulting from this integrated modeling approach. The research also applied the developed framework to a particular traffic demand management strategy and assessed the impact of dynamic tolls around the specific site of I-66 inside the beltway. The integrated traffic-management/pavement-treatment framework was applied to address both the operational and pavement performance of the network. Aimsun hybrid macro/meso dynamic user equilibrium experiments were used to simulate the network with a modified cost function taking care of the dynamic pricing along the I-66 tolled facility. Furthermore, the framework was expanded to include the development of a systematic and comprehensive methodology to optimize the allocation of networkwide pavement treatment work zones over space and time. The proposed methodology also contributed to the development of a surrogate function that reduces the optimization computation burden so that researchers would be able to conduct work zone allocation optimization without having to run expensive simulation work. Finally, in this dissertation, a user-friendly decision-support tool was developed to assist in the pavement treatment and project selection planning process. We use machine learning models to encapsulate the simulation optimization process. / Doctor of Philosophy / Departments of Transportation (DOTs) are responsible for keeping their road network in a state of good repair. Improvement in pavement rehabilitation plans can lead to savings in the order of tens of millions of dollars. Pavement rehabilitation plans result in work zone schedules on the transportation network. Limited roadway capacities due to work zones affect traffic assignments and routing on the roads, which impacts the selection of optimal operation strategies to manage the resulting traffic. On the other hand, the choice of any particular operation and routing strategy will result in different distributions of traffic volumes on the roads and affect the pavement deterioration levels due to traffic loading, leading to other optimal rehabilitation plans and corresponding work zones. While there have been several research efforts on infrastructure condition assessment and other research efforts on traffic control and demand management strategies, there is a wide gap in the nexus of the two fields. To address this issue, this dissertation introduces an integrated simulation-optimization framework that accounts for the combined effects of pavement conditions and traffic management decision-making strategies. The research focuses on exploring the range of possible performance outcomes resulting from this integrated modeling approach. The research also applied the developed framework to a particular traffic demand management strategy and assessed the impact of dynamic tolls around the specific site of I-66 inside the beltway. The integrated traffic-management/pavement-treatment framework was applied to address both the operational and pavement performance of the network. Furthermore, the framework was expanded to include the development of a systematic and comprehensive methodology to optimize the allocation of networkwide pavement treatment work zones over space and time. The proposed methodology also contributed to the development of a surrogate function that reduces the optimization computation burden so that researchers would be able to conduct work zone allocation optimization without having to run expensive simulation work. Finally, in this dissertation, a user-friendly decision-support tool was developed to assist in the pavement treatment and project selection planning process. We use machine learning models to encapsulate the simulation optimization process.

The focus of this research is the line assignment problem in printed circuit card assembly systems. The line assignment problem involves the allocation of circuit card types to an appropriate assembly line among a set of assembly lines with the objective of reducing the total assembly time. These circuit cards are to be assembled in a manufacturing facility, capable of simultaneously producing a wide variety of printed circuit cards in different production volumes. A set of component types is required for each printed circuit card. The objective is to assign the circuit cards to the assembly line such that the total assembly time, which includes the setup time as well as the processing time required for all card types in a set, is minimized. The focus of this research is to develop an algorithmic strategy for addressing this problem in electronics assembly. This problem involves considering several interrelated decision problems such as assigning printed circuit cards to assembly lines, grouping circuit cards into families to reduce the number of setups, and assigning component types to machines to balance workload. The line assignment models are formulated as large scale mixed integer programming problems and are solved using a branch-and-bound algorithm, supplemented by techniques for improving the solution time. The models and solution approaches are demonstrated using industry representative data sets and can serve as useful decision support tools for process planning engineers. / Master of Science

Microworlds are visual, 2D grid-based worlds with programmable actors that help ease students into programming. Microworlds have been used as a pedagogical tool for teaching students to program in an object-oriented paradigm for several years now. With the popularity of Android smart phones, creating a pedagogical microworld for Android can help students learn not just Java, OO and event-driven concepts, but also learn to use the Android framework to create concrete, real-world applications. This thesis presents Sofia.Micro, an Android-based pedagogical microworld framework that not only allows Greenfoot-style microworld programs to run on Android, but also adds additional functionalities to microworlds that have not been previously explored, such as built-in shape and physics support, event-driven programming in a microworld context, and allowing for both Greenfoot-style actors and Karel-style actors in the same world. / Master of Science

This thesis provides three main contributions with respect to the Dynamic Channel and Power Assignment (DCPA) problem. DCPA refers to the allocation of transmit power and frequency channels to links in a cognitive dynamic spectrum network so as to maximize the total number of feasible links while minimizing the aggregate transmit power. In order to provide a method to compare related, yet disparate, work, the first contribution of this thesis is a unifying optimization formulation to describe the DCPA problem. This optimization problem is based on maximizing the number of feasible links and minimizing transmit power of a set of communications links in a given communications network. Using this optimization formulation, this thesis develops its second contribution: a evaluation method for comparing DCPA algorithms. The evaluation method is applied to five DPCA algorithms representative of the DCPA literature . These five algorithms are selected to illustrate the tradeoffs between control modes (centralized versus distributed) and channel/power assignment techniques. Initial algorithm comparisons are done by analyzing channel and power assignment techniques and algorithmic complexity of five different DCPA algorithms. Through simulations, algorithm performance is evaluated by the metrics of feasibility ratio and average power per link. Results show that the centralized algorithm Minimum Power Increase Assignment (MPIA) has the overall best feasibility ratio and the lowest average power per link of the five algorithms we investigated. Through assignment by the least change in transmit power, MPIA minimizes interference and increases the number of feasible links. However, implementation of this algorithm requires calculating the inverse of near singular matrices, which could lead to inaccurate results. The third contribution of this thesis is a proposed distributed channel assignment algorithm, Least Interfering Channel and Iterative Power Assignment (LICIPA). This distributed algorithm has the best feasibility ratio and lowest average power per link of the distributed algorithms. In some cases, LICIPA achieves 90% of the feasibility ratio of MPIA, while having lower complexity and overall lower average run time. / Master of Science

This dissertation addresses the development and analysis of optimization models for evacuation planning. Specifically we consider the cases of large-scale regional evacuation using household vehicles and hospital evacuation. Since it is difficult to estimate the exact number of people evacuating, we first consider the case where the population size is uncertain. We review the methods studied in the literature, mainly the strategy of using a deterministic counterpart, i.e., a single deterministic parameter to represent the uncertain population, and we show that these methods are not very effective in generating a good traffic management strategy. We provide alternatives, where we describe some networks where an optimal policy exist independent of the demand realization and we propose some simple heuristics for more complex ones. Next we consider the traffic management tools that can be generated from an evacuation plan. We start by introducing the cell transmission model with flow reduction. This model captures the flow reduction after the onset of congestion. We then discuss the management tools that can be extracted from this model. We also propose some simplification to the model formulation to enhance its tractability. A heuristic for generating a solution is also proposed, and its solution quality is analyzed. Finally, we discuss the hospital evacuation problem where we develop an integer programming model that integrates the building evacuation with the transportation of patients. The impact of building evacuation capabilities on the transportation plan is investigated through the case of a large regional hospital case study. We also propose a decomposition scheme to improve the tractability of the integer program. / Ph. D.

With the proliferation of fairly powerful mobile devices and ubiquitous wireless technology, traditional mobile ad hoc networks (MANETs) now migrate into a new era of service-oriented MANETs wherein a node can provide and receive service from other nodes it encounters and interacts with. This dissertation research concerns trust management and its applications for service-oriented MANETs to answer the challenges of MANET environments, including no centralized authority, dynamically changing topology, limited bandwidth and battery power, limited observations, unreliable communication, and the presence of malicious nodes who act to break the system functionality as well as selfish nodes who act to maximize their own gain. We propose a context-aware trust management model called CATrust for service-oriented ad hoc networks. The novelty of our design lies in the use of logit regression to dynamically estimate trustworthiness of a service provider based on its service behavior patterns in a context environment, treating channel conditions, node status, service payoff, and social disposition as 'context' information. We develop a recommendation filtering mechanism to effectively screen out false recommendations even in extremely hostile environments in which the majority recommenders are malicious. We demonstrate desirable convergence, accuracy, and resiliency properties of CATrust. We also demonstrate that CATrust outperforms contemporary peer-to-peer and Internet of Things trust models in terms of service trust prediction accuracy against collusion recommendation attacks. We validate the design of trust-based service management based on CATrust with a node-to-service composition and binding MANET application and a node-to-task assignment MANET application with multi-objective optimization (MOO) requirements. For either application, we propose a trust-based algorithm to effectively filter out malicious nodes exhibiting various attack behaviors by penalizing them with trust loss, which ultimately leads to high user satisfaction. Our trust-based algorithm is efficient with polynomial runtime complexity while achieving a close-to-optimal solution. We demonstrate that our trust-based algorithm built on CATrust outperforms a non-trust-based counterpart using blacklisting techniques and trust-based counterparts built on contemporary peer-to-peer trust protocols. We also develop a dynamic table-lookup method to apply the best trust model parameter settings upon detection of rapid MANET environment changes to maximize MOO performance. / Ph. D.

In this dissertation, we study multi-robot coordination in the context of multi-target tracking. Specifically, we are interested in the coordination achieved by means of submodular function optimization. Submodularity encodes the diminishing returns property that arises in multi-robot coordination. For example, the marginal gain of assigning an additional robot to track the same target diminishes as the number of robots assigned increases. The advantage of formulating coordination problems as submodular optimization is that a simple, greedy algorithm is guaranteed to give a good performance. However, often this comes at the expense of unrealistic models and assumptions. For example, the standard formulation does not take into account the fact that robots may fail, either randomly or due to adversarial attacks. When operating in uncertain conditions, we typically seek to optimize the expected performance. However, this does not give any flexibility for a user to seek conservative or aggressive behaviors from the team of robots. Furthermore, most coordination algorithms force robots to communicate at each time step, even though they may not need to. Our goal in this dissertation is to overcome these limitations by devising coordination algorithms that are parsimonious in communication, allow a user to manage the risk of the robot performance, and are resilient to worst-case robot failures and attacks. In the first part of this dissertation, we focus on designing parsimonious communication strategies for target tracking. Specifically, we investigate the problem of determining when to communicate and who to communicate with. When the robots use range sensors, the tracking performance is a function of the relative positions of the robots and the targets. We propose a self-triggered communication strategy in which a robot communicates its own position with its neighbors only when a certain set of conditions are violated. We prove that this strategy converges to the optimal robot positions for tracking a single target and in practice, reduces the number of communication messages by 30%. When tracking multiple targets, we can reduce the communication by forming subsets of robots and assigning one subset to track a target. We investigate a number of measures for tracking quality based on the observability matrix and show which ones are submodular and which ones are not. For non-submodular measures, we show a greedy algorithm gives a 1/(n+1) approximation, if we restrict the subset to n robots. In optimizing submodular functions, a common assumption is that the function value is deterministic, which may not hold in practice. For example, the sensor performance may depend on environmental conditions which are not known exactly. In the second part of the dissertation, we design an algorithm for stochastic submodular optimization. The standard formulation for stochastic optimization optimizes the expected performance. However, the expectation is a risk-neutral measure. Instead, we optimize the Conditional Value-at-Risk (CVaR), which allows the user the flexibility of choosing a risk level. We present an algorithm, based on the greedy algorithm, and prove that its performance has bounded suboptimality and improves with running time. We also present an online version of the algorithm to adapt to real-time scenarios. In the third part of this dissertation, we focus on scenarios where a set of robots may fail naturally or due to adversarial attacks. Our objective is to track as many targets as possible, a submodular measure, assuming worst-case robot failures. We present both centralized and distributed resilient tracking algorithms to cope with centralized and distributed communication settings. We prove these algorithms give a constant-factor approximation of the optimal in polynomial running time. / Doctor of Philosophy / Today, robotics and autonomous systems have been increasingly used in various areas such as manufacturing, military, agriculture, medical sciences, and environmental monitoring. However, most of these systems are fragile and vulnerable to adversarial attacks and uncertain environmental conditions. In most cases, even if a part of the system fails, the entire system performance can be significantly undermined. As robots start to coexist with humans, we need algorithms that can be trusted under real-world, not just ideal conditions. Thus, this dissertation focuses on enabling security, trustworthiness, and long-term autonomy in robotics and autonomous systems. In particular, we devise coordination algorithms that are resilient to attacks, trustworthy in the face of the uncertain conditions, and allow the long-term operation of multi-robot systems. We evaluate our algorithms through extensive simulations and proof-of-concept experiments. Generally speaking, multi-robot systems form the "physical" layer of Cyber-Physical Sytems (CPS), the Internet of Things (IoT), and Smart City. Thus, our research can find applications in the areas of connected and autonomous vehicles, intelligent transportation, communications and sensor networks, and environmental monitoring in smart cities.

Automated programming assignment grading tools have become integral to CS courses at introductory as well as advanced levels. However a lot of these tools have their own custom approaches to setting up assignments and describing how solutions should be tested, requiring instructors to make a significant learning investment to begin using a new tool. In addition, differences between tools mean that initial investment must be repeated when switching tools or adding a new one. Worse still, tool-specific strategies further reduce the ability of educators to share and reuse their assignments. As a solution to this problem, we describe our experiences working with PEML, the Programming Exercise Markup Language, which provides an easy to use, instructor friendly approach for writing programming assignments. Unlike tool-oriented data interchange formats, PEML is designed to provide a human friendly authoring format that has been developed to be intuitive, expressive and not be a technological or notational barrier to instructors. We describe the design of PEML and also discuss its implementation as a programming library, a web application, and a microservice that provides full parsing and rendering capabilities for easy integration into any tools or scripting libraries. We also describe the integration of PEML into two automated testing and grading tools used at Virginia Tech by the CS department: Code Workout and Web-CAT. We then describe our experiences using PEML to describe a full range of programming assignments, laboratory exercises, and small coding questions of varying complexity in demonstrating the practicality of the notation. We evaluate the feasibility of PEML using this encoding exercise as well as the effect of its integration into the aforementioned automated grading tools. We finally present a framework for integrating PEML into existing grading tools and then draw our conclusions as well as list down avenues PEML can be expanded into in the future. / Master of Science / Automated grading tools have become ubiquitous to CS courses focused on programming concepts at both the undergraduate as well as graduate level. These tools allow instructors to provide near instant feedback to students as well as spend more time focusing on the curriculum rather than grading. However, these tools use a variety programming assignment representation formats and without a standardized representation, instructors and educators may struggle to share and reuse assignments across different tools and platforms. To address this need, we have developed the Programming Exercise Markup Language (PEML), a standardized format for representing programming exercises, designed to be human-friendly as well as easy to learn and use. PEML includes information about the problem statement, input and output formats, constraints, and sample test cases, and can be used for a wide range of exercise types and programming languages. As part of this master's thesis project, we encoded 50 assignments of varying size and difficulty into PEML as well as integrated support for PEML into Web-CAT and Code Workout, two commonly used automated grading tools used at Virginia Tech. Building upon our experience performing this task, we also designed a framework that can be utilized when integrating PEML into other automated grading tools. By providing a standardized way of representing programming assignments, PEML can help to streamline programming education and make it easier for instructors and educators to create and share assignments across different tools and platforms.

Multi-criteria scheduling provides the opportunity to create mathematical optimization models that are applicable to a diverse set of problem domains in the business world. This research addresses two different employee scheduling applications using multi-criteria objectives that present decision makers with trade-offs between global optimality and the level of disruption to current operating resources. Additionally, it investigates a scheduling problem from the product testing domain and proposes a heuristic solution technique for the problem that is shown to produce very high-quality solutions in short amounts of time. Chapter 2 addresses a grant administration workload-to-staff assignment problem that occurs in the Office of Research and Sponsored Programs at land-grant universities. We identify the optimal workload assignment plan which differs considerably due to multiple reassignments from the current state. To achieve the optimal workload reassignment plan we demonstrate a technique to identify the n best reassignments from the current state that provides the greatest progress toward the utopian solution. Solving this problem over several values of n and plotting the results allows the decision maker to visualize the reassignments and the progress achieved toward the utopian balanced workload solution. Chapter 3 identifies a weekly schedule that seeks the most cost-effective set of coach-to-program assignments in a gymnastics facility. We identify the optimal assignment plan using an integer linear programming model. The optimal assignment plan differs greatly from the status quo; therefore, we utilize a similar approach from Chapter 2 and use a multiple objective optimization technique to identify the n best staff reassignments. Again, the decision maker can visualize the trade-off between the number of reassignments and the resulting progress toward the utopian staffing cost solution and make an informed decision about the best number of reassignments. Chapter 4 focuses on product test scheduling in the presence of in-process and at-completion inspection constraints. Such testing arises in the context of the manufacture of products that must perform reliably in extreme environmental conditions. Each product receives a certification at the successful completion of a predetermined series of tests. Operational efficiency is enhanced by determining the optimal order and start times of tests so as to minimize the make span while ensuring that technicians are available when needed to complete in-process and at-completion inspections We first formulate a mixed-integer programming model (MILP) to identify the optimal solution to this problem using IBM ILOG CPLEX Interactive Optimizer 12.7. We also present a genetic algorithm (GA) solution that is implemented and solved in Microsoft Excel. Computational results are presented demonstrating the relative merits of the MILP and GA solution approaches across a number of scenarios. / Ph. D. / Multi-criteria scheduling provides the opportunity to create mathematical optimization models that are applicable to a diverse set of problem domains in the business world. This research addresses two different employee scheduling applications using multi-criteria objectives that present decision makers with trade-offs between global optimality and the level of disruption to current operating resources. Additionally, it investigates a scheduling problem from the product testing domain and proposes a heuristic solution technique for the problem that is shown to produce very high-quality solutions in short amounts of time. Chapter 2 addresses a grant administration workload-to-staff assignment problem that occurs in the Office of Research and Sponsored Programs at land-grant universities. Solving this problem and plotting the results allows the decision maker to visualize the number of reassignments and the progress achieved toward the utopian balanced workload solution. Chapter 3 identifies a weekly schedule that seeks the most cost-effective set of coach-to-program assignments in a gymnastics facility. Again, the decision maker can visualize the trade-off between the number of reassignments and the resulting progress toward the utopian staffing cost solution and make an informed decision about the best number of reassignments. Chapter 4 focuses on product test scheduling in the presence of in-process and at-completion inspection constraints. Such testing arises in the context of the manufacture of products that must perform reliably in extreme environmental conditions. Each product receives a certification at the successful completion of a predetermined series of tests. Computational results are presented demonstrating the relative merits of the mixed integer linear programming model and the genetic algorithm solution approaches across a number of scenarios.