Showing 1–50 of 55 results for author: Saxena, D

CONGO: Compressive Online Gradient Optimization with Application to Microservices Management

Authors: Jeremy Carleton, Prathik Vijaykumar, Divyanshu Saxena, Dheeraj Narasimha, Srinivas Shakkottai, Aditya Akella

Abstract: We address the challenge of online convex optimization where the objective function's gradient exhibits sparsity, indicating that only a small number of dimensions possess non-zero gradients. Our aim is to leverage this sparsity to obtain useful estimates of the objective function's gradient even when the only information available is a limited number of function samples. Our motivation stems from… ▽ More We address the challenge of online convex optimization where the objective function's gradient exhibits sparsity, indicating that only a small number of dimensions possess non-zero gradients. Our aim is to leverage this sparsity to obtain useful estimates of the objective function's gradient even when the only information available is a limited number of function samples. Our motivation stems from distributed queueing systems like microservices-based applications, characterized by request-response workloads. Here, each request type proceeds through a sequence of microservices to produce a response, and the resource allocation across the collection of microservices is controlled to balance end-to-end latency with resource costs. While the number of microservices is substantial, the latency function primarily reacts to resource changes in a few, rendering the gradient sparse. Our proposed method, CONGO (Compressive Online Gradient Optimization), combines simultaneous perturbation with compressive sensing to estimate gradients. We establish analytical bounds on the requisite number of compressive sensing samples per iteration to maintain bounded bias of gradient estimates, ensuring sub-linear regret. By exploiting sparsity, we reduce the samples required per iteration to match the gradient's sparsity, rather than the problem's original dimensionality. Numerical experiments and real-world microservices benchmarks demonstrate CONGO's superiority over multiple stochastic gradient descent approaches, as it quickly converges to performance comparable to policies pre-trained with workload awareness. △ Less

Submitted 8 July, 2024; originally announced July 2024.

Comments: 28 pages, 7 figures

NASPrecision: Neural Architecture Search-Driven Multi-Stage Learning for Surface Roughness Prediction in Ultra-Precision Machining

Authors: Penghui Ruan, Divya Saxena, Jiannong Cao, Xiaoyun Liu, Ruoxin Wang, Chi Fai Cheung

Abstract: Accurate surface roughness prediction is critical for ensuring high product quality, especially in areas like manufacturing and aerospace, where the smallest imperfections can compromise performance or safety. However, this is challenging due to complex, non-linear interactions among variables, which is further exacerbated with limited and imbalanced datasets. Existing methods using traditional ma… ▽ More Accurate surface roughness prediction is critical for ensuring high product quality, especially in areas like manufacturing and aerospace, where the smallest imperfections can compromise performance or safety. However, this is challenging due to complex, non-linear interactions among variables, which is further exacerbated with limited and imbalanced datasets. Existing methods using traditional machine learning algorithms require extensive domain knowledge for feature engineering and substantial human intervention for model selection. To address these issues, we propose NASPrecision, a Neural Architecture Search (NAS)-Driven Multi-Stage Learning Framework. This innovative approach autonomously identifies the most suitable features and models for various surface roughness prediction tasks and significantly enhances the performance by multi-stage learning. Our framework operates in three stages: 1) architecture search stage, employing NAS to automatically identify the most effective model architecture; 2) initial training stage, where we train the neural network for initial predictions; 3) refinement stage, where a subsequent model is appended to refine and capture subtle variations overlooked by the initial training stage. In light of limited and imbalanced datasets, we adopt a generative data augmentation technique to balance and generate new data by learning the underlying data distribution. We conducted experiments on three distinct real-world datasets linked to different machining techniques. Results show improvements in Mean Absolute Percentage Error (MAPE), Root Mean Square Error (RMSE), and Standard Deviation (STD) by 18%, 31%, and 22%, respectively. This establishes it as a robust and general solution for precise surface roughness prediction, potentially boosting production efficiency and product quality in key industries while minimizing domain expertise and human intervention. △ Less

Submitted 27 May, 2024; originally announced May 2024.

FedDistill: Global Model Distillation for Local Model De-Biasing in Non-IID Federated Learning

Authors: Changlin Song, Divya Saxena, Jiannong Cao, Yuqing Zhao

Abstract: Federated Learning (FL) is a novel approach that allows for collaborative machine learning while preserving data privacy by leveraging models trained on decentralized devices. However, FL faces challenges due to non-uniformly distributed (non-iid) data across clients, which impacts model performance and its generalization capabilities. To tackle the non-iid issue, recent efforts have utilized the… ▽ More Federated Learning (FL) is a novel approach that allows for collaborative machine learning while preserving data privacy by leveraging models trained on decentralized devices. However, FL faces challenges due to non-uniformly distributed (non-iid) data across clients, which impacts model performance and its generalization capabilities. To tackle the non-iid issue, recent efforts have utilized the global model as a teaching mechanism for local models. However, our pilot study shows that their effectiveness is constrained by imbalanced data distribution, which induces biases in local models and leads to a 'local forgetting' phenomenon, where the ability of models to generalize degrades over time, particularly for underrepresented classes. This paper introduces FedDistill, a framework enhancing the knowledge transfer from the global model to local models, focusing on the issue of imbalanced class distribution. Specifically, FedDistill employs group distillation, segmenting classes based on their frequency in local datasets to facilitate a focused distillation process to classes with fewer samples. Additionally, FedDistill dissects the global model into a feature extractor and a classifier. This separation empowers local models with more generalized data representation capabilities and ensures more accurate classification across all classes. FedDistill mitigates the adverse effects of data imbalance, ensuring that local models do not forget underrepresented classes but instead become more adept at recognizing and classifying them accurately. Our comprehensive experiments demonstrate FedDistill's effectiveness, surpassing existing baselines in accuracy and convergence speed across several benchmark datasets. △ Less

Submitted 14 April, 2024; originally announced April 2024.

Comments: 13 pages, 9 figures, 5 tables

Beyond Predictive Algorithms in Child Welfare

Authors: Erina Seh-Young Moon, Devansh Saxena, Tegan Maharaj, Shion Guha

Abstract: Caseworkers in the child welfare (CW) sector use predictive decision-making algorithms built on risk assessment (RA) data to guide and support CW decisions. Researchers have highlighted that RAs can contain biased signals which flatten CW case complexities and that the algorithms may benefit from incorporating contextually rich case narratives, i.e. - casenotes written by caseworkers. To investiga… ▽ More Caseworkers in the child welfare (CW) sector use predictive decision-making algorithms built on risk assessment (RA) data to guide and support CW decisions. Researchers have highlighted that RAs can contain biased signals which flatten CW case complexities and that the algorithms may benefit from incorporating contextually rich case narratives, i.e. - casenotes written by caseworkers. To investigate this hypothesized improvement, we quantitatively deconstructed two commonly used RAs from a United States CW agency. We trained classifier models to compare the predictive validity of RAs with and without casenote narratives and applied computational text analysis on casenotes to highlight topics uncovered in the casenotes. Our study finds that common risk metrics used to assess families and build CWS predictive risk models (PRMs) are unable to predict discharge outcomes for children who are not reunified with their birth parent(s). We also find that although casenotes cannot predict discharge outcomes, they contain contextual case signals. Given the lack of predictive validity of RA scores and casenotes, we propose moving beyond quantitative risk assessments for public sector algorithms and towards using contextual sources of information such as narratives to study public sociotechnical systems. △ Less

Submitted 26 February, 2024; originally announced March 2024.

Are We Asking the Right Questions?: Designing for Community Stakeholders' Interactions with AI in Policing

Authors: MD Romael Haque, Devansh Saxena, Katy Weathington, Joseph Chudzik, Shion Guha

Abstract: Research into recidivism risk prediction in the criminal legal system has garnered significant attention from HCI, critical algorithm studies, and the emerging field of human-AI decision-making. This study focuses on algorithmic crime mapping, a prevalent yet underexplored form of algorithmic decision support (ADS) in this context. We conducted experiments and follow-up interviews with 60 particip… ▽ More Research into recidivism risk prediction in the criminal legal system has garnered significant attention from HCI, critical algorithm studies, and the emerging field of human-AI decision-making. This study focuses on algorithmic crime mapping, a prevalent yet underexplored form of algorithmic decision support (ADS) in this context. We conducted experiments and follow-up interviews with 60 participants, including community members, technical experts, and law enforcement agents (LEAs), to explore how lived experiences, technical knowledge, and domain expertise shape interactions with the ADS, impacting human-AI decision-making. Surprisingly, we found that domain experts (LEAs) often exhibited anchoring bias, readily accepting and engaging with the first crime map presented to them. Conversely, community members and technical experts were more inclined to engage with the tool, adjust controls, and generate different maps. Our findings highlight that all three stakeholders were able to provide critical feedback regarding AI design and use - community members questioned the core motivation of the tool, technical experts drew attention to the elastic nature of data science practice, and LEAs suggested redesign pathways such that the tool could complement their domain expertise. △ Less

Submitted 19 March, 2024; v1 submitted 7 February, 2024; originally announced February 2024.

On a Foundation Model for Operating Systems

Authors: Divyanshu Saxena, Nihal Sharma, Donghyun Kim, Rohit Dwivedula, Jiayi Chen, Chenxi Yang, Sriram Ravula, Zichao Hu, Aditya Akella, Sebastian Angel, Joydeep Biswas, Swarat Chaudhuri, Isil Dillig, Alex Dimakis, P. Brighten Godfrey, Daehyeok Kim, Chris Rossbach, Gang Wang

Abstract: This paper lays down the research agenda for a domain-specific foundation model for operating systems (OSes). Our case for a foundation model revolves around the observations that several OS components such as CPU, memory, and network subsystems are interrelated and that OS traces offer the ideal dataset for a foundation model to grasp the intricacies of diverse OS components and their behavior in… ▽ More This paper lays down the research agenda for a domain-specific foundation model for operating systems (OSes). Our case for a foundation model revolves around the observations that several OS components such as CPU, memory, and network subsystems are interrelated and that OS traces offer the ideal dataset for a foundation model to grasp the intricacies of diverse OS components and their behavior in varying environments and workloads. We discuss a wide range of possibilities that then arise, from employing foundation models as policy agents to utilizing them as generators and predictors to assist traditional OS control algorithms. Our hope is that this paper spurs further research into OS foundation models and creating the next generation of operating systems for the evolving computing landscape. △ Less

