-
LLMs as Evaluators: A Novel Approach to Evaluate Bug Report Summarization
Authors:
Abhishek Kumar,
Sonia Haiduc,
Partha Pratim Das,
Partha Pratim Chakrabarti
Abstract:
Summarizing software artifacts is an important task that has been thoroughly researched. For evaluating software summarization approaches, human judgment is still the most trusted evaluation. However, it is time-consuming and fatiguing for evaluators, making it challenging to scale and reproduce. Large Language Models (LLMs) have demonstrated remarkable capabilities in various software engineering…
▽ More
Summarizing software artifacts is an important task that has been thoroughly researched. For evaluating software summarization approaches, human judgment is still the most trusted evaluation. However, it is time-consuming and fatiguing for evaluators, making it challenging to scale and reproduce. Large Language Models (LLMs) have demonstrated remarkable capabilities in various software engineering tasks, motivating us to explore their potential as automatic evaluators for approaches that aim to summarize software artifacts. In this study, we investigate whether LLMs can evaluate bug report summarization effectively. We conducted an experiment in which we presented the same set of bug summarization problems to humans and three LLMs (GPT-4o, LLaMA-3, and Gemini) for evaluation on two tasks: selecting the correct bug report title and bug report summary from a set of options. Our results show that LLMs performed generally well in evaluating bug report summaries, with GPT-4o outperforming the other LLMs. Additionally, both humans and LLMs showed consistent decision-making, but humans experienced fatigue, impacting their accuracy over time. Our results indicate that LLMs demonstrate potential for being considered as automated evaluators for bug report summarization, which could allow scaling up evaluations while reducing human evaluators effort and fatigue.
△ Less
Submitted 1 September, 2024;
originally announced September 2024.
-
Single-image coherent reconstruction of objects and humans
Authors:
Sarthak Batra,
Partha P. Chakrabarti,
Simon Hadfield,
Armin Mustafa
Abstract:
Existing methods for reconstructing objects and humans from a monocular image suffer from severe mesh collisions and performance limitations for interacting occluding objects. This paper introduces a method to obtain a globally consistent 3D reconstruction of interacting objects and people from a single image. Our contributions include: 1) an optimization framework, featuring a collision loss, tai…
▽ More
Existing methods for reconstructing objects and humans from a monocular image suffer from severe mesh collisions and performance limitations for interacting occluding objects. This paper introduces a method to obtain a globally consistent 3D reconstruction of interacting objects and people from a single image. Our contributions include: 1) an optimization framework, featuring a collision loss, tailored to handle human-object and human-human interactions, ensuring spatially coherent scene reconstruction; and 2) a novel technique to robustly estimate 6 degrees of freedom (DOF) poses, specifically for heavily occluded objects, exploiting image inpainting. Notably, our proposed method operates effectively on images from real-world scenarios, without necessitating scene or object-level 3D supervision. Extensive qualitative and quantitative evaluation against existing methods demonstrates a significant reduction in collisions in the final reconstructions of scenes with multiple interacting humans and objects and a more coherent scene reconstruction.
△ Less
Submitted 15 August, 2024;
originally announced August 2024.
-
Analyzing Sentiment Polarity Reduction in News Presentation through Contextual Perturbation and Large Language Models
Authors:
Alapan Kuila,
Somnath Jena,
Sudeshna Sarkar,
Partha Pratim Chakrabarti
Abstract:
In today's media landscape, where news outlets play a pivotal role in shaping public opinion, it is imperative to address the issue of sentiment manipulation within news text. News writers often inject their own biases and emotional language, which can distort the objectivity of reporting. This paper introduces a novel approach to tackle this problem by reducing the polarity of latent sentiments i…
▽ More
In today's media landscape, where news outlets play a pivotal role in shaping public opinion, it is imperative to address the issue of sentiment manipulation within news text. News writers often inject their own biases and emotional language, which can distort the objectivity of reporting. This paper introduces a novel approach to tackle this problem by reducing the polarity of latent sentiments in news content. Drawing inspiration from adversarial attack-based sentence perturbation techniques and a prompt based method using ChatGPT, we employ transformation constraints to modify sentences while preserving their core semantics. Using three perturbation methods: replacement, insertion, and deletion coupled with a context-aware masked language model, we aim to maximize the desired sentiment score for targeted news aspects through a beam search algorithm. Our experiments and human evaluations demonstrate the effectiveness of these two models in achieving reduced sentiment polarity with minimal modifications while maintaining textual similarity, fluency, and grammatical correctness. Comparative analysis confirms the competitive performance of the adversarial attack based perturbation methods and prompt-based methods, offering a promising solution to foster more objective news reporting and combat emotional language bias in the media.
△ Less
Submitted 3 February, 2024;
originally announced February 2024.
-
DietCNN: Multiplication-free Inference for Quantized CNNs
Authors:
Swarnava Dey,
Pallab Dasgupta,
Partha P Chakrabarti
Abstract:
The rising demand for networked embedded systems with machine intelligence has been a catalyst for sustained attempts by the research community to implement Convolutional Neural Networks (CNN) based inferencing on embedded resource-limited devices. Redesigning a CNN by removing costly multiplication operations has already shown promising results in terms of reducing inference energy usage. This pa…
▽ More
The rising demand for networked embedded systems with machine intelligence has been a catalyst for sustained attempts by the research community to implement Convolutional Neural Networks (CNN) based inferencing on embedded resource-limited devices. Redesigning a CNN by removing costly multiplication operations has already shown promising results in terms of reducing inference energy usage. This paper proposes a new method for replacing multiplications in a CNN by table look-ups. Unlike existing methods that completely modify the CNN operations, the proposed methodology preserves the semantics of the major CNN operations. Conforming to the existing mechanism of the CNN layer operations ensures that the reliability of a standard CNN is preserved. It is shown that the proposed multiplication-free CNN, based on a single activation codebook, can achieve 4.7x, 5.6x, and 3.5x reduction in energy per inference in an FPGA implementation of MNIST-LeNet-5, CIFAR10-VGG-11, and Tiny ImageNet-ResNet-18 respectively. Our results show that the DietCNN approach significantly improves the resource consumption and latency of deep inference for smaller models, often used in embedded systems. Our code is available at: https://github.com/swadeykgp/DietCNN
△ Less
Submitted 17 August, 2023; v1 submitted 9 May, 2023;
originally announced May 2023.
-
Towards Adversarial Purification using Denoising AutoEncoders
Authors:
Dvij Kalaria,
Aritra Hazra,
Partha Pratim Chakrabarti
Abstract:
With the rapid advancement and increased use of deep learning models in image identification, security becomes a major concern to their deployment in safety-critical systems. Since the accuracy and robustness of deep learning models are primarily attributed from the purity of the training samples, therefore the deep learning architectures are often susceptible to adversarial attacks. Adversarial a…
▽ More
With the rapid advancement and increased use of deep learning models in image identification, security becomes a major concern to their deployment in safety-critical systems. Since the accuracy and robustness of deep learning models are primarily attributed from the purity of the training samples, therefore the deep learning architectures are often susceptible to adversarial attacks. Adversarial attacks are often obtained by making subtle perturbations to normal images, which are mostly imperceptible to humans, but can seriously confuse the state-of-the-art machine learning models. We propose a framework, named APuDAE, leveraging Denoising AutoEncoders (DAEs) to purify these samples by using them in an adaptive way and thus improve the classification accuracy of the target classifier networks that have been attacked. We also show how using DAEs adaptively instead of using them directly, improves classification accuracy further and is more robust to the possibility of designing adaptive attacks to fool them. We demonstrate our results over MNIST, CIFAR-10, ImageNet dataset and show how our framework (APuDAE) provides comparable and in most cases better performance to the baseline methods in purifying adversaries. We also design adaptive attack specifically designed to attack our purifying model and demonstrate how our defense is robust to that.
△ Less
Submitted 29 August, 2022;
originally announced August 2022.
-
Resisting Adversarial Attacks in Deep Neural Networks using Diverse Decision Boundaries
Authors:
Manaar Alam,
Shubhajit Datta,
Debdeep Mukhopadhyay,
Arijit Mondal,
Partha Pratim Chakrabarti
Abstract:
The security of deep learning (DL) systems is an extremely important field of study as they are being deployed in several applications due to their ever-improving performance to solve challenging tasks. Despite overwhelming promises, the deep learning systems are vulnerable to crafted adversarial examples, which may be imperceptible to the human eye, but can lead the model to misclassify. Protecti…
▽ More
The security of deep learning (DL) systems is an extremely important field of study as they are being deployed in several applications due to their ever-improving performance to solve challenging tasks. Despite overwhelming promises, the deep learning systems are vulnerable to crafted adversarial examples, which may be imperceptible to the human eye, but can lead the model to misclassify. Protections against adversarial perturbations on ensemble-based techniques have either been shown to be vulnerable to stronger adversaries or shown to lack an end-to-end evaluation. In this paper, we attempt to develop a new ensemble-based solution that constructs defender models with diverse decision boundaries with respect to the original model. The ensemble of classifiers constructed by (1) transformation of the input by a method called Split-and-Shuffle, and (2) restricting the significant features by a method called Contrast-Significant-Features are shown to result in diverse gradients with respect to adversarial attacks, which reduces the chance of transferring adversarial examples from the original to the defender model targeting the same class. We present extensive experimentations using standard image classification datasets, namely MNIST, CIFAR-10 and CIFAR-100 against state-of-the-art adversarial attacks to demonstrate the robustness of the proposed ensemble-based defense. We also evaluate the robustness in the presence of a stronger adversary targeting all the models within the ensemble simultaneously. Results for the overall false positives and false negatives have been furnished to estimate the overall performance of the proposed methodology.
△ Less
Submitted 18 August, 2022;
originally announced August 2022.
-
Deep Learning-based Spatially Explicit Emulation of an Agent-Based Simulator for Pandemic in a City
Authors:
Varun Madhavan,
Adway Mitra,
Partha Pratim Chakrabarti
Abstract:
Agent-Based Models are very useful for simulation of physical or social processes, such as the spreading of a pandemic in a city. Such models proceed by specifying the behavior of individuals (agents) and their interactions, and parameterizing the process of infection based on such interactions based on the geography and demography of the city. However, such models are computationally very expensi…
▽ More
Agent-Based Models are very useful for simulation of physical or social processes, such as the spreading of a pandemic in a city. Such models proceed by specifying the behavior of individuals (agents) and their interactions, and parameterizing the process of infection based on such interactions based on the geography and demography of the city. However, such models are computationally very expensive, and the complexity is often linear in the total number of agents. This seriously limits the usage of such models for simulations, which often have to be run hundreds of times for policy planning and even model parameter estimation. An alternative is to develop an emulator, a surrogate model that can predict the Agent-Based Simulator's output based on its initial conditions and parameters. In this paper, we discuss a Deep Learning model based on Dilated Convolutional Neural Network that can emulate such an agent based model with high accuracy. We show that use of this model instead of the original Agent-Based Model provides us major gains in the speed of simulations, allowing much quicker calibration to observations, and more extensive scenario analysis. The models we consider are spatially explicit, as the locations of the infected individuals are simulated instead of the gross counts. Another aspect of our emulation framework is its divide-and-conquer approach that divides the city into several small overlapping blocks and carries out the emulation in them parallelly, after which these results are merged together. This ensures that the same emulator can work for a city of any size, and also provides significant improvement of time complexity of the emulator, compared to the original simulator.
△ Less
Submitted 29 January, 2023; v1 submitted 28 May, 2022;
originally announced May 2022.
-
Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks
Authors:
Kushal Kedia,
Rajat Kumar Jenamani,
Aritra Hazra,
Partha Pratim Chakrabarti
Abstract:
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents from their start locations to end locations. We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF), wherein agents are assigned a sequence of planning tasks that contain precedence constraints between them. PC-MAPF has various applications, for example in…
▽ More
Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents from their start locations to end locations. We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF), wherein agents are assigned a sequence of planning tasks that contain precedence constraints between them. PC-MAPF has various applications, for example in multi-agent pickup and delivery problems where some objects might require multiple agents to collaboratively pickup and move them in unison. Precedence constraints also arise in warehouse assembly problems where before a manufacturing task can begin, its input resources must be manufactured and delivered. We propose a novel algorithm, Precedence Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal solutions for this class of problems. PC-CBS utilizes a Precedence-Constrained Task-Graph to define valid intervals for each planning task and updates them when precedence conflicts are encountered. We benchmark the performance of this algorithm over various warehouse assembly, and multi-agent pickup and delivery tasks, and use it to evaluate the sub-optimality of a recently proposed efficient baseline.
△ Less
Submitted 8 February, 2022;
originally announced February 2022.
-
PARL: Enhancing Diversity of Ensemble Networks to Resist Adversarial Attacks via Pairwise Adversarially Robust Loss Function
Authors:
Manaar Alam,
Shubhajit Datta,
Debdeep Mukhopadhyay,
Arijit Mondal,
Partha Pratim Chakrabarti
Abstract:
The security of Deep Learning classifiers is a critical field of study because of the existence of adversarial attacks. Such attacks usually rely on the principle of transferability, where an adversarial example crafted on a surrogate classifier tends to mislead the target classifier trained on the same dataset even if both classifiers have quite different architecture. Ensemble methods against ad…
▽ More
The security of Deep Learning classifiers is a critical field of study because of the existence of adversarial attacks. Such attacks usually rely on the principle of transferability, where an adversarial example crafted on a surrogate classifier tends to mislead the target classifier trained on the same dataset even if both classifiers have quite different architecture. Ensemble methods against adversarial attacks demonstrate that an adversarial example is less likely to mislead multiple classifiers in an ensemble having diverse decision boundaries. However, recent ensemble methods have either been shown to be vulnerable to stronger adversaries or shown to lack an end-to-end evaluation. This paper attempts to develop a new ensemble methodology that constructs multiple diverse classifiers using a Pairwise Adversarially Robust Loss (PARL) function during the training procedure. PARL utilizes gradients of each layer with respect to input in every classifier within the ensemble simultaneously. The proposed training procedure enables PARL to achieve higher robustness against black-box transfer attacks compared to previous ensemble methods without adversely affecting the accuracy of clean examples. We also evaluate the robustness in the presence of white-box attacks, where adversarial examples are crafted using parameters of the target classifier. We present extensive experiments using standard image classification datasets like CIFAR-10 and CIFAR-100 trained using standard ResNet20 classifier against state-of-the-art adversarial attacks to demonstrate the robustness of the proposed ensemble methodology.
△ Less
Submitted 9 December, 2021;
originally announced December 2021.
-
Detecting Adversaries, yet Faltering to Noise? Leveraging Conditional Variational AutoEncoders for Adversary Detection in the Presence of Noisy Images
Authors:
Dvij Kalaria,
Aritra Hazra,
Partha Pratim Chakrabarti
Abstract:
With the rapid advancement and increased use of deep learning models in image identification, security becomes a major concern to their deployment in safety-critical systems. Since the accuracy and robustness of deep learning models are primarily attributed from the purity of the training samples, therefore the deep learning architectures are often susceptible to adversarial attacks. Adversarial a…
▽ More
With the rapid advancement and increased use of deep learning models in image identification, security becomes a major concern to their deployment in safety-critical systems. Since the accuracy and robustness of deep learning models are primarily attributed from the purity of the training samples, therefore the deep learning architectures are often susceptible to adversarial attacks. Adversarial attacks are often obtained by making subtle perturbations to normal images, which are mostly imperceptible to humans, but can seriously confuse the state-of-the-art machine learning models. What is so special in the slightest intelligent perturbations or noise additions over normal images that it leads to catastrophic classifications by the deep neural networks? Using statistical hypothesis testing, we find that Conditional Variational AutoEncoders (CVAE) are surprisingly good at detecting imperceptible image perturbations. In this paper, we show how CVAEs can be effectively used to detect adversarial attacks on image classification networks. We demonstrate our results over MNIST, CIFAR-10 dataset and show how our method gives comparable performance to the state-of-the-art methods in detecting adversaries while not getting confused with noisy images, where most of the existing methods falter.
△ Less
Submitted 9 December, 2021; v1 submitted 28 November, 2021;
originally announced November 2021.
-
Artificial Intelligence Methods Based Hierarchical Classification of Frontotemporal Dementia to Improve Diagnostic Predictability
Authors:
Km Poonam,
Rajlakshmi Guha,
Partha P Chakrabarti
Abstract:
Patients with Frontotemporal Dementia (FTD) have impaired cognitive abilities, executive and behavioral traits, loss of language ability, and decreased memory capabilities. Based on the distinct patterns of cortical atrophy and symptoms, the FTD spectrum primarily includes three variants: behavioral variant FTD (bvFTD), non-fluent variant primary progressive aphasia (nfvPPA), and semantic variant…
▽ More
Patients with Frontotemporal Dementia (FTD) have impaired cognitive abilities, executive and behavioral traits, loss of language ability, and decreased memory capabilities. Based on the distinct patterns of cortical atrophy and symptoms, the FTD spectrum primarily includes three variants: behavioral variant FTD (bvFTD), non-fluent variant primary progressive aphasia (nfvPPA), and semantic variant primary progressive aphasia (svPPA). The purpose of this study is to classify MRI images of every single subject into one of the spectrums of the FTD in a hierarchical order by applying data-driven techniques of Artificial Intelligence (AI) on cortical thickness data. This data is computed by FreeSurfer software. We used the Smallest Univalue Segment Assimilating Nucleus (SUSAN) technique to minimize the noise in cortical thickness data. Specifically, we took 204 subjects from the frontotemporal lobar degeneration neuroimaging initiative (NIFTD) database to validate this approach, and each subject was diagnosed in one of the diagnostic categories (bvFTD, svPPA, nfvPPA and cognitively normal). Our proposed automated classification model yielded classification accuracy of 86.5, 76, and 72.7 with support vector machine (SVM), linear discriminant analysis (LDA), and Naive Bayes methods, respectively, in 10-fold cross-validation analysis, which is a significant improvement on a traditional single multi-class model with an accuracy of 82.7, 73.4, and 69.2.
△ Less
Submitted 12 April, 2021;
originally announced April 2021.
-
City-scale Simulation of Covid-19 Pandemic and Intervention Policies using Agent-based Modelling
Authors:
Gaurav Suryawanshi,
Varun Madhavan,
Adway Mitra,
Partha Pratim Chakrabarti
Abstract:
During the Covid-19 pandemic, most governments across the world imposed policies like lock-down of public spaces and restrictions on people's movements to minimize the spread of the virus through physical contact. However, such policies have grave social and economic costs, and so it is important to pre-assess their impacts. In this work we aim to visualize the dynamics of the pandemic in a city u…
▽ More
During the Covid-19 pandemic, most governments across the world imposed policies like lock-down of public spaces and restrictions on people's movements to minimize the spread of the virus through physical contact. However, such policies have grave social and economic costs, and so it is important to pre-assess their impacts. In this work we aim to visualize the dynamics of the pandemic in a city under different intervention policies, by simulating the behavior of the residents. We develop a very detailed agent-based model for a city, including its residents, physical and social spaces like homes, marketplaces, workplaces, schools/colleges etc. We parameterize our model for Kolkata city in India using ward-level demographic and civic data. We demonstrate that under appropriate choice of parameters, our model is able to reproduce the observed dynamics of the Covid-19 pandemic in Kolkata, and also indicate the counter-factual outcomes of alternative intervention policies.
△ Less
Submitted 9 September, 2021; v1 submitted 4 April, 2021;
originally announced April 2021.
-
Early-Stage Resource Estimation from Functional Reliability Specification in Embedded Cyber-Physical Systems
Authors:
Ginju V. George,
Aritra Hazra,
Pallab Dasgupta,
Partha Pratim Chakrabarti
Abstract:
Reliability and fault tolerance are critical attributes of embedded cyber-physical systems that require a high safety-integrity level. For such systems, the use of formal functional safety specifications has been strongly advocated in most industrial safety standards, but reliability and fault tolerance have traditionally been treated as platform issues. We believe that addressing reliability and…
▽ More
Reliability and fault tolerance are critical attributes of embedded cyber-physical systems that require a high safety-integrity level. For such systems, the use of formal functional safety specifications has been strongly advocated in most industrial safety standards, but reliability and fault tolerance have traditionally been treated as platform issues. We believe that addressing reliability and fault tolerance at the functional safety level widens the scope for resource optimization, targeting those functionalities that are safety-critical, rather than the entire platform. Moreover, for software based control functionalities, temporal redundancies have become just as important as replication of physical resources, and such redundancies can be modeled at the functional specification level. The ability to formally model functional reliability at a specification level enables early estimation of physical resources and computation bandwidth requirements. In this paper we propose, for the first time, a resource estimation methodology from a formal functional safety specification augmented by reliability annotations. The proposed reliability specification is overlaid on the safety-critical functional specification and our methodology extracts a constraint satisfaction problem for determining the optimal set of resources for meeting the reliability target for the safety-critical behaviors. We use SMT (Satisfiability Modulo Theories) / ILP (Integer Linear Programming) solvers at the back end to solve the optimization problem, and demonstrate the feasibility of our methodology on a Satellite Launch Vehicle Navigation, Guidance and Control (NGC) System.
△ Less
Submitted 3 May, 2020;
originally announced May 2020.
-
Joint Seat Allocation 2018: An algorithmic perspective
Authors:
Surender Baswana,
Partha Pratim Chakrabarti,
Yashodhan Kanoria,
Utkarsh Patange,
Sharat Chandran
Abstract:
Until 2014, admissions to the Indian Institutes of Technology (IITs) were conducted under one umbrella, whereas the admissions to the non-IIT Centrally Funded Government Institutes (CFTIs) were conducted under a different umbrella, the Central Seat Allocation Board.
In 2015, a new Multi-Round Multi-Run Deferred Acceptance joint seat allocation process was implemented, improving the efficiency an…
▽ More
Until 2014, admissions to the Indian Institutes of Technology (IITs) were conducted under one umbrella, whereas the admissions to the non-IIT Centrally Funded Government Institutes (CFTIs) were conducted under a different umbrella, the Central Seat Allocation Board.
In 2015, a new Multi-Round Multi-Run Deferred Acceptance joint seat allocation process was implemented, improving the efficiency and productivity of concerned stakeholders. The process brings all CFTIs under one umbrella for admissions: 100 institutes and approximately 39000 seats in 2018. In this scheme, each candidate submits a single choice list over all available programs, and receives no more than a single seat from the system, based on the choices and the ranks in the relevant merit lists. Significantly, overbooking of seats is forbidden.
In this report, we provide details of our safe, fair and optimal algorithm. Novel features include the ability to handle multiple merit lists, seat guarantee across multiple rounds, implementing reservation, and de-reservation rules, handling escalation of ranks due to a revision of marks by state boards during the allocation process, and dealing with last minute de-recognition of other backward caste categories. A notable rule required the allocation of supernumerary seats to females, provided the program did not have a sufficient desired percentage, while, at the same time, not reducing the number of seats available to non-females.
Looking forward, we posit first that it is inevitable that different colleges will prefer different mechanisms of judging merit, and assigning relative rank. We believe the ability of our algorithm to gracefully handle multiple merit lists gives us hope to express optimism that all undergraduate admissions in the country, beyond the CFTIs, can beneficially use the suggested scheme.
△ Less
Submitted 11 November, 2019; v1 submitted 14 April, 2019;
originally announced April 2019.
-
Multi-mode Sampling Period Selection for Embedded Real Time Control
Authors:
Rajorshee Raha,
Soumyajit Dey,
Partha Pratim Chakrabarti,
Pallab Dasgupta
Abstract:
Recent studies have shown that adaptively regulating the sampling rate results in significant reduction in computational resources in embedded software based control. Selecting a uniform sampling rate for a control loop is robust, but overtly pessimistic for sharing processors among multiple control loops. Fine grained regulation of periodicity achieves better resource utilization, but is hard to…
▽ More
Recent studies have shown that adaptively regulating the sampling rate results in significant reduction in computational resources in embedded software based control. Selecting a uniform sampling rate for a control loop is robust, but overtly pessimistic for sharing processors among multiple control loops. Fine grained regulation of periodicity achieves better resource utilization, but is hard to implement online in a robust way. In this paper we propose multi-mode sampling period selection, derived from an offline control theoretic analysis of the system. We report significant gains in computational efficiency without trading off control performance.
△ Less
Submitted 29 June, 2015;
originally announced June 2015.
-
Algorithms for Generating Ordered Solutions for Explicit AND/OR Structures
Authors:
Priyankar Ghosh,
Amit Sharma,
P. P. Chakrabarti,
Pallab Dasgupta
Abstract:
We present algorithms for generating alternative solutions for explicit acyclic AND/OR structures in non-decreasing order of cost. The proposed algorithms use a best first search technique and report the solutions using an implicit representation ordered by cost. In this paper, we present two versions of the search algorithm -- (a) an initial version of the best first search algorithm, ASG, which…
▽ More
We present algorithms for generating alternative solutions for explicit acyclic AND/OR structures in non-decreasing order of cost. The proposed algorithms use a best first search technique and report the solutions using an implicit representation ordered by cost. In this paper, we present two versions of the search algorithm -- (a) an initial version of the best first search algorithm, ASG, which may present one solution more than once while generating the ordered solutions, and (b) another version, LASG, which avoids the construction of the duplicate solutions. The actual solutions can be reconstructed quickly from the implicit compact representation used. We have applied the methods on a few test domains, some of them are synthetic while the others are based on well known problems including the search space of the 5-peg Tower of Hanoi problem, the matrix-chain multiplication problem and the problem of finding secondary structure of RNA. Experimental results show the efficacy of the proposed algorithms over the existing approach. Our proposed algorithms have potential use in various domains ranging from knowledge based frameworks to service composition, where the AND/OR structure is widely used for representing problems.
△ Less
Submitted 22 January, 2014;
originally announced January 2014.
