Abdul Sattar

EAAI Journal 2022 Journal Article

Long range multi-step water quality forecasting using iterative ensembling

• Md Khaled Ben Islam
• M.A. Hakim Newton
• Julia Rahman
• Jarrod Trevathan
• Abdul Sattar

Real-life water quality monitoring applications such as aquaculture domains and water resource management need long range multi-step prediction for disaster control. However, prediction accuracy usually degrades gradually as the prediction target timepoint is further away from the current timepoint. To address this, recent water quality forecasting methods mostly rely on complex deep learning models. In this paper, we propose a simple time-variant iterative ensembling method that strives to significantly improve the performance of a given arbitrary long range multi-step time series predictor for water quality data with minimal increase in computational cost. With the given predictor, our proposed method iteratively uses ensembles of predicted values for preceding steps to improve the prediction accuracy for the succeeding steps. The iterative ensembling operation is performed on the trained model and only at the inference stage, and so does not need any further computing-intensive training for the performance improvement. We experimentally show that the proposed method is effective with 7 predictors and 9 water quality datasets of various types, and it outperforms the state-of-the-art results in those datasets by around 2%–29% in mean absolute error (MAE), root mean squared error (RMSE) and mean absolute percentage error (MAPE) metrics. Similar improvement has also been found in two other metrics such as normalized Nash–Sutcliffe model efficiency coefficient (NNSE) metric and Taylor diagram plot. Overall, the proposed iterative ensembling is a promising approach for multi-step long range water quality prediction for high-frequency water quality monitoring systems.

EAAI Journal 2021 Journal Article

Constraint based local search for flowshops with sequence-dependent setup times

• Vahid Riahi
• M.A. Hakim Newton
• Abdul Sattar

Permutation flowshop scheduling problem with sequence-dependent setup times (PFSP-SDST) and makespan minimisation is NP-hard. It has important practical applications, for example, in the cider industry and the print industry. There exist several metaheuristic algorithms to solve this problem. However, within practical time limits, those algorithms still either find low quality solutions or struggle with large problems. In this paper, we have proposed a simple but effective local search algorithm, called constraint based local search (CBLS) algorithm, which transforms the SDST constraints into an auxiliary objective function and uses the auxiliary objective function to guide the search towards the optimal value of the actual objective function. Our motivation comes from the constraint optimisation models in artificial intelligence (AI), where constraint-based informed decisions are of particular interest instead of random-based decisions. Our experimental results on well-known 480 instances of PFSP-SDST show that the proposed CBLS algorithm outperforms existing state-of-the-art PFSP-SDST algorithms. Moreover, our algorithm obtains new upper bounds for 204 out of 360 medium- and large-sized problem instances.

IJCAI Conference 2017 Conference Paper

A Unifying Framework for Probabilistic Belief Revision

• Zhiqiang Zhuang
• James Delgrande
• Abhaya Nayak
• Abdul Sattar

In this paper we provide a general, unifying framework for probabilistic belief revision. We first introduce a probabilistic logic called p-logic that is capable of representing and reasoning with basic probabilistic information. With p-logic as the background logic, we define a revision function called p-revision that resembles partial meet revision in the AGM framework. We provide a representation theorem for p-revision which shows that it can be characterised by the set of basic AGM revision postulates. P-revision represents an "all purpose" method for revising probabilistic information that can be used for, but not limited to, the revision problems behind Bayesian conditionalisation, Jeffrey conditionalisation, and Lewis's imaging. Importantly, p-revision subsumes all three approaches indicating that Bayesian conditionalisation, Jeffrey conditionalisation, and Lewis' imaging all obey the basic principles of AGM revision. As well our investigation sheds light on the corresponding operation of AGM expansion in the probabilistic setting.

JAIR Journal 2017 Journal Article

Encoding Domain Transitions for Constraint-Based Planning

• Nina Ghanbari Ghooshchi
• Majid Namazi
• M.A.Hakim Newton
• Abdul Sattar

We describe a constraint-based automated planner named Transition Constraints for Parallel Planning (TCPP). TCPP constructs its constraint model from a redefined version of the domain transition graphs (DTG) of a given planning problem. TCPP encodes state transitions in the redefined DTGs by using table constraints with cells containing don't cares or wild cards. TCPP uses Minion the constraint solver to solve the constraint model and returns a parallel plan. We empirically compare TCPP with the other state-of-the-art constraint-based parallel planner PaP2. PaP2 encodes action successions in the finite state automata (FSA) as table constraints with cells containing sets of values. PaP2 uses SICStus Prolog as its constraint solver. We also improve PaP2 by using don’t cares and mutex constraints. Our experiments on a number of standard classical planning benchmark domains demonstrate TCPP's efficiency over the original PaP2 running on SICStus Prolog and our reconstructed and enhanced versions of PaP2 running on Minion.