Submitted 12 December, 2023; originally announced December 2023.

Comments: Machine Learning for Systems Workshop at 37th NeurIPS Conference, 2023, New Orleans, LA, USA

MGAS: Multi-Granularity Architecture Search for Trade-Off Between Model Effectiveness and Efficiency

Authors: Xiaoyun Liu, Divya Saxena, Jiannong Cao, Yuqing Zhao, Penghui Ruan

Abstract: Neural architecture search (NAS) has gained significant traction in automating the design of neural networks. To reduce the time cost, differentiable architecture search (DAS) transforms the traditional paradigm of discrete candidate sampling and evaluation into that of differentiable super-net optimization and discretization. However, existing DAS methods fail to trade off between model performan… ▽ More Neural architecture search (NAS) has gained significant traction in automating the design of neural networks. To reduce the time cost, differentiable architecture search (DAS) transforms the traditional paradigm of discrete candidate sampling and evaluation into that of differentiable super-net optimization and discretization. However, existing DAS methods fail to trade off between model performance and model size. They either only conduct coarse-grained operation-level search, which results in redundant model parameters, or restrictively explore fine-grained filter-level and weight-level units with pre-defined remaining ratios, suffering from excessive pruning problem. Additionally, these methods compromise search quality to save memory during the search process. To tackle these issues, we introduce multi-granularity architecture search (MGAS), a unified framework which aims to discover both effective and efficient neural networks by comprehensively yet memory-efficiently exploring the multi-granularity search space. Specifically, we improve the existing DAS methods in two aspects. First, we balance the model unit numbers at different granularity levels with adaptive pruning. We learn discretization functions specific to each granularity level to adaptively determine the unit remaining ratio according to the evolving architecture. Second, we reduce the memory consumption without degrading the search quality using multi-stage search. We break down the super-net optimization and discretization into multiple sub-net stages, and perform progressive re-evaluation to allow for re-pruning and regrowing of previous units during subsequent stages, compensating for potential bias. Extensive experiments on CIFAR-10, CIFAR-100 and ImageNet demonstrate that MGAS outperforms other state-of-the-art methods in achieving a better trade-off between model performance and model size. △ Less

Submitted 9 December, 2023; v1 submitted 23 October, 2023; originally announced October 2023.

An AI-Driven VM Threat Prediction Model for Multi-Risks Analysis-Based Cloud Cybersecurity

Authors: Deepika Saxena, Ishu Gupta, Rishabh Gupta, Ashutosh Kumar Singh, Xiaoqing Wen

Abstract: Cloud virtualization technology, ingrained with physical resource sharing, prompts cybersecurity threats on users' virtual machines (VM)s due to the presence of inevitable vulnerabilities on the offsite servers. Contrary to the existing works which concentrated on reducing resource sharing and encryption and decryption of data before transfer for improving cybersecurity which raises computational… ▽ More Cloud virtualization technology, ingrained with physical resource sharing, prompts cybersecurity threats on users' virtual machines (VM)s due to the presence of inevitable vulnerabilities on the offsite servers. Contrary to the existing works which concentrated on reducing resource sharing and encryption and decryption of data before transfer for improving cybersecurity which raises computational cost overhead, the proposed model operates diversely for efficiently serving the same purpose. This paper proposes a novel Multiple Risks Analysis based VM Threat Prediction Model (MR-TPM) to secure computational data and minimize adversary breaches by proactively estimating the VMs threats. It considers multiple cybersecurity risk factors associated with the configuration and management of VMs, along with analysis of users' behaviour. All these threat factors are quantified for the generation of respective risk score values and fed as input into a machine learning based classifier to estimate the probability of threat for each VM. The performance of MR-TPM is evaluated using benchmark Google Cluster and OpenNebula VM threat traces. The experimental results demonstrate that the proposed model efficiently computes the cybersecurity risks and learns the VM threat patterns from historical and live data samples. The deployment of MR-TPM with existing VM allocation policies reduces cybersecurity threats up to 88.9%. △ Less

Submitted 18 August, 2023; originally announced August 2023.

Journal ref: IEEE Transactions on Systems, Man, and Cybernetics: Systems Journal, 2023

Algorithmic Harms in Child Welfare: Uncertainties in Practice, Organization, and Street-level Decision-Making

Authors: Devansh Saxena, Shion Guha

Abstract: Algorithms in public services such as child welfare, criminal justice, and education are increasingly being used to make high-stakes decisions about human lives. Drawing upon findings from a two-year ethnography conducted at a child welfare agency, we highlight how algorithmic systems are embedded within a complex decision-making ecosystem at critical points of the child welfare process. Caseworke… ▽ More Algorithms in public services such as child welfare, criminal justice, and education are increasingly being used to make high-stakes decisions about human lives. Drawing upon findings from a two-year ethnography conducted at a child welfare agency, we highlight how algorithmic systems are embedded within a complex decision-making ecosystem at critical points of the child welfare process. Caseworkers interact with algorithms in their daily lives where they must collect information about families and feed it to algorithms to make critical decisions. We show how the interplay between systemic mechanics and algorithmic decision-making can adversely impact the fairness of the decision-making process itself. We show how functionality issues in algorithmic systems can lead to process-oriented harms where they adversely affect the nature of professional practice, and administration at the agency, and lead to inconsistent and unreliable decisions at the street level. In addition, caseworkers are compelled to undertake additional labor in the form of repair work to restore disrupted administrative processes and decision-making, all while facing organizational pressures and time and resource constraints. Finally, we share the case study of a simple algorithmic tool that centers caseworkers' decision-making within a trauma-informed framework and leads to better outcomes, however, required a significant amount of investments on the agency's part in creating the ecosystem for its proper use. △ Less

Submitted 9 August, 2023; originally announced August 2023.

Dirigo: Self-scaling Stateful Actors For Serverless Real-time Data Processing

Authors: Le Xu, Divyanshu Saxena, Neeraja J. Yadwadkar, Aditya Akella, Indranil Gupta

Abstract: We propose Dirigo, a distributed stream processing service built atop virtual actors. Dirigo achieves both a high level of resource efficiency and performance isolation driven by user intent (SLO). To improve resource efficiency, Dirigo adopts a serverless architecture that enables time-sharing of compute resources among streaming operators, both within and across applications. Meanwhile, Dirigo i… ▽ More We propose Dirigo, a distributed stream processing service built atop virtual actors. Dirigo achieves both a high level of resource efficiency and performance isolation driven by user intent (SLO). To improve resource efficiency, Dirigo adopts a serverless architecture that enables time-sharing of compute resources among streaming operators, both within and across applications. Meanwhile, Dirigo improves performance isolation by inheriting the property of function autoscaling from serverless architecture. Specifically, Dirigo proposes (i) dual-mode actor, an actor abstraction that dynamically provides orderliness guarantee for streaming operator during autoscaling and (ii) a data plane scheduling mechanism, along with its API, that allows scheduling and scaling at the message-level granularity. △ Less

Submitted 7 August, 2023; originally announced August 2023.

Cryptography approach for Secure Outsourced Data Storage in Cloud Environment

Authors: Rishabh Gupta, Deepika Saxena, Ashutosh Kumar Singh

Abstract: A large amount of data and applications are migrated by researchers, stakeholders, academia, and business organizations to the cloud environment due to its large variety of services, which involve the least maintenance cost, maximum flexibility, and on-demand service for storage, computation, and data distribution intentions. Despite the various characteristics the cloud environment supports, it a… ▽ More A large amount of data and applications are migrated by researchers, stakeholders, academia, and business organizations to the cloud environment due to its large variety of services, which involve the least maintenance cost, maximum flexibility, and on-demand service for storage, computation, and data distribution intentions. Despite the various characteristics the cloud environment supports, it also faces many challenges. However, data users may not completely trust a cloud environment that is engaged by a third party. Every cloud user always has a prime concern, i.e., security. Numerous methods have been designed to solve the issue of data security during data storage, calculation, and sharing across stakeholders and users. Nevertheless, there is a lack of existing methods that tackle the issue of the security of data when it is stored in a cloud environment. This article presents a precise security method that has handled the security of data while it is being shared and stored in the cloud. These methods have been utilized to lessen security assaults and prevent unauthorized parties from accessing the actual data. The article is concluded with some limitations and recommendations for the future in terms of secure data retention and distribution. △ Less

Submitted 14 June, 2023; originally announced June 2023.

An AI-driven intelligent traffic management model for 6G cloud radio access networks

Authors: Smruti Rekha Swain, Deepika Saxena, Jatinder Kumar, Ashutosh Kumar Singh, Chung-Nan Lee

Abstract: This letter proposes a novel Cloud Radio Access Network (C-RAN) traffic analysis and management model that estimates probable RAN traffic congestion and mitigate its effect by adopting a suitable handling mechanism. A computation approach is introduced to classify heterogeneous RAN traffic into distinct traffic states based on bandwidth consumption and execution time of various job requests. Furth… ▽ More This letter proposes a novel Cloud Radio Access Network (C-RAN) traffic analysis and management model that estimates probable RAN traffic congestion and mitigate its effect by adopting a suitable handling mechanism. A computation approach is introduced to classify heterogeneous RAN traffic into distinct traffic states based on bandwidth consumption and execution time of various job requests. Further, a cloud-based traffic management is employed to schedule and allocate resources among user job requests according to the associated traffic states to minimize latency and maximize bandwidth utilization. The experimental evaluation and comparison of the proposed model with state-of-the-art methods reveal that it is effective in minimizing the worse effect of traffic congestion and improves bandwidth utilization and reduces job execution latency up to 17.07% and 18%, respectively. △ Less

Submitted 25 March, 2023; originally announced March 2023.

Journal ref: IEEE Wireless Communications Letters 2023

Planning for Manipulation among Movable Objects: Deciding Which Objects Go Where, in What Order, and How

Authors: Dhruv Saxena, Maxim Likhachev

