Your search for: 'author:("Alviano, Mario")' has returned 12 results. (0.023s) Save search

Authors: Alviano, Mario

Article Type: Research Article

Abstract: Answer set programming (ASP) is a declarative language for nonmonotonic reasoning based on stable model semantics. A stable model is a classical model of the input program satisfying the following stability condition: only necessary information is included in the model under the assumptions provided by the model itself for the unknown knowledge in the program, where unknown knowledge is encoded by means of default negation. Rational agents acting in the real world often have to reason in presence of unknown knowledge. It is also common that real world agents cannot meet all their desiderata. For this reason, ASP programs may …include weak constraints for representing numerical preferences over jointly incompatible conditions. Stable models are therefore associated with a cost given by the unsatisfied weak constraints, and stable models of minimum cost are preferred. This paper summarizes algorithms and strategies for computing optimal stable models, and hints on how these algorithms can be extended to handle some qualitative preferences that have a natural representation in circumscription, that is, those based on subset-minimality and superset-maximality. Show more

Keywords: Answer set programming, boolean optimization, unsatisfiable core analysis, circumscription

DOI: 10.3233/IA-180119

Citation: Intelligenza Artificiale, vol. 12, no. 1, pp. 1-14, 2018

Authors: Alviano, Mario

Article Type: Research Article

Abstract: Aggregation functions are widely used in answer set programming (ASP) for representing and reasoning on knowledge involving sets of objects collectively. These sets may also depend recursively on the results of the aggregation functions, even if so far the support for such recursive aggregations was quite limited in ASP systems. In fact, recursion over aggregates was restricted to convex aggregates, i.e., aggregates that may have only one transition from false to true, and one from true to false, in this specific order. Recently, such a restriction has been overcome, so that the user can finally use non-convex recursive aggregates in …ASP programs. An evaluation of ASP programs with non-convex recursive aggregates is reported in this paper, also testing a recently proposed extension of the concept of the positive extension graph to the case of programs with aggregates. Moreover, as an additional contribution, new rewritings for EVEN and ODD are presented: EVEN maps to true aggregation sets containing an even number of true literals, and ODD maps to true aggregation sets containing an odd number of true literals. Both aggregates are non-convex, and previously replaced by a conjunction of non-convex sums, whose size is quadratic with respect to the number of literals in the aggregation set. A different rewriting is presented in this paper, whose size is linear with respect to the number of literals in the aggregation set. Show more

Keywords: answer set programming, aggregation functions, non-convex recursive aggregates

DOI: 10.3233/FI-2016-1441

Citation: Fundamenta Informaticae, vol. 149, no. 1-2, pp. 1-34, 2016

Authors: Alviano, Mario

Article Type: Research Article

Abstract: Answer Set Programming (ASP) is a powerful formalism for knowledge representation and common sense reasoning, particularly suitable for representing incomplete knowledge and nonmonotonic reasoning. ASP is used in Artificial Intelligence applications such as diagnosis and planning. Aggregate functions are an important extension to ASP that allow the representation of concepts involving sets of data in a natural way. We have analyzed the properties of recursive aggregates, identified rich classes of programs with a unique answer set, and defined a new notion of unfounded set that we used in answer set computations. Experimental results on the implemented prototype, obtained by extending …DLV, show a significant performance improvement of our enhanced approach over existing techniques. In this paper we summarize some of our results, which are fully described in the thesis of the same title. Show more

Keywords: Logic programming, answer set semantics, recursive aggregates

DOI: 10.3233/IA-2011-0023

Citation: Intelligenza Artificiale, vol. 5, no. 2, pp. 207-215, 2011

Authors: Alviano, Mario

Article Type: Research Article

Abstract: The fundamental mechanism that humans use in argumentation can be formalized in abstract argumentation frameworks. Many semantics are associated with abstract argumentation frameworks, each one consisting of a set of extensions, that is, a set of sets of arguments. Some of these semantics are based on preference relations that essentially impose to maximize or minimize some property. This paper presents the argumentation reasoner PYGLAF , which provides a uniform view of many semantics for abstract argumentation frameworks in terms of circumscription. Specifically, several computational problems of abstract argumentation frameworks are reduced to circumscription by means of linear encodings, and a …few others are solved by means of a sequence of calls to an oracle for circumscription. Finally, grounded extensions are obtained in polynomial time by unit propagation, and acceptance problems are addressed by first checking cardinality optimal models of circumscribed theories, so that the naive extension enumeration is possibly avoided. Show more

Keywords: abstract argumentation frameworks, propositional circumscription, minimal model enumeration, incremental solving

DOI: 10.3233/FI-2019-1808

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 1-30, 2019

Authors: Alviano, Mario | Faber, Wolfgang

Article Type: Research Article

Abstract: For many practical applications of ASP, for instance data integration or planning, query answering is important, and therefore query optimization techniques for ASP are of great interest. Magic Sets are one of these techniques, originally defined for Datalog queries (ASP without disjunction and negation). Dynamic Magic Sets (DMS) are an extension of this technique, which has been proved to be sound and complete for query answering over ASP programs with stratified negation. A distinguishing feature of DMS is that the optimization can be exploited also during the non-deterministic phase of ASP engines. In particular, after some assumptions have been made …during the computation, parts of the program may become irrelevant to a query under these assumptions. This allows for dynamic pruning of the search space, which may result in exponential performance gains. In this paper, the correctness of DMS is formally established and proved for brave and cautious reasoning over the class of super-coherent ASP programs (ASPsc programs). ASPsc programs guarantee consistency (i.e., have answer sets) when an arbitrary set of facts is added to them. This result generalizes the applicability of DMS, since the class of ASPsc programs is richer than ASP programs with stratified negation, and in particular includes all odd-cycle-free programs. DMS has been implemented as an extension of DLV, and the effectiveness of DMS for ASPsc programs is empirically confirmed by experimental results with this system. Show more