IJCAI Conference 2015 Conference Paper

Probabilistic Belief Contraction Using Argumentation

• Kinzang Chhogyal
• Abhaya Nayak
• Zhiqiang Zhuang
• Abdul Sattar

When a belief state is represented as a probability function P, the resulting belief state of the contraction of a sentence (belief) from the original belief state P can be given by the probabilistic version of the Harper Identity. Specifically, the result of contracting P by a sentence h is taken to be the mixture of two states: the original state P, and the resultant state P∗ ¬h of revising P by the negation of h. What proportion of P and P∗ ¬h should be used in this mixture remains an open issue and is largely ignored in literature. In this paper, we first classify different belief states by their stability, and then exploit the quantitative nature of probabilities and combine it with the basic ideas of argumentation theory to determine the mixture proportions. We, therefore, propose a novel approach to probabilistic belief contraction using argumentation.

AAAI Conference 2015 Conference Paper

Transition Constraints for Parallel Planning

• Nina Ghooshchi
• Majid Namazi
• M A Hakim Newton
• Abdul Sattar

We present a planner named Transition Constraints for Parallel Planning (TCPP). TCPP constructs a new constraint model from domain transition graphs (DTG) of a given planning problem. TCPP encodes the constraint model by using table constraints that allow don’t cares or wild cards as cell values. TCPP uses Minion the constraint solver to solve the constraint model and returns the parallel plan. Empirical results exhibit the efficiency of our planning system over state-ofthe-art constraint-based planners.

AAAI Conference 2013 Conference Paper

Mixed Heuristic Local Search for Protein Structure Prediction

• Swakkhar Shatabda
• M. A. Newton
• Abdul Sattar

Protein structure prediction is an unsolved problem in computational biology. One great difficulty is due to the unknown factors in the actual energy function. Moreover, the energy models available are often not very informative particularly when spatially similar structures are compared during search. We introduce several novel heuristics to augment the energy model and present a new local search algorithm that exploits these heuristics in a mixed fashion. Although the heuristics individually are weaker in performance than the energy function, their combination interestingly produces stronger results. For standard benchmark proteins on the face centered cubic lattice and a realistic 20 × 20 energy model, we obtain structures with significantly lower energy than those obtained by the state-of-the-art algorithms. We also report results for these proteins using the same energy model on the cubic lattice.

AAAI Conference 2013 Conference Paper

Simplified Lattice Models for Protein Structure Prediction: How Good Are They?

• Swakkhar Shatabda
• M. A. Newton
• Abdul Sattar

IJCAI Conference 2013 Conference Paper

Weight-Enhanced Diversification in Stochastic Local Search for Satisfiability

• Thach-Thao Duong
• Duc Nghia Pham
• Abdul Sattar
• M. A. Hakim Newton

Intensification and diversification are the key factors that control the performance of stochastic local search in satisfiability (SAT). Recently, Novelty Walk has become a popular method for improving diversification of the search and so has been integrated in many well-known SAT solvers such as TNM and gNovelty+. In this paper, we introduce new heuristics to improve the effectiveness of Novelty Walk in terms of reducing search stagnation. In particular, we use weights (based on statistical information collected during the search) to focus the diversification phase onto specific areas of interest. With a given probability, we select the most frequently unsatisfied clause instead of a totally random one as Novelty Walk does. Amongst all the variables appearing in the selected clause, we then select the least flipped variable for the next move. Our experimental results show that the new weightenhanced diversification method significantly improves the performance of gNovelty+ and thus outperforms other local search SAT solvers on a wide range of structured and random satisfiability benchmarks.

AIIM Journal 2012 Journal Article

An implicit approach to deal with periodically repeated medical data

• Bela Stantic
• Paolo Terenziani
• Guido Governatori
• Alessio Bottrighi
• Abdul Sattar

Context Temporal information plays a crucial role in medicine, so that in medical informatics there is an increasing awareness that suitable database approaches are needed to store and support it. Specifically, a great amount of clinical data (e. g. , therapeutic data) are periodically repeated. Although an explicit treatment is possible in most cases, it causes severe storage and disk I/O problems. Objective In this paper, we propose an innovative approach to cope with periodic relational medical data in an implicit way. Methods We propose a new data model, representing periodic data in a compact (implicit) way, which is a consistent extension of TSQL2 consensus approach. Then, we identify some important types of temporal queries, and present query answering algorithms to answer them. Finally, we also run experiments to evaluate our approach. Results The experiments show that our approach outperforms current explicit approaches, especially as regard disk I/O. Conclusion We have provided an implicit approach to periodic data with is a consistent extension of TSQL2 (and which is thus grant interoperable with it), and we have experimentally proven that it outperforms current explicit approaches.