Abstract: We are interested in pick-and-place style robot manipulation tasks in cluttered and confined 3D workspaces among movable objects that may be rearranged by the robot and may slide, tilt, lean or topple. A recently proposed algorithm, M4M, determines which objects need to be moved and where by solving a Multi-Agent Pathfinding MAPF abstraction of this problem. It then utilises a nonprehensile push p… ▽ More We are interested in pick-and-place style robot manipulation tasks in cluttered and confined 3D workspaces among movable objects that may be rearranged by the robot and may slide, tilt, lean or topple. A recently proposed algorithm, M4M, determines which objects need to be moved and where by solving a Multi-Agent Pathfinding MAPF abstraction of this problem. It then utilises a nonprehensile push planner to compute actions for how the robot might realise these rearrangements and a rigid body physics simulator to check whether the actions satisfy physics constraints encoded in the problem. However, M4M greedily commits to valid pushes found during planning, and does not reason about orderings over pushes if multiple objects need to be rearranged. Furthermore, M4M does not reason about other possible MAPF solutions that lead to different rearrangements and pushes. In this paper, we extend M4M and present Enhanced-M4M (E-M4M) -- a systematic graph search-based solver that searches over orderings of pushes for movable objects that need to be rearranged and different possible rearrangements of the scene. We introduce several algorithmic optimisations to circumvent the increased computational complexity, discuss the space of problems solvable by E-M4M and show that experimentally, both on the real robot and in simulation, it significantly outperforms the original M4M algorithm, as well as other state-of-the-art alternatives when dealing with complex scenes. △ Less

Submitted 23 March, 2023; originally announced March 2023.

Comments: Accepted for publication at the International Conference on Automated Planning and Scheduling (ICAPS), 2023

Planning for Complex Non-prehensile Manipulation Among Movable Objects by Interleaving Multi-Agent Pathfinding and Physics-Based Simulation

Authors: Dhruv Mauria Saxena, Maxim Likhachev

Abstract: Real-world manipulation problems in heavy clutter require robots to reason about potential contacts with objects in the environment. We focus on pick-and-place style tasks to retrieve a target object from a shelf where some `movable' objects must be rearranged in order to solve the task. In particular, our motivation is to allow the robot to reason over and consider non-prehensile rearrangement ac… ▽ More Real-world manipulation problems in heavy clutter require robots to reason about potential contacts with objects in the environment. We focus on pick-and-place style tasks to retrieve a target object from a shelf where some `movable' objects must be rearranged in order to solve the task. In particular, our motivation is to allow the robot to reason over and consider non-prehensile rearrangement actions that lead to complex robot-object and object-object interactions where multiple objects might be moved by the robot simultaneously, and objects might tilt, lean on each other, or topple. To support this, we query a physics-based simulator to forward simulate these interaction dynamics which makes action evaluation during planning computationally very expensive. To make the planner tractable, we establish a connection between the domain of Manipulation Among Movable Objects and Multi-Agent Pathfinding that lets us decompose the problem into two phases our M4M algorithm iterates over. First we solve a multi-agent planning problem that reasons about the configurations of movable objects but does not forward simulate a physics model. Next, an arm motion planning problem is solved that uses a physics-based simulator but does not search over possible configurations of movable objects. We run simulated and real-world experiments with the PR2 robot and compare against relevant baseline algorithms. Our results highlight that M4M generates complex 3D interactions, and solves at least twice as many problems as the baselines with competitive performance. △ Less

Submitted 23 March, 2023; originally announced March 2023.

Comments: Accepted for publication at the IEEE International Conference on Robotics and Automation (ICRA), 2023

Rethinking "Risk" in Algorithmic Systems Through A Computational Narrative Analysis of Casenotes in Child-Welfare

Authors: Devansh Saxena, Erina Seh-Young Moon, Aryan Chaurasia, Yixin Guan, Shion Guha

Abstract: Risk assessment algorithms are being adopted by public sector agencies to make high-stakes decisions about human lives. Algorithms model "risk" based on individual client characteristics to identify clients most in need. However, this understanding of risk is primarily based on easily quantifiable risk factors that present an incomplete and biased perspective of clients. We conducted a computation… ▽ More Risk assessment algorithms are being adopted by public sector agencies to make high-stakes decisions about human lives. Algorithms model "risk" based on individual client characteristics to identify clients most in need. However, this understanding of risk is primarily based on easily quantifiable risk factors that present an incomplete and biased perspective of clients. We conducted a computational narrative analysis of child-welfare casenotes and draw attention to deeper systemic risk factors that are hard to quantify but directly impact families and street-level decision-making. We found that beyond individual risk factors, the system itself poses a significant amount of risk where parents are over-surveilled by caseworkers and lack agency in decision-making processes. We also problematize the notion of risk as a static construct by highlighting the temporality and mediating effects of different risk, protective, systemic, and procedural factors. Finally, we draw caution against using casenotes in NLP-based systems by unpacking their limitations and biases embedded within them. △ Less

Submitted 16 February, 2023; originally announced February 2023.

Performance Analysis of Machine Learning Centered Workload Prediction Models for Cloud

Authors: Deepika Saxena, Jitendra Kumar, Ashutosh Kumar Singh, Stefan Schmid

Abstract: The precise estimation of resource usage is a complex and challenging issue due to the high variability and dimensionality of heterogeneous service types and dynamic workloads. Over the last few years, the prediction of resource usage and traffic has received ample attention from the research community. Many machine learning-based workload forecasting models have been developed by exploiting their… ▽ More The precise estimation of resource usage is a complex and challenging issue due to the high variability and dimensionality of heterogeneous service types and dynamic workloads. Over the last few years, the prediction of resource usage and traffic has received ample attention from the research community. Many machine learning-based workload forecasting models have been developed by exploiting their computational power and learning capabilities. This paper presents the first systematic survey cum performance analysis-based comparative study of diversified machine learning-driven cloud workload prediction models. The discussion initiates with the significance of predictive resource management followed by a schematic description, operational design, motivation, and challenges concerning these workload prediction models. Classification and taxonomy of different prediction approaches into five distinct categories are presented focusing on the theoretical concepts and mathematical functioning of the existing state-of-the-art workload prediction methods. The most prominent prediction approaches belonging to a distinct class of machine learning models are thoroughly surveyed and compared. All five classified machine learning-based workload prediction models are implemented on a common platform for systematic investigation and comparison using three distinct benchmark cloud workload traces via experimental analysis. The essential key performance indicators of state-of-the-art approaches are evaluated for comparison and the paper is concluded by discussing the trade-offs and notable remarks. △ Less

Submitted 5 February, 2023; originally announced February 2023.

Designing Human-Centered Algorithms for the Public Sector: A Case Study of the U.S. Child-Welfare System

Authors: Devansh Saxena

Abstract: The U.S. Child Welfare System (CWS) is increasingly seeking to emulate business models of the private sector centered in efficiency, cost reduction, and innovation through the adoption of algorithms. These data-driven systems purportedly improve decision-making, however, the public sector poses its own set of challenges with respect to the technical, theoretical, cultural, and societal implication… ▽ More The U.S. Child Welfare System (CWS) is increasingly seeking to emulate business models of the private sector centered in efficiency, cost reduction, and innovation through the adoption of algorithms. These data-driven systems purportedly improve decision-making, however, the public sector poses its own set of challenges with respect to the technical, theoretical, cultural, and societal implications of algorithmic decision-making. To fill these gaps, my dissertation comprises four studies that examine: 1) how caseworkers interact with algorithms in their day-to-day discretionary work, 2) the impact of algorithmic decision-making on the nature of practice, organization, and street-level decision-making, 3) how casenotes can help unpack patterns of invisible labor and contextualize decision-making processes, and 4) how casenotes can help uncover deeper systemic constraints and risk factors that are hard to quantify but directly impact families and street-level decision-making. My goal for this research is to investigate systemic disparities and design and develop algorithmic systems that are centered in the theory of practice and improve the quality of human discretionary work. These studies have provided actionable steps for human-centered algorithm design in the public sector. △ Less

Submitted 11 December, 2022; originally announced December 2022.

OSC-MC: Online Secure Communication Model for Cloud Environment

Authors: Deepika Saxena, Ashutosh Kumar Singh

Abstract: A malicious cloud user may exploit outsourced data involved in online communication, co-residency, and hypervisor vulnerabilities to breach and hamper sensitive information, and inject malicious traffic-based congestion, rendering services to other benign users. To address this critical and challenging the problem, this letter proposes an Online Secure Communication Model for Cloud (OSC-MC) by ide… ▽ More A malicious cloud user may exploit outsourced data involved in online communication, co-residency, and hypervisor vulnerabilities to breach and hamper sensitive information, and inject malicious traffic-based congestion, rendering services to other benign users. To address this critical and challenging the problem, this letter proposes an Online Secure Communication Model for Cloud (OSC-MC) by identifying and terminating malicious VMs and inter-VM links prior to the occurrence of security threats. The anomalous network traffic, bandwidth usage, and unauthorized inter-VM links are security breach indicators which guides secure cloud communication and resource allocation. The simulation and comparison of the proposed model with existing approaches reveal that it significantly improves authorised inter-communication links up to 34.5% with a reduction of network hogs, and power consumption by 66.46% and 39.31%, respectively. △ Less

Submitted 11 December, 2022; originally announced December 2022.

Journal ref: IEEE Communications Letters, 2021

A Fault Tolerant Elastic Resource Management Framework Towards High Availability of Cloud Services

Authors: Deepika Saxena, Ishu Gupta, Ashutosh Kumar Singh, Chung-Nan Lee

Abstract: Cloud computing has become inevitable for every digital service which has exponentially increased its usage. However, a tremendous surge in cloud resource demand stave off service availability resulting into outages, performance degradation, load imbalance, and excessive power-consumption. The existing approaches mainly attempt to address the problem by using multi-cloud and running multiple repli… ▽ More Cloud computing has become inevitable for every digital service which has exponentially increased its usage. However, a tremendous surge in cloud resource demand stave off service availability resulting into outages, performance degradation, load imbalance, and excessive power-consumption. The existing approaches mainly attempt to address the problem by using multi-cloud and running multiple replicas of a virtual machine (VM) which accounts for high operational-cost. This paper proposes a Fault Tolerant Elastic Resource Management (FT-ERM) framework that addresses aforementioned problem from a different perspective by inducing high-availability in servers and VMs. Specifically, (1) an online failure predictor is developed to anticipate failure-prone VMs based on predicted resource contention; (2) the operational status of server is monitored with the help of power analyser, resource estimator and thermal analyser to identify any failure due to overloading and overheating of servers proactively; and (3) failure-prone VMs are assigned to proposed fault-tolerance unit composed of decision matrix and safe box to trigger VM migration and handle any outage beforehand while maintaining desired level of availability for cloud users. The proposed framework is evaluated and compared against state-of-the-arts by executing experiments using two real-world datasets. FT-ERM improved the availability of the services up to 34.47% and scales down VM-migration and power-consumption up to 88.6% and 62.4%, respectively over without FT-ERM approach. △ Less