Keywords: Magic sets, query answering optimization, general answer set programming

DOI: 10.3233/AIC-2011-0492

Citation: AI Communications, vol. 24, no. 2, pp. 125-145, 2011

Authors: Alviano, Mario | Dodaro, Carmine

Article Type: Research Article

Abstract: Modern, efficient Answer Set Programming solvers implement answer set search via non-chronological backtracking algorithms. The extension of these algorithms to answer set enumeration is nontrivial. In fact, adding blocking constraints to discard already computed answer sets is inadequate because the introduced constraints may not fit in memory or deteriorate the efficiency of the solver. On the other hand, the algorithm implemented by CLASP , which can run in polynomial space, requires to modify the answer set search procedure. The algorithm is revised in this paper so as to make it almost independent from the underlying answer set search procedure, provided …that the procedure accepts as input a logic program and a list of assumption literals, and returns an answer set (and associated branching literals). In fact, thanks to an alternative view in terms of transition systems, the revised algorithm is suitable to easily accommodate the enumerate of models of other Boolean languages, among them classical models of propositional theories. On a pragmatic level, the paper presents two implementations of the enumeration algorithm, in WASP for answer set enumeration, and in GLUCOSE for classical models enumeration. The implemented systems are compared empirically to the state of the art solver CLASP . Show more

Keywords: Answer Set Programming, Enumeration, Assumption Literals

DOI: 10.3233/FI-2019-1809

Citation: Fundamenta Informaticae, vol. 167, no. 1-2, pp. 31-58, 2019

Authors: Alviano, Mario | Dodaro, Carmine

Article Type: Research Article

Abstract: Many efficient algorithms for the computation of optimum stable models in the context of Answer Set Programming (ASP) are based on unsatisfiable core analysis. Among them, algorithm OLL was the first introduced in the context of ASP, whereas algorithms ONE and PMRES were first introduced for solving the Maximum Satisfiability problem (MaxSAT) and later on adapted to ASP. In this paper, we present the porting to ASP of another state-of-the-art algorithm introduced for MaxSAT, namely K , which generalizes ONE and PMRES . Moreover, we present a new algorithm called OLL-IN-ONE that compactly encodes all aggregates of OLL by taking …advantage of shared aggregate sets propagators. The performance of the algorithms have been empirically compared on instances taken from the latest ASP Competition. Show more

Keywords: Answer Set Programming, weak constraints, unsatisfiable core analysis

DOI: 10.3233/FI-2020-1974

Citation: Fundamenta Informaticae, vol. 176, no. 3-4, pp. 271-297, 2020

Authors: Alviano, Mario | Greco, Gianluigi | Guzzo, Antonella

Article Type: Research Article

Abstract: Coalition formation is studied in a setting where agents take part to a group decision-making scenario and where their preferences are expressed via weighted propositional logic, in particular by considering formulas consisting of conjunctions of literals only. Interactions among agents are constrained by an underlying social environment and each agent is associated with a specific social factor determining to which extent she prefers staying in a coalition with other agents. In particular, the utilities of the agents depend not only on their absolute preferences but also on the number of “neighbors” occurring with them in the coalition that emerged. Within …this setting, the computational complexity of a number of relevant reasoning tasks is studied, by charting a clear picture of the intrinsic difficulty of finding “agreements” among the agents. Specific algorithmic approaches to reason about such social environments are proposed under the utilitarian perspective, where the collective utility of a coalition is the sum of the utilities of the individuals, as well as under the egalitarian perspective, with the goal being to maximize the utility of the least satisfied agent. These algorithms have been implemented and results of experimental activity are discussed, too. Show more

Keywords: Social environments, coalition formation, propositional logic, pseudo-Boolean solvers, computational complexity

DOI: 10.3233/AIC-180770

Citation: AI Communications, vol. 31, no. 5, pp. 383-407, 2018

Authors: Alviano, Mario | Dodaro, Carmine | Maratea, Marco

Article Type: Research Article

Abstract: The goal of the Nurse Scheduling Problem is to find an assignment of nurses to shifts according to specific requirements. Frequently, a computed schedule may become not usable because of sudden absences of some nurses. In this cases, Nurse Rescheduling amounts to the computation of a new schedule, which has to satisfy the original requirements and the new absences. Additionally, a good solution to the Nurse Rescheduling Problem must be as similar as possible to the original schedule, which practically means that the number of changes has to be minimized. This paper focuses on the requirements specified by an Italian …hospital, and recently addressed by an approach based on Answer Set Programming (ASP). Even if promising results have been obtained with ASP, the original encoding presents some intrinsic weaknesses, which are identified and eventually circumvented in this paper. The new encoding is designed by taking into account both intrinsic properties of Nurse Scheduling and internal details of ASP solvers, such as cardinality and weight constraint propagators. The performance gain of clingo and wasp is empirically verified on instances from ASP literature. As an additional contribution, the performance of clingo and wasp is compared to other declarative frameworks, namely SAT and ILP; the best performance is obtained by clingo running the new ASP encoding. The advanced ASP encodings are then extended to solve Nurse Rescheduling, and an empirical evaluation is conducted with clingo and wasp . Show more

DOI: 10.3233/IA-170030

Citation: Intelligenza Artificiale, vol. 12, no. 2, pp. 109-124, 2018

Authors: Alviano, Mario | Greco, Gianluigi | Scarcello, Francesco

Article Type: Editorial

DOI: 10.3233/IA-200072

Citation: Intelligenza Artificiale, vol. 14, no. 2, pp. 179-181, 2020