AAMAS Conference 2012 Conference Paper

On modeling punishment in multi-agent systems

• Subhasis Thakur
• Guido Governatori
• Abdul Sattar

In this paper we study isolation as a form of punishment. Although an isolated violator is punished as it can not benefit from the interactions with other agents, compliant agents may also suffer from not engaging with the violators. In this paper we analyze such problems. Certain modifications of multi agent systems are needed to solve this problem. These modifications are aimed to make the violator redundant so that it can be ignored and hence isolated. Deciding on these modifications is NP-complete and approximation algorithms exist.

AAAI Conference 2012 Conference Paper

Trap Avoidance in Local Search Using Pseudo-Conflict Learning

• Duc Pham
• Thach-Thao Duong
• Abdul Sattar

A key challenge in developing efficient local search solvers is to effectively minimise search stagnation (i. e. avoiding traps or local minima). A majority of the state-of-the-art local search solvers perform random and/or Novelty-based walks to overcome search stagnation. Although such strategies are effective in diversifying a search from its current local minimum, they do not actively prevent the search from visiting previously encountered local minima. In this paper, we propose a new preventative strategy to effectively minimise search stagnation using pseudo-conflict learning. We define a pseudo-conflict as a derived path from the search trajectory that leads to a local minimum. We then introduce a new variable selection scheme that penalises variables causing those pseudo-conflicts. Our experimental results show that the new preventative approach significantly improves the performance of local search solvers on a wide range of structured and random benchmarks.

AAAI Conference 2012 Conference Paper

Two New Local Search Strategies for Minimum Vertex Cover

• Shaowei Cai
• Kaile Su
• Abdul Sattar

In this paper, we propose two new strategies to design efficient local search algorithms for the minimum vertex cover (MVC) problem. There are two main drawbacks in state-ofthe-art MVC local search algorithms: First, they select a pair of vertices to be exchanged simultaneously, which is time consuming; Second, although they use edge weighting techniques, they do not have a strategy to decrease the weights. To address these drawbacks, we propose two new strategies: two stage exchange and edge weighting with forgetting. The two stage exchange strategy selects two vertices to be exchanged separately and performs the exchange in two stages. The strategy of edge weighting with forgetting not only increases weights of uncovered edges, but also decreases some weights for each edge periodically. We utilize these two strategies to design a new algorithm dubbed NuMVC. The experimental results show that NuMVC significantly outperforms existing state-of-the-art heuristic algorithms on most of the hard DIMACS instances and all instances in the hard random BHOSLIB benchmark.

AIJ Journal 2011 Journal Article

Local search with edge weighting and configuration checking heuristics for minimum vertex cover

• Shaowei Cai
• Kaile Su
• Abdul Sattar

The Minimum Vertex Cover (MVC) problem is a well-known combinatorial optimization problem of great importance in theory and applications. In recent years, local search has been shown to be an effective and promising approach to solve hard problems, such as MVC. In this paper, we introduce two new local search algorithms for MVC, called EWLS (Edge Weighting Local Search) and EWCC (Edge Weighting Configuration Checking). The first algorithm EWLS is an iterated local search algorithm that works with a partial vertex cover, and utilizes an edge weighting scheme which updates edge weights when getting stuck in local optima. Nevertheless, EWLS has an instance-dependent parameter. Further, we propose a strategy called Configuration Checking for handling the cycling problem in local search. This is used in designing a more efficient algorithm that has no instance-dependent parameters, which is referred to as EWCC. Unlike previous vertex-based heuristics, the configuration checking strategy considers the induced subgraph configurations when selecting a vertex to add into the current candidate solution. A detailed experimental study is carried out using the well-known DIMACS and BHOSLIB benchmarks. The experimental results conclude that EWLS and EWCC are largely competitive on DIMACS benchmarks, where they outperform other current best heuristic algorithms on most hard instances, and dominate on the hard random BHOSLIB benchmarks. Moreover, EWCC makes a significant improvement over EWLS, while both EWLS and EWCC set a new record on a twenty-year challenge instance. Further, EWCC performs quite well even on structured instances in comparison to the best exact algorithm we know. We also study the run-time behavior of EWLS and EWCC which shows interesting properties of both algorithms.

AIJ Journal 2008 Journal Article