Submitted 7 December, 2022; originally announced December 2022.

Comments: IEEE Transactions of Network and Service Management, 2022

A proactive autoscaling and energy-efficient VM allocation framework using online multi-resource neural network for cloud data center

Authors: Deepika Saxena, Ashutosh Kumar Singh

Abstract: This work proposes an energy-efficient resource provisioning and allocation framework to meet the dynamic demands of future applications. The frequent variations in a cloud user's resource demand lead 'to the problem of excess power consumption, resource wastage, performance, and Quality-of-Service degradation. The proposed framework addresses these challenges by matching the application's predict… ▽ More This work proposes an energy-efficient resource provisioning and allocation framework to meet the dynamic demands of future applications. The frequent variations in a cloud user's resource demand lead 'to the problem of excess power consumption, resource wastage, performance, and Quality-of-Service degradation. The proposed framework addresses these challenges by matching the application's predicted resource requirement with the resource capacity of VMs precisely and thereby consolidating the entire load on the minimum number of energy-efficient physical machines. The three consecutive contributions of the proposed work are: Online Multi-Resource Feed-forward Neural Network to forecast the multiple resource demands concurrently for future applications; autoscaling of VMs based on the clustering of the predicted resource requirements; allocation of the scaled VMs on the energy-efficient PMs. The integrated approach successively optimizes resource utilization, saves energy and automatically adapts to the changes in future application resource demand. The proposed framework is evaluated by using real workload traces of the benchmark Google Cluster Dataset and compared against different scenarios including energy-efficient VM placement with resource prediction only, VMP without resource prediction and autoscaling, and optimal VMP with autoscaling based on actual resource utilization. The observed results demonstrate that the proposed integrated approach achieves near-optimal performance against optimal VMP and outperforms rest of the VMPs in terms of power saving and resource utilization up to 88.5% and 21.12% respectively. In addition, the OM-FNN predictor shows better accuracy, lesser time and space complexity over a traditional single-input and single-output feed-forward neural network predictor. △ Less

Submitted 4 December, 2022; originally announced December 2022.

Journal ref: Neurocomputing, 2020

A High Availability Management Model based on VM Significance Ranking and Resource Estimation for Cloud Applications

Authors: Deepika Saxena, Ashutosh Kumar Singh

Abstract: Massive upsurge in cloud resource usage stave off service availability resulting into outages, resource contention, and excessive power-consumption. The existing approaches have addressed this challenge by providing multi-cloud, VM migration, and running multiple replicas of each VM which accounts for high expenses of cloud data centre (CDC). In this context, a novel VM Significance Ranking and Re… ▽ More Massive upsurge in cloud resource usage stave off service availability resulting into outages, resource contention, and excessive power-consumption. The existing approaches have addressed this challenge by providing multi-cloud, VM migration, and running multiple replicas of each VM which accounts for high expenses of cloud data centre (CDC). In this context, a novel VM Significance Ranking and Resource Estimation based High Availability Management (SRE-HM) Model is proposed to enhance service availability for users with optimized cost for CDC. The model estimates resource contention based server failure and organises needed resources beforehand for maintaining desired level of service availability. A significance ranking parameter is introduced and computed for each VM, executing critical or non-critical tasks followed by the selection of an admissible High Availability (HA) strategy respective to its significance and user specified constraints. It enables cost optimization for CDC by rendering failure tolerance strategies for significant VMs only instead of all the VMs. The proposed model is evaluated and compared against state-of-the-arts by executing experiments using Google Cluster dataset. SRE-HM improved the services availability up to 19.56% and scales down the number of active servers and power-consumption up to 26.67% and 19.1%, respectively over HA without SRE-HM. △ Less

Submitted 29 November, 2022; originally announced November 2022.

Journal ref: IEEE Transactions on Services Computing, 2022

A Quantum Approach Towards the Adaptive Prediction of Cloud Workloads

Authors: Ashutosh Kumar Singh, Deepika Saxena, Jitendra Kumar, Vrinda Gupta

Abstract: This work presents a novel Evolutionary Quantum Neural Network (EQNN) based workload prediction model for Cloud datacenter. It exploits the computational efficiency of quantum computing by encoding workload information into qubits and propagating this information through the network to estimate the workload or resource demands with enhanced accuracy proactively. The rotation and reverse rotation e… ▽ More This work presents a novel Evolutionary Quantum Neural Network (EQNN) based workload prediction model for Cloud datacenter. It exploits the computational efficiency of quantum computing by encoding workload information into qubits and propagating this information through the network to estimate the workload or resource demands with enhanced accuracy proactively. The rotation and reverse rotation effects of the Controlled-NOT (C-NOT) gate serve activation function at the hidden and output layers to adjust the qubit weights. In addition, a Self Balanced Adaptive Differential Evolution (SB-ADE) algorithm is developed to optimize qubit network weights. The accuracy of the EQNN prediction model is extensively evaluated and compared with seven state-of-the-art methods using eight real world benchmark datasets of three different categories. Experimental results reveal that the use of the quantum approach to evolutionary neural network substantially improves the prediction accuracy up to 91.6% over the existing approaches. △ Less

Submitted 26 November, 2022; originally announced November 2022.

Journal ref: IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2021

an intelligent security centered resource-efficient resource management model for cloud computing environments

Authors: Deepika Saxena, Ashutosh Kumar Singh

Abstract: This paper proposes a conceptual model for a secure and performance-efficient workload management model in cloud environments. In this model, a resource management unit is employed for energy and performance proficient allocation of virtual machines while ensuring the secure processing of users' applications by defending against data breaches due to unauthorized access to virtual machines in real-… ▽ More This paper proposes a conceptual model for a secure and performance-efficient workload management model in cloud environments. In this model, a resource management unit is employed for energy and performance proficient allocation of virtual machines while ensuring the secure processing of users' applications by defending against data breaches due to unauthorized access to virtual machines in real-time. The resource management unit is guided by a secure virtual machine management unit which is designed to generate information regarding unauthorized access or inter-communication links among active virtual machines. Also, a workload analyzer unit operates concurrently to estimate resource utilization information to assist the resource management unit in the performance-efficient allocation of virtual machines. Contrary to prior works which engage access control mechanisms, encryption, and decryption of data before the transfer and the use of tunneling for prevention of unauthorized access to virtual machines which raises excess computational cost overhead, the proposed model operates diversely for efficiently serving the same purpose. △ Less

Submitted 29 October, 2022; originally announced October 2022.

Comments: This article contains 12 pages, and 3 figures. It presents a conceptual resource management model for cloud data center environments which is the outcome of the authors' six to seven years of research work in the area of Cloud Computing

Security and Privacy in Big Data Sharing: State-of-the-Art and Research Directions

Authors: Houda Ferradi, Jiannong Cao, Shan Jiang, Yinfeng Cao, Divya Saxena

Abstract: Big Data Sharing (BDS) refers to the act of the data owners to share data so that users can find, access and use data according to the agreement. In recent years, BDS has been an emerging topic due to its wide applications, such as big data trading and cross-domain data analytics. However, as the multiple parties are involved in a BDS platform, the issue of security and privacy violation arises. T… ▽ More Big Data Sharing (BDS) refers to the act of the data owners to share data so that users can find, access and use data according to the agreement. In recent years, BDS has been an emerging topic due to its wide applications, such as big data trading and cross-domain data analytics. However, as the multiple parties are involved in a BDS platform, the issue of security and privacy violation arises. There have been a number of solutions for enhancing security and preserving privacy at different big data operations (e.g., data operation, data searching, data sharing and data outsourcing). To the best of our knowledge, there is no existing survey that has particularly focused on the broad and systematic developments of these security and privacy solutions. In this study, we conduct a comprehensive survey of the state-of-the-art solutions introduced to tackle security and privacy issues in BDS. For a better understanding, we first introduce a general model for BDS and identify the security and privacy requirements. We discuss and classify the state-of-the-art security and privacy solutions for BDS according to the identified requirements. Finally, based on the insights gained, we present and discuss new promising research directions. △ Less

Submitted 17 October, 2022; originally announced October 2022.

Comments: 33 pages, 8 figures

MSC Class: 68M25; 94A60 ACM Class: K.6.5; E.3

AdaptCL: Adaptive Continual Learning for Tackling Heterogeneity in Sequential Datasets

Authors: Yuqing Zhao, Divya Saxena, Jiannong Cao

Abstract: Managing heterogeneous datasets that vary in complexity, size, and similarity in continual learning presents a significant challenge. Task-agnostic continual learning is necessary to address this challenge, as datasets with varying similarity pose difficulties in distinguishing task boundaries. Conventional task-agnostic continual learning practices typically rely on rehearsal or regularization te… ▽ More Managing heterogeneous datasets that vary in complexity, size, and similarity in continual learning presents a significant challenge. Task-agnostic continual learning is necessary to address this challenge, as datasets with varying similarity pose difficulties in distinguishing task boundaries. Conventional task-agnostic continual learning practices typically rely on rehearsal or regularization techniques. However, rehearsal methods may struggle with varying dataset sizes and regulating the importance of old and new data due to rigid buffer sizes. Meanwhile, regularization methods apply generic constraints to promote generalization but can hinder performance when dealing with dissimilar datasets lacking shared features, necessitating a more adaptive approach. In this paper, we propose AdaptCL, a novel adaptive continual learning method to tackle heterogeneity in sequential datasets. AdaptCL employs fine-grained data-driven pruning to adapt to variations in data complexity and dataset size. It also utilizes task-agnostic parameter isolation to mitigate the impact of varying degrees of catastrophic forgetting caused by differences in data similarity. Through a two-pronged case study approach, we evaluate AdaptCL on both datasets of MNIST Variants and DomainNet, as well as datasets from different domains. The latter include both large-scale, diverse binary-class datasets and few-shot, multi-class datasets. Across all these scenarios, AdaptCL consistently exhibits robust performance, demonstrating its flexibility and general applicability in handling heterogeneous datasets. △ Less

Submitted 11 December, 2023; v1 submitted 22 July, 2022; originally announced July 2022.

Comments: This article has been accepted by TNNLS

Hierarchical Reinforcement Learning with Opponent Modeling for Distributed Multi-agent Cooperation

Authors: Zhixuan Liang, Jiannong Cao, Shan Jiang, Divya Saxena, Huafeng Xu

Abstract: Many real-world applications can be formulated as multi-agent cooperation problems, such as network packet routing and coordination of autonomous vehicles. The emergence of deep reinforcement learning (DRL) provides a promising approach for multi-agent cooperation through the interaction of the agents and environments. However, traditional DRL solutions suffer from the high dimensions of multiple… ▽ More Many real-world applications can be formulated as multi-agent cooperation problems, such as network packet routing and coordination of autonomous vehicles. The emergence of deep reinforcement learning (DRL) provides a promising approach for multi-agent cooperation through the interaction of the agents and environments. However, traditional DRL solutions suffer from the high dimensions of multiple agents with continuous action space during policy search. Besides, the dynamicity of agents' policies makes the training non-stationary. To tackle the issues, we propose a hierarchical reinforcement learning approach with high-level decision-making and low-level individual control for efficient policy search. In particular, the cooperation of multiple agents can be learned in high-level discrete action space efficiently. At the same time, the low-level individual control can be reduced to single-agent reinforcement learning. In addition to hierarchical reinforcement learning, we propose an opponent modeling network to model other agents' policies during the learning process. In contrast to end-to-end DRL approaches, our approach reduces the learning complexity by decomposing the overall task into sub-tasks in a hierarchical way. To evaluate the efficiency of our approach, we conduct a real-world case study in the cooperative lane change scenario. Both simulation and real-world experiments show the superiority of our approach in the collision rate and convergence speed. △ Less

Submitted 25 June, 2022; originally announced June 2022.

Comments: 11 pages, 13 figures, 2 tables

ACM Class: I.2.9; I.2.11

From Multi-agent to Multi-robot: A Scalable Training and Evaluation Platform for Multi-robot Reinforcement Learning

Authors: Zhiuxan Liang, Jiannong Cao, Shan Jiang, Divya Saxena, Jinlin Chen, Huafeng Xu

Abstract: Multi-agent reinforcement learning (MARL) has been gaining extensive attention from academia and industries in the past few decades. One of the fundamental problems in MARL is how to evaluate different approaches comprehensively. Most existing MARL methods are evaluated in either video games or simplistic simulated scenarios. It remains unknown how these methods perform in real-world scenarios, es… ▽ More Multi-agent reinforcement learning (MARL) has been gaining extensive attention from academia and industries in the past few decades. One of the fundamental problems in MARL is how to evaluate different approaches comprehensively. Most existing MARL methods are evaluated in either video games or simplistic simulated scenarios. It remains unknown how these methods perform in real-world scenarios, especially multi-robot systems. This paper introduces a scalable emulation platform for multi-robot reinforcement learning (MRRL) called SMART to meet this need. Precisely, SMART consists of two components: 1) a simulation environment that provides a variety of complex interaction scenarios for training and 2) a real-world multi-robot system for realistic performance evaluation. Besides, SMART offers agent-environment APIs that are plug-and-play for algorithm implementation. To illustrate the practicality of our platform, we conduct a case study on the cooperative driving lane change scenario. Building off the case study, we summarize several unique challenges of MRRL, which are rarely considered previously. Finally, we open-source the simulation environments, associated benchmark tasks, and state-of-the-art baselines to encourage and empower MRRL research. △ Less

Submitted 20 June, 2022; originally announced June 2022.

Comments: 13 pages

ACM Class: I.2.9; I.2.11

How to Train a (Bad) Algorithmic Caseworker: A Quantitative Deconstruction of Risk Assessments in Child-Welfare

Authors: Devansh Saxena, Charlie Repaci, Melanie Sage, Shion Guha

Abstract: Child welfare (CW) agencies use risk assessment tools as a means to achieve evidence-based, consistent, and unbiased decision-making. These risk assessments act as data collection mechanisms and have further evolved into algorithmic systems in recent years. Moreover, several of these algorithms have reinforced biased theoretical constructs and predictors because of the easy availability of structu… ▽ More Child welfare (CW) agencies use risk assessment tools as a means to achieve evidence-based, consistent, and unbiased decision-making. These risk assessments act as data collection mechanisms and have further evolved into algorithmic systems in recent years. Moreover, several of these algorithms have reinforced biased theoretical constructs and predictors because of the easy availability of structured assessment data. In this study, we critically examine the Washington Assessment of Risk Model (WARM), a prominent risk assessment tool that has been adopted by over 30 states in the United States and has been repurposed into more complex algorithms. We compared WARM against the narrative coding of casenotes written by caseworkers who used WARM. We found significant discrepancies between the casenotes and WARM data where WARM scores did not not mirror caseworkers' notes about family risk. We provide the SIGCHI community with some initial findings from the quantitative de-construction of a child-welfare algorithm. △ Less

Submitted 19 December, 2022; v1 submitted 10 March, 2022; originally announced March 2022.

Unpacking Invisible Work Practices, Constraints, and Latent Power Relationships in Child Welfare through Casenote Analysis

Authors: Devansh Saxena, Erina Seh-Young Moon, Dahlia Shehata, Shion Guha

Abstract: Caseworkers are trained to write detailed narratives about families in Child-Welfare (CW) which informs collaborative high-stakes decision-making. Unlike other administrative data, these narratives offer a more credible source of information with respect to workers' interactions with families as well as underscore the role of systemic factors in decision-making. SIGCHI researchers have emphasized… ▽ More Caseworkers are trained to write detailed narratives about families in Child-Welfare (CW) which informs collaborative high-stakes decision-making. Unlike other administrative data, these narratives offer a more credible source of information with respect to workers' interactions with families as well as underscore the role of systemic factors in decision-making. SIGCHI researchers have emphasized the need to understand human discretion at the street-level to be able to design human-centered algorithms for the public sector. In this study, we conducted computational text analysis of casenotes at a child-welfare agency in the midwestern United States and highlight patterns of invisible street-level discretionary work and latent power structures that have direct implications for algorithm design. Casenotes offer a unique lens for policymakers and CW leadership towards understanding the experiences of on-the-ground caseworkers. As a result of this study, we highlight how street-level discretionary work needs to be supported by sociotechnical systems developed through worker-centered design. This study offers the first computational inspection of casenotes and introduces them to the SIGCHI community as a critical data source for studying complex sociotechnical systems. △ Less

Submitted 10 March, 2022; originally announced March 2022.

Time Series Clustering for Human Behavior Pattern Mining

Authors: Rohan Kabra, Divya Saxena, Dhaval Patel, Jiannong Cao

Abstract: Human behavior modeling deals with learning and understanding behavior patterns inherent in humans' daily routines. Existing pattern mining techniques either assume human dynamics is strictly periodic, or require the number of modes as input, or do not consider uncertainty in the sensor data. To handle these issues, in this paper, we propose a novel clustering approach for modeling human behavior… ▽ More Human behavior modeling deals with learning and understanding behavior patterns inherent in humans' daily routines. Existing pattern mining techniques either assume human dynamics is strictly periodic, or require the number of modes as input, or do not consider uncertainty in the sensor data. To handle these issues, in this paper, we propose a novel clustering approach for modeling human behavior (named, MTpattern) from time-series data. For mining frequent human behavior patterns effectively, we utilize a three-stage pipeline: (1) represent time series data into a sequence of regularly sampled equal-sized unit time intervals for better analysis, (2) a new distance measure scheme is proposed to cluster similar sequences which can handle temporal variation and uncertainty in the data, and (3) exploit an exemplar-based clustering mechanism and fine-tune its parameters to output minimum number of clusters with given permissible distance constraints and without knowing the number of modes present in the data. Then, the average of all sequences in a cluster is considered as a human behavior pattern. Empirical studies on two real-world datasets and a simulated dataset demonstrate the effectiveness of MTpattern with respect to internal and external measures of clustering. △ Less

Submitted 24 October, 2021; v1 submitted 14 October, 2021; originally announced October 2021.

Comments: 16 pages

AMRA*: Anytime Multi-Resolution Multi-Heuristic A*

Authors: Dhruv Mauria Saxena, Tushar Kusnur, Maxim Likhachev

Abstract: Heuristic search-based motion planning algorithms typically discretise the search space in order to solve the shortest path problem. Their performance is closely related to this discretisation. A fine discretisation allows for better approximations of the continuous search space, but makes the search for a solution more computationally costly. A coarser resolution might allow the algorithms to fin… ▽ More Heuristic search-based motion planning algorithms typically discretise the search space in order to solve the shortest path problem. Their performance is closely related to this discretisation. A fine discretisation allows for better approximations of the continuous search space, but makes the search for a solution more computationally costly. A coarser resolution might allow the algorithms to find solutions quickly at the expense of quality. For large state spaces, it can be beneficial to search for solutions across multiple resolutions even though defining the discretisations is challenging. The recently proposed algorithm Multi-Resolution A* (MRA*) searches over multiple resolutions. It traverses large areas of obstacle-free space and escapes local minima at a coarse resolution. It can also navigate so-called narrow passageways at a finer resolution. In this work, we develop AMRA*, an anytime version of MRA*. AMRA* tries to find a solution quickly using the coarse resolution as much as possible. It then refines the solution by relying on the fine resolution to discover better paths that may not have been available at the coarse resolution. In addition to being anytime, AMRA* can also leverage information sharing between multiple heuristics. We prove that AMRA* is complete and optimal (in-the-limit of time) with respect to the finest resolution. We show its performance on 2D grid navigation and 4D kinodynamic planning problems. △ Less

Submitted 23 March, 2023; v1 submitted 11 October, 2021; originally announced October 2021.

Comments: Published at IEEE International Conference on Robotics and Automation (ICRA), 2022. Code available at https://github.com/dhruvms/amra

A Survey and Comparative Study on Multi-Cloud Architectures: Emerging Issues And Challenges For Cloud Federation

Authors: Deepika Saxena, Rishabh Gupta, Ashutosh Kumar Singh

Abstract: Multi-cloud concept has broaden the world of cloud computing and has become a buzzword today. The word Multi-cloud envisions utilization of services from multiple heterogeneous cloud providers via a single architecture at customer premises. Though cloud computing has many issues and offers open research challenges, still the academics and industrial research has paved a pathway for multi-cloud env… ▽ More Multi-cloud concept has broaden the world of cloud computing and has become a buzzword today. The word Multi-cloud envisions utilization of services from multiple heterogeneous cloud providers via a single architecture at customer premises. Though cloud computing has many issues and offers open research challenges, still the academics and industrial research has paved a pathway for multi-cloud environment. The concept of multi-cloud is in maturing phase, and many research projects are in progress to provide a multi-cloud architecture which is successfully enabled in all the respects like easy configuration, security, management etc. In this paper, concepts, challenges, requirement and future directions for multi-cloud environment are discussed. A survey of existing approaches and solutions provided by different multi-cloud architectures is entailed along with analysis of the pros and cons of different architectures while comparing the same. △ Less