Modelling and solving temporal reasoning as propositional satisfiability

• Duc Nghia Pham
• John Thornton
• Abdul Sattar

Representing and reasoning about time dependent information is a key research issue in many areas of computer science and artificial intelligence. One of the best known and widely used formalisms for representing interval-based qualitative temporal information is Allen's interval algebra (IA). The fundamental reasoning task in IA is to find a scenario that is consistent with the given information. This problem is in general NP-complete. In this paper, we investigate how an interval-based representation, or IA network, can be encoded into a propositional formula of Boolean variables and/or predicates in decidable theories. Our task is to discover whether satisfying such a formula can be more efficient than finding a consistent scenario for the original problem. There are two basic approaches to modelling an IA network: one represents the relations between intervals as variables and the other represents the end-points of each interval as variables. By combining these two approaches with three different Boolean satisfiability (SAT) encoding schemes, we produced six encoding schemes for converting IA to SAT. In addition, we also showed how IA networks can be formulated into satisfiability modulo theories (SMT) formulae based on the quantifier-free integer difference logic (QF-IDL). These encodings were empirically studied using randomly generated IA problems of sizes ranging from 20 to 100 nodes. A general conclusion we draw from these experimental results is that encoding IA into SAT produces better results than existing approaches. More specifically, we show that the new point-based 1-D support SAT encoding of IA produces consistently better results than the other alternatives considered. In comparison with the six different SAT encodings, the SMT encoding came fourth after the point-based and interval-based 1-D support schemes and the point-based direct scheme. Further, we observe that the phase transition region maps directly from the IA encoding to each SAT or SMT encoding, but, surprisingly, the location of the hard region varies according to the encoding scheme. Our results also show a fixed performance ranking order over the various encoding schemes.

IJCAI Conference 2007 Conference Paper

• Duc Nghia Pham
• John Thornton
• Abdul Sattar

Local search procedures for solving satisfiability problems have attracted considerable attention since the development of GSAT in 1992. However, recent work indicates that for many real-world problems, complete search methods have the advantage, because modern heuristics are able to effectively exploit problem structure. Indeed, to develop a local search technique that can effectively deal with variable dependencies has been an open challenge since 1997.

AAMAS Conference 2006 Conference Paper

Execution Monitoring in BDI Agents

• Abdul Sattar
• Kewen Wang
• Raihana Ferdous
• Timothy Cleaver

AAMAS Conference 2006 Conference Paper

The Interpreted System Model of Knowledge, Belief, Desire and Intention

• Kaile Su
• Xiangyu Luo
• Abdul Sattar
• Mehmet Orgun

AAMAS Conference 2005 Conference Paper

A Computationally Grounded Logic of Knowledge, Belief and Certainty

• Kaile Su
• Abdul Sattar
• Guido Governatori
• Qingliang Chen

IJCAI Conference 2005 Conference Paper

Computationally Grounded Model of BDI-Agents

• Kaile Su
• Abdul Sattar
• Kewen Wang
• Guido

AAAI Conference 2005 Conference Paper

SAT-Based versus CSP-Based Constraint Weighting for Satisfiability

• Duc Nghia Pham
• Abdul Sattar

Recent research has focused on bridging the gap between the satisfiability (SAT) and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formula (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. Experimental results have shown this approach can achieve significant improvements in performance compared with the traditional SAT and CSP approaches. In this paper, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based approach to handle weights, together with CSP-based approach to variable instantiation, is superior to other combinations of SAT and CSP-based approaches. A further experiment on the round robin scheduling problem indicates that this many-valued constraint weighting approach outperforms other state-of-the-art solvers.

IJCAI Conference 1999 Conference Paper

A New Framework for Reasoning about Points, Intervals and Durations

• Arun K Pujari
• Abdul Sattar

We present a new framework for reasoning about points, intervals and durations--Point Interval Duration Network (PIDN). The PIDN adequately handles both qualitative and quantitaive temporal information. We show that Interval Algebra, Point Algebra, TCSP, PDN and A P D N become special cases of P I D N. The underlying algebraic structure of P I D N is closed under composition and intersection. Determinig consistency of P I D N is NP-llard. However, we identify some tractable subclasses of P I D N. We show that path consistency is not sufficient to ensure global consistency o[ the tractable subclasses of P I D N. We identify a subclass for which enforcing 4-consistency suffices to ensure the global consistency, and prove that this subclass is maximal for qualitative constraints. Our approach is based on the geometric interpretation of the domains of temporal objects. Interestingly, the classical Helly\s Theorem of 1923 is used to prove the complexity for the tractable subclass.