Submitted 29 August, 2021; originally announced August 2021.

Comments: 14 pages, 11 figures

Artificial Intelligence in the Global South (AI4D): Potential and Risks

Authors: P. J. Wall, Deepak Saxena, Suzana Brown

Abstract: Artificial intelligence is becoming more widely available in all parts of the world. This has created many previously unforeseen possibilities for addressing the challenges outlined in the Sustainable Development Goals in the Global South. However, the use of AI in such contexts brings with it a unique set of risks and challenges. Among these are the potential for Governments to use such technolog… ▽ More Artificial intelligence is becoming more widely available in all parts of the world. This has created many previously unforeseen possibilities for addressing the challenges outlined in the Sustainable Development Goals in the Global South. However, the use of AI in such contexts brings with it a unique set of risks and challenges. Among these are the potential for Governments to use such technologies to suppress their own people, and the ethical questions arising from implementing AI primarily designed and developed in the Global North into vastly different social, cultural, and political environments in the Global South. This paper examines the key issues and questions arising in the emerging sub-field of AI for global development (AI4D) and the potential and risks associated with using such technologies in the Global South. We propose that although there are many risks associated with the use of AI, the potential benefits are enough to warrant detailed research and investigation of the most appropriate and effective ways to design, develop, implement, and use such technologies in the Global South. We conclude by calling for the wider ICT4D community to continue to conduct detailed research and investigation of all aspects of AI4D. △ Less

Submitted 23 August, 2021; originally announced August 2021.

Comments: In proceedings of the 1st Virtual Conference on Implications of Information and Digital Technologies for Development, 2021

Investigating Personalisation-Privacy Paradox Among Young Irish Consumers: A Case of Smart Speakers

Authors: Caoimhe O'Maonaigh, Deepak Saxena

Abstract: Personalisation refers to the catering of online services to match consumer's interests. In order to provide personalised service, companies gather data on the consumer. In this situation, consumers must navigate a trade-off when they want the benefits of personalised information and services while simultaneously wish to protect themselves from privacy risks. However, despite many individuals clai… ▽ More Personalisation refers to the catering of online services to match consumer's interests. In order to provide personalised service, companies gather data on the consumer. In this situation, consumers must navigate a trade-off when they want the benefits of personalised information and services while simultaneously wish to protect themselves from privacy risks. However, despite many individuals claiming that privacy is an essential right to them, they behave contradictorily in online environments by not engaging in privacy-preserving behaviours. This paradox is known as the personalisation-privacy Paradox. The personalisation-privacy paradox has been studied in many different scenarios, ranging from location-based advertising to online shopping. The objective of this study is to investigate the personalisation-privacy paradox in the context of smart speakers. Based on an exploratory study with young Irish consumers, this study suggests a difference between the users and non-users of smart speakers in terms of their perception of privacy risks and corresponding privacy-preserving behaviours. In so doing, it also explains the existence of the personalisation-privacy paradox and offers insights for further research. △ Less

Submitted 23 August, 2021; originally announced August 2021.

Comments: In proceedings of the 1st Virtual Conference on Implications of Information and Digital Technologies for Development, 2021

Data Security and Privacy in Cloud Computing: Concepts and Emerging Trends

Authors: Rishabh Gupta, Deepika Saxena, Ashutosh Kumar Singh

Abstract: Millions of users across the world leverages data processing and sharing benefits from cloud environment. Data security and privacy are inevitable requirement of cloud environment. Massive usage and sharing of data among users opens door to security loopholes. This paper envisages a discussion of cloud environment, its utilities, challenges, and emerging research trends confined to secure processi… ▽ More Millions of users across the world leverages data processing and sharing benefits from cloud environment. Data security and privacy are inevitable requirement of cloud environment. Massive usage and sharing of data among users opens door to security loopholes. This paper envisages a discussion of cloud environment, its utilities, challenges, and emerging research trends confined to secure processing and sharing of data. △ Less

Submitted 21 August, 2021; originally announced August 2021.

Comments: 9 pages, 3 figures

On the performance of GPU accelerated q-LSKUM based meshfree solvers in Fortran, C++, Python, and Julia

Authors: Nischay Ram Mamidi, Kumar Prasun, Dhruv Saxena, Anil Nemili, Bharatkumar Sharma, S. M. Deshpande

Abstract: This report presents a comprehensive analysis of the performance of GPU accelerated meshfree CFD solvers for two-dimensional compressible flows in Fortran, C++, Python, and Julia. The programming model CUDA is used to develop the GPU codes. The meshfree solver is based on the least squares kinetic upwind method with entropy variables (q-LSKUM). To assess the computational efficiency of the GPU sol… ▽ More This report presents a comprehensive analysis of the performance of GPU accelerated meshfree CFD solvers for two-dimensional compressible flows in Fortran, C++, Python, and Julia. The programming model CUDA is used to develop the GPU codes. The meshfree solver is based on the least squares kinetic upwind method with entropy variables (q-LSKUM). To assess the computational efficiency of the GPU solvers and to compare their relative performance, benchmark calculations are performed on seven levels of point distribution. To analyse the difference in their run-times, the computationally intensive kernel is profiled. Various performance metrics are investigated from the profiled data to determine the cause of observed variation in run-times. To address some of the performance related issues, various optimisation strategies are employed. The optimised GPU codes are compared with the naive codes, and conclusions are drawn from their performance. △ Less

Submitted 16 August, 2021; originally announced August 2021.

Comments: 42 pages, 3 figures

ACM Class: D.3.0; J.2

A Secure and Multi-objective Virtual Machine Placement Framework for Cloud Data Centre

Authors: Deepika Saxena, Ishu Gupta, Jitendra Kumar, Ashutosh Kumar Singh, Xiaoqing Wen

Abstract: To facilitate cost-effective and elastic computing benefits to the cloud users, the energy-efficient and secure allocation of virtual machines (VMs) plays a significant role at the data centre. The inefficient VM Placement (VMP) and sharing of common physical machines among multiple users leads to resource wastage, excessive power consumption, increased inter-communication cost and security breach… ▽ More To facilitate cost-effective and elastic computing benefits to the cloud users, the energy-efficient and secure allocation of virtual machines (VMs) plays a significant role at the data centre. The inefficient VM Placement (VMP) and sharing of common physical machines among multiple users leads to resource wastage, excessive power consumption, increased inter-communication cost and security breaches. To address the aforementioned challenges, a novel secure and multi-objective virtual machine placement (SM-VMP) framework is proposed with an efficient VM migration. The proposed framework ensures an energy-efficient distribution of physical resources among VMs that emphasizes secure and timely execution of user application by reducing inter-communication delay. The VMP is carried out by applying the proposed Whale Optimization Genetic Algorithm (WOGA), inspired by whale evolutionary optimization and non-dominated sorting based genetic algorithms. The performance evaluation for static and dynamic VMP and comparison with recent state-of-the-arts observed a notable reduction in shared servers, inter-communication cost, power consumption and execution time up to 28.81%, 25.7%, 35.9% and 82.21%, respectively and increased resource utilization up to 30.21%. △ Less

Submitted 28 July, 2021; originally announced July 2021.

Comments: This article has been accepted for inclusion in a future issue of IEEE Systems Journal (2021)

A Framework of High-Stakes Algorithmic Decision-Making for the Public Sector Developed through a Case Study of Child-Welfare

Authors: Devansh Saxena, Karla Badillo-Urquiola, Pamela Wisniewski, Shion Guha

Abstract: Algorithms have permeated throughout civil government and society, where they are being used to make high-stakes decisions about human lives. In this paper, we first develop a cohesive framework of algorithmic decision-making adapted for the public sector (ADMAPS) that reflects the complex socio-technical interactions between \textit{human discretion}, \textit{bureaucratic processes}, and \textit{… ▽ More Algorithms have permeated throughout civil government and society, where they are being used to make high-stakes decisions about human lives. In this paper, we first develop a cohesive framework of algorithmic decision-making adapted for the public sector (ADMAPS) that reflects the complex socio-technical interactions between \textit{human discretion}, \textit{bureaucratic processes}, and \textit{algorithmic decision-making} by synthesizing disparate bodies of work in the fields of Human-Computer Interaction (HCI), Science and Technology Studies (STS), and Public Administration (PA). We then applied the ADMAPS framework to conduct a qualitative analysis of an in-depth, eight-month ethnographic case study of the algorithms in daily use within a child-welfare agency that serves approximately 900 families and 1300 children in the mid-western United States. Overall, we found there is a need to focus on strength-based algorithmic outcomes centered in social ecological frameworks. In addition, algorithmic systems need to support existing bureaucratic processes and augment human discretion, rather than replace it. Finally, collective buy-in in algorithmic systems requires trust in the target outcomes at both the practitioner and bureaucratic levels. As a result of our study, we propose guidelines for the design of high-stakes algorithmic decision-making tools in the child-welfare system, and more generally, in the public sector. We empirically validate the theoretically derived ADMAPS framework to demonstrate how it can be useful for systematically making pragmatic decisions about the design of algorithms for the public sector. △ Less

Submitted 12 October, 2021; v1 submitted 7 July, 2021; originally announced July 2021.

workload forecasting and resource management models based on machine learning for cloud computing environments

Authors: Deepika Saxena, Ashutosh Kumar Singh

Abstract: The workload prediction and resource allocation significantly play an inevitable role in production of an efficient cloud environment. The proactive estimation of future workload followed by decision of resource allocation have become a prior solution to handle other in-built challenges like the under/over-loading of physical machines, resource wastage, Quality-of-Services (QoS) violations, load b… ▽ More The workload prediction and resource allocation significantly play an inevitable role in production of an efficient cloud environment. The proactive estimation of future workload followed by decision of resource allocation have become a prior solution to handle other in-built challenges like the under/over-loading of physical machines, resource wastage, Quality-of-Services (QoS) violations, load balancing,VM migration and many more. In this context, the paper presents a comprehensive survey of workload forecasting and predictive resource management models in cloud environment. A conceptual framework for workload forecasting and resource management, categorization of existing machine learning based resources allocation techniques, and major challenges of inefficient distribution of physical resource distribution are discussed pertaining to cloud computing. Thereafter, a thorough survey of existing state-of-the-art contributions empowering machine learning based approaches in the field of cloud workload prediction and resource management are rendered. Finally, the paper explores and concludes various emerging challenges and future research directions concerning elastic resource management in cloud environment. △ Less

Submitted 29 June, 2021; originally announced June 2021.

Comments: 17 pages,5 figures

Manipulation Planning Among Movable Obstacles Using Physics-Based Adaptive Motion Primitives

Authors: Dhruv Mauria Saxena, Muhammad Suhail Saleem, Maxim Likhachev

Abstract: Robot manipulation in cluttered scenes often requires contact-rich interactions with objects. It can be more economical to interact via non-prehensile actions, for example, push through other objects to get to the desired grasp pose, instead of deliberate prehensile rearrangement of the scene. For each object in a scene, depending on its properties, the robot may or may not be allowed to make cont… ▽ More Robot manipulation in cluttered scenes often requires contact-rich interactions with objects. It can be more economical to interact via non-prehensile actions, for example, push through other objects to get to the desired grasp pose, instead of deliberate prehensile rearrangement of the scene. For each object in a scene, depending on its properties, the robot may or may not be allowed to make contact with, tilt, or topple it. To ensure that these constraints are satisfied during non-prehensile interactions, a planner can query a physics-based simulator to evaluate the complex multi-body interactions caused by robot actions. Unfortunately, it is infeasible to query the simulator for thousands of actions that need to be evaluated in a typical planning problem as each simulation is time-consuming. In this work, we show that (i) manipulation tasks (specifically pick-and-place style tasks from a tabletop or a refrigerator) can often be solved by restricting robot-object interactions to adaptive motion primitives in a plan, (ii) these actions can be incorporated as subgoals within a multi-heuristic search framework, and (iii) limiting interactions to these actions can help reduce the time spent querying the simulator during planning by up to 40x in comparison to baseline algorithms. Our algorithm is evaluated in simulation and in the real-world on a PR2 robot using PyBullet as our physics-based simulator. Supplementary video: \url{https://youtu.be/ABQc7JbeJPM}. △ Less

Submitted 23 March, 2023; v1 submitted 8 February, 2021; originally announced February 2021.

Comments: Published at IEEE International Conference on Robotics and Automation (ICRA), 2021

Enhanced Innovized Repair Operator for Evolutionary Multi- and Many-objective Optimization

Authors: Sukrit Mittal, Dhish Kumar Saxena, Kalyanmoy Deb, Erik Goodman

Abstract: "Innovization" is a task of learning common relationships among some or all of the Pareto-optimal (PO) solutions in multi- and many-objective optimization problems. Recent studies have shown that a chronological sequence of non-dominated solutions obtained in consecutive iterations during an optimization run also possess salient patterns that can be used to learn problem features to help create ne… ▽ More "Innovization" is a task of learning common relationships among some or all of the Pareto-optimal (PO) solutions in multi- and many-objective optimization problems. Recent studies have shown that a chronological sequence of non-dominated solutions obtained in consecutive iterations during an optimization run also possess salient patterns that can be used to learn problem features to help create new and improved solutions. In this paper, we propose a machine-learning- (ML-) assisted modelling approach that learns the modifications in design variables needed to advance population members towards the Pareto-optimal set. We then propose to use the resulting ML model as an additional innovized repair (IR2) operator to be applied on offspring solutions created by the usual genetic operators, as a novel mean of improving their convergence properties. In this paper, the well-known random forest (RF) method is used as the ML model and is integrated with various evolutionary multi- and many-objective optimization algorithms, including NSGA-II, NSGA-III, and MOEA/D. On several test problems ranging from two to five objectives, we demonstrate improvement in convergence behaviour using the proposed IR2-RF operator. Since the operator does not demand any additional solution evaluations, instead using the history of gradual and progressive improvements in solutions over generations, the proposed ML-based optimization opens up a new direction of optimization algorithm development with advances in AI and ML approaches. △ Less

Submitted 21 November, 2020; originally announced November 2020.

Report number: COIN Lab Report: 2020020

Search-based Planning for Active Sensing in Goal-Directed Coverage Tasks

Authors: Tushar Kusnur, Dhruv Mauria Saxena, Maxim Likhachev

Abstract: Path planning for robotic coverage is the task of determining a collision-free robot trajectory that observes all points of interest in an environment. Robots employed for such tasks are often capable of exercising active control over onboard observational sensors during navigation. In this paper, we tackle the problem of planning robot and sensor trajectories that maximize information gain in suc… ▽ More Path planning for robotic coverage is the task of determining a collision-free robot trajectory that observes all points of interest in an environment. Robots employed for such tasks are often capable of exercising active control over onboard observational sensors during navigation. In this paper, we tackle the problem of planning robot and sensor trajectories that maximize information gain in such tasks where the robot needs to cover points of interest with its sensor footprint. Search-based planners in general guarantee completeness and provable bounds on suboptimality with respect to an underlying graph discretization. However, searching for kinodynamically feasible paths in the joint space of robot and sensor state variables with standard search is computationally expensive. We propose two alternative search-based approaches to this problem. The first solves for robot and sensor trajectories independently in decoupled state spaces while maintaining a history of sensor headings during the search. The second is a two-step approach that first quickly computes a solution in decoupled state spaces and then refines it by searching its local neighborhood in the joint space for a better solution. We evaluate our approaches in simulation with a kinodynamically constrained unmanned aerial vehicle performing coverage over a 2D environment and show their benefits. △ Less

Submitted 14 November, 2020; originally announced November 2020.

Comments: Submitted to ICRA 2021

A Novel Column Generation Heuristic for Airline Crew Pairing Optimization with Large-scale Complex Flight Networks

Authors: Divyam Aggarwal, Dhish Kumar Saxena, Saaju Pualose, Thomas Bäck, Michael Emmerich

Abstract: Crew Pairing Optimization (CPO) is critical for an airlines' business viability, given that the crew operating cost is second only to the fuel cost. CPO aims at generating a set of flight sequences (crew pairings) to cover all scheduled flights, at minimum cost, while satisfying several legality constraints. The state-of-the-art heavily relies on relaxing the underlying Integer Programming Problem… ▽ More Crew Pairing Optimization (CPO) is critical for an airlines' business viability, given that the crew operating cost is second only to the fuel cost. CPO aims at generating a set of flight sequences (crew pairings) to cover all scheduled flights, at minimum cost, while satisfying several legality constraints. The state-of-the-art heavily relies on relaxing the underlying Integer Programming Problem into a Linear Programming Problem, which in turn is solved through the Column Generation (CG) technique. However, with the alarmingly expanding airlines' operations, CPO is marred by the curse of dimensionality, rendering the exact CG-implementations obsolete, and necessitating the heuristic-based CG-implementations. Yet, in literature, the much prevalent large-scale complex flight networks involving multiple { crew bases and/or hub-and-spoke sub-networks, largely remain uninvestigated. This paper proposes a novel CG heuristic, which has enabled the in-house development of an Airline Crew Pairing Optimizer (AirCROP). The efficacy of the heuristic/AirCROP has been tested on real-world, large-scale, complex network instances with over 4,200 flights, 15 crew bases, and multiple hub-and-spoke sub-networks (resulting in billion-plus possible pairings). Notably, this paper has a dedicated focus on the proposed CG heuristic (not the entire AirCROP framework) based on balancing random exploration of pairings; exploitation of domain knowledge (on optimal solution features); and utilization of the past computational & search effort through archiving. Though this paper has an airline context, the proposed CG heuristic may find wider applications across different domains, by serving as a template on how to utilize domain knowledge to better tackle combinatorial optimization problems. △ Less

Submitted 2 July, 2021; v1 submitted 18 May, 2020; originally announced May 2020.

Comments: 26 pages, 8 figures, 6 tables, 5 Algorithms

Generative Adversarial Networks (GANs Survey): Challenges, Solutions, and Future Directions

Authors: Divya Saxena, Jiannong Cao

Abstract: Generative Adversarial Networks (GANs) is a novel class of deep generative models which has recently gained significant attention. GANs learns complex and high-dimensional distributions implicitly over images, audio, and data. However, there exists major challenges in training of GANs, i.e., mode collapse, non-convergence and instability, due to inappropriate design of network architecture, use of… ▽ More Generative Adversarial Networks (GANs) is a novel class of deep generative models which has recently gained significant attention. GANs learns complex and high-dimensional distributions implicitly over images, audio, and data. However, there exists major challenges in training of GANs, i.e., mode collapse, non-convergence and instability, due to inappropriate design of network architecture, use of objective function and selection of optimization algorithm. Recently, to address these challenges, several solutions for better design and optimization of GANs have been investigated based on techniques of re-engineered network architectures, new objective functions and alternative optimization algorithms. To the best of our knowledge, there is no existing survey that has particularly focused on broad and systematic developments of these solutions. In this study, we perform a comprehensive survey of the advancements in GANs design and optimization solutions proposed to handle GANs challenges. We first identify key research issues within each design and optimization technique and then propose a new taxonomy to structure solutions by key research issues. In accordance with the taxonomy, we provide a detailed discussion on different GANs variants proposed within each solution and their relationships. Finally, based on the insights gained, we present the promising research directions in this rapidly growing field. △ Less

Submitted 5 April, 2023; v1 submitted 30 April, 2020; originally announced May 2020.

Comments: 61 pages

Journal ref: ACM CSUR, 2021

On Learning Combinatorial Patterns to Assist Large-Scale Airline Crew Pairing Optimization

Authors: Divyam Aggarwal, Yash Kumar Singh, Dhish Kumar Saxena

Abstract: Airline Crew Pairing Optimization (CPO) aims at generating a set of legal flight sequences (crew pairings), to cover an airline's flight schedule, at minimum cost. It is usually performed using Column Generation (CG), a mathematical programming technique for guided search-space exploration. CG exploits the interdependencies between the current and the preceding CG-iteration for generating new vari… ▽ More Airline Crew Pairing Optimization (CPO) aims at generating a set of legal flight sequences (crew pairings), to cover an airline's flight schedule, at minimum cost. It is usually performed using Column Generation (CG), a mathematical programming technique for guided search-space exploration. CG exploits the interdependencies between the current and the preceding CG-iteration for generating new variables (pairings) during the optimization-search. However, with the unprecedented scale and complexity of the emergent flight networks, it has become imperative to learn higher-order interdependencies among the flight-connection graphs, and utilize those to enhance the efficacy of the CPO. In first of its kind and what marks a significant departure from the state-of-the-art, this paper proposes a novel adaptation of the Variational Graph Auto-Encoder for learning plausible combinatorial patterns among the flight-connection data obtained through the search-space exploration by an Airline Crew Pairing Optimizer, AirCROP (developed by the authors and validated by the research consortium's industrial sponsor, GE Aviation). The resulting flight-connection predictions are combined on-the-fly using a novel heuristic to generate new pairings for the optimizer. The utility of the proposed approach is demonstrated on large-scale (over 4200 flights), real-world, complex flight-networks of US-based airlines, characterized by multiple hub-and-spoke subnetworks and several crew bases. △ Less

Submitted 2 May, 2020; v1 submitted 28 April, 2020; originally announced April 2020.

Comments: 8 pages, 6 figures

Methods for Generating Typologies of Non/use

Authors: Devansh Saxena, Patrick Skeba, Shion Guha, Eric P. S. Baumer

Abstract: Prior studies of technology non-use demonstrate the need for approaches that go beyond a simple binary distinction between users and non-users. This paper proposes a set of two different methods by which researchers can identify types of non/use$^{1}$ relevant to the particular sociotechnical settings they are studying. These methods are demonstrated by applying them to survey data about Facebook… ▽ More Prior studies of technology non-use demonstrate the need for approaches that go beyond a simple binary distinction between users and non-users. This paper proposes a set of two different methods by which researchers can identify types of non/use$^{1}$ relevant to the particular sociotechnical settings they are studying. These methods are demonstrated by applying them to survey data about Facebook non/use. The results demonstrate that the different methods proposed here identify fairly comparable types of non/use. They also illustrate how the two methods make different trade offs between the granularity of the resulting typology and the total sample size. The paper also demonstrates how the different typologies resulting from these methods can be used in predictive modeling, allowing for the two methods to corroborate or disconfirm results from one another. The discussion considers implications and applications of these methods, both for research on technology non/use and for studying social computing more broadly. △ Less

Submitted 9 April, 2020; originally announced April 2020.

On Initializing Airline Crew Pairing Optimization for Large-scale Complex Flight Networks

Authors: Divyam Aggarwal, Dhish Kumar Saxena, Thomas Bäck, Michael Emmerich

Abstract: Crew pairing optimization (CPO) is critically important for any airline, since its crew operating costs are second-largest, next to the fuel-cost. CPO aims at generating a set of flight sequences (crew pairings) covering a flight-schedule, at minimum-cost, while satisfying several legality constraints. For large-scale complex flight networks, billion-plus legal pairings (variables) are possible, r… ▽ More Crew pairing optimization (CPO) is critically important for any airline, since its crew operating costs are second-largest, next to the fuel-cost. CPO aims at generating a set of flight sequences (crew pairings) covering a flight-schedule, at minimum-cost, while satisfying several legality constraints. For large-scale complex flight networks, billion-plus legal pairings (variables) are possible, rendering their offline enumeration intractable and an exhaustive search for their minimum-cost full flight-coverage subset impractical. Even generating an initial feasible solution (IFS: a manageable set of legal pairings covering all flights), which could be subsequently optimized is a difficult (NP-complete) problem. Though, as part of a larger project the authors have developed a crew pairing optimizer (AirCROP), this paper dedicatedly focuses on IFS-generation through a novel heuristic based on divide-and-cover strategy and Integer Programming. For real-world large and complex flight network datasets (including over 3200 flights and 15 crew bases) provided by GE Aviation, the proposed heuristic shows upto a ten-fold speed improvement over another state-of-the-art approach. Unprecedentedly, this paper presents an empirical investigation of the impact of IFS-cost on the final (optimized) solution-cost, revealing that too low an IFS-cost does not necessarily imply faster convergence for AirCROP or even lower cost for the optimized solution. △ Less

Submitted 15 March, 2020; originally announced March 2020.

Comments: 17 pages, 9 figures, manuscript submitted for review in a refereed journal

Airline Crew Pairing Optimization Framework for Large Networks with Multiple Crew Bases and Hub-and-Spoke Subnetworks

Authors: Divyam Aggarwal, Dhish Kumar Saxena, Thomas Bäck, Michael Emmerich

Abstract: Crew Pairing Optimization aims at generating a set of flight sequences (crew pairings), covering all flights in an airline's flight schedule, at minimum cost, while satisfying several legality constraints. CPO is critically important for airlines' business viability, considering that the crew operating cost is their second-largest expense. It poses an NP-hard combinatorial optimization problem, to… ▽ More Crew Pairing Optimization aims at generating a set of flight sequences (crew pairings), covering all flights in an airline's flight schedule, at minimum cost, while satisfying several legality constraints. CPO is critically important for airlines' business viability, considering that the crew operating cost is their second-largest expense. It poses an NP-hard combinatorial optimization problem, to tackle which, the state-of-the-art relies on relaxing the underlying Integer Programming Problem (IPP) into a Linear Programming Problem (LPP), solving the latter through Column Generation (CG) technique, and integerization of the resulting LPP solution. However, with the growing scale and complexity of the flight networks (those with a large number of flights, multiple crew bases and/or multiple hub-and-spoke subnetworks), the utility of the conventional CG-practices has become questionable. This paper proposed an Airline Crew Pairing Optimization Framework, AirCROP, whose constitutive modules include the Legal Crew Pairing Generator, Initial Feasible Solution Generator, and an Optimization Engine built on heuristic-based CG-implementation. In this paper, besides the design of AirCROP's modules, insights into important questions related to how these modules interact, which the literature is otherwise silent on, have been shared. These relate to the sensitivity of AirCROP's performance towards: sources of variability over multiple runs for a given problem, initialization method, and termination parameters for LPP-solutioning and IPP-solutioning. The efficacy of the AirCROP has been demonstrated on real-world large-scale and complex flight networks (with over 4200 flights, 15 crew bases, and billion-plus pairings). It is hoped that with the emergence of such complex flight networks, this paper shall serve as an important milestone for affiliated research and applications. △ Less

Submitted 18 November, 2020; v1 submitted 9 March, 2020; originally announced March 2020.

Comments: 28 pages, 3 figures, 9 tables, manuscript submitted for review in a refereed journal. A patent application, based on this research, has been filed in the Netherlands Patent Office. Moreover, D. Aggarwal (author) received the IEEE-ITSS Young Professionals Travelling Fellowship Award for presenting this research work at IEEE ITSC 2019, held in Auckland, New Zealand in October 2019

Real-World Airline Crew Pairing Optimization: Customized Genetic Algorithm versus Column Generation Method

Authors: Divyam Aggarwal, Dhish Kumar Saxena, Thomas Back, Michael Emmerich

Abstract: Airline crew pairing optimization problem (CPOP) aims to find a set of flight sequences (crew pairings) that cover all flights in an airline's highly constrained flight schedule at minimum cost. Since crew cost is second only to the fuel cost, CPOP solutioning is critically important for an airline. However, CPOP is NP-hard, and tackling it is quite challenging. The literature suggests, that when… ▽ More Airline crew pairing optimization problem (CPOP) aims to find a set of flight sequences (crew pairings) that cover all flights in an airline's highly constrained flight schedule at minimum cost. Since crew cost is second only to the fuel cost, CPOP solutioning is critically important for an airline. However, CPOP is NP-hard, and tackling it is quite challenging. The literature suggests, that when the CPOP's scale and complexity is reasonably limited, and an enumeration of all crew pairings is possible, then Metaheuristics are used, predominantly Genetic Algorithms (GAs). Else, Column Generation (CG) based Mixed Integer Programming techniques are used. Notably, as per the literature, a maximum of 45,000 crew pairings have been tackled by GAs. In a significant departure, this paper considers over 800 flights of a US-based large airline (with a monthly network of over 33,000 flights), and tests the efficacy of GAs by enumerating all 400,000+ crew pairings, apriori. Towards it, this paper proposes a domain-knowledge-driven customized-GA. The utility of incorporating domain-knowledge in GA operations, particularly initialization and crossover, is highlighted through suitable experiments. Finally, the proposed GA's performance is compared with a CG-based approach (developed in-house by the authors). Though the latter is found to perform better in terms of solution's cost-quality and run time, it is hoped that this paper will help in better understanding the strengths and limitations of domain-knowledge-driven customizations in GAs, for solving combinatorial optimization problems, including CPOPs. △ Less

Submitted 27 May, 2023; v1 submitted 8 March, 2020; originally announced March 2020.

Comments: 14 pages, 3 figures, 5 tables

Journal ref: In: Evolutionary Multi-Criterion Optimization. EMO 2023. Lecture Notes in Computer Science, vol 13970. Springer, Cham

A Human-Centered Review of the Algorithms used within the U.S. Child Welfare System

Authors: Devansh Saxena, Karla Badillo-Urquiola, Pamela J. Wisniewski, Shion Guha

Abstract: The U.S. Child Welfare System (CWS) is charged with improving outcomes for foster youth; yet, they are overburdened and underfunded. To overcome this limitation, several states have turned towards algorithmic decision-making systems to reduce costs and determine better processes for improving CWS outcomes. Using a human-centered algorithmic design approach, we synthesize 50 peer-reviewed publicati… ▽ More The U.S. Child Welfare System (CWS) is charged with improving outcomes for foster youth; yet, they are overburdened and underfunded. To overcome this limitation, several states have turned towards algorithmic decision-making systems to reduce costs and determine better processes for improving CWS outcomes. Using a human-centered algorithmic design approach, we synthesize 50 peer-reviewed publications on computational systems used in CWS to assess how they were being developed, common characteristics of predictors used, as well as the target outcomes. We found that most of the literature has focused on risk assessment models but does not consider theoretical approaches (e.g., child-foster parent matching) nor the perspectives of caseworkers (e.g., case notes). Therefore, future algorithms should strive to be context-aware and theoretically robust by incorporating salient factors identified by past research. We provide the HCI community with research avenues for developing human-centered algorithms that redirect attention towards more equitable outcomes for CWS. △ Less

Submitted 7 March, 2020; originally announced March 2020.