1,720,995 research outputs found
Geometric reasoning on the Traveling Salesperson Problem: comparing Answer Set Programming and Constraint Logic Programming Approaches
No full textThe Traveling Salesperson Problem (TSP) is one of the best-known problems in computer science. Many instances and real world applications fall into the Euclidean TSP special case, in which each node is identified by its coordinates on the plane and the Euclidean distance is used as cost function. It is worth noting that in the Euclidean TSP more information is available than in the general case; in a previous publication, the use of geometric information has been exploited to speedup TSP solving for Constraint Logic Programming (CLP) solvers. In this work, we study the applicability of geometric reasoning to the Euclidean TSP in the context of an ASP computation. We compare experimentally a classical ASP approach to the TSP and the effect of the reasoning based on geometric properties. We also compare the speedup of the additional filtering based on geometric information on an Answer Set Programming (ASP) solver and a CLP on Finite Domain (CLP(FD)) solver
ASPECT: Answer Set rePresentation as vEctor graphiCs in laTex
No full textLogic programming is a declarative programming paradigm that finds extensive use in the field of Artificial Intelligence (AI). As a result, it has become a valuable tool used in university courses for teaching students AI techniques. Besides Prolog language, the more recent Answer Set Programming (ASP) language turns out to be a powerful tool for developing advanced applications due to the expressiveness of the language and the availability of efficient solving systems. Unfortunately, the output of ASP solvers can be difficult to interpret, since it is a set of atoms, often long and verbose. This is most true in the case of students learning the language or in the case of experts developing applications for complex real-world problems. For these reasons, the ability to produce, when possible, a graphical representation of the solver output becomes useful to ensure easier interpretation of the results. In this paper we present ASPECT, a sub-language of ASP in which the user can directly define, in an intuitive and declarative way, a graphical representation of the answer set. The ASPECT atoms can be converted into the popular LaTeX markup language to produce vector graphics. The documents produced by ASPECT are easy to embed in documents such as scientific articles, course handouts, and presentations. Also, the development of user-friendly interfaces is critical for wider use of similar technologies in the industrial sector as well
Logic-Based Benders Decomposition in Answer Set Programming for Chronic Outpatients Scheduling
No full textIn answer set programming (ASP), the user can define declaratively a problem and solve it with efficient solvers; practical applications of ASP are countless and several constraint problems have been successfully solved with ASP. On the other hand, solution time usually grows in a superlinear way (often, exponential) with respect to the size of the instance, which is impractical for large instances. A widely used approach is to split the optimization problem into subproblems (SPs) that are solved in sequence, some committing to the values assigned by others, and reconstructing a valid assignment for the whole problem by juxtaposing the solutions of the single SPs. On the one hand, this approach is much faster due to the superlinear behavior; on the other hand, it does not provide any guarantee of optimality: committing to the assignment of one SP can rule out the optimal solution from the search space. In other research areas, logic-Based Benders decomposition (LBBD) proved effective; in LBBD, the problem is decomposed into a master problem (MP) and one or several SPs. The solution of the MP is passed to the SPs that can possibly fail. In case of failure, a no-good is returned to the MP that is solved again with the addition of the new constraint. The solution process is iterated until a valid solution is obtained for all the SPs or the MP is proven infeasible. The obtained solution is provably optimal under very mild conditions. In this paper, we apply for the first time LBBD to ASP, exploiting an application in health care as case study. Experimental results show the effectiveness of the approach. We believe that the availability of LBBD can further increase the practical applicability of ASP technologies
Nonground Abductive Logic Programming with Probabilistic Integrity Constraints
No full textUncertain information is being taken into account in an increasing number of application fields. In the meantime, abduction has been proved a powerful tool for handling hypothetical reasoning and incomplete knowledge. Probabilistic logical models are a suitable framework to handle uncertain information, and in the last decade many probabilistic logical languages have been proposed, as well as inference and learning systems for them. In the realm of Abductive Logic Programming (ALP), a variety of proof procedures have been defined as well. In this paper, we consider a richer logic language, coping with probabilistic abduction with variables. In particular, we consider an ALP program enriched with integrity constraints à la IFF, possibly annotated with a probability value. We first present the overall abductive language and its semantics according to the Distribution Semantics. We then introduce a proof procedure, obtained by extending one previously presented, and prove its soundness and completeness
A Decomposition Approach to the Clinical Pathway Deployment for Chronic Outpatients with Comorbidities
No full textBranching interval algebra: An almost complete picture
No full textBranching Algebra is the natural branching-time generalization of Allen's Interval Algebra. As in the linear case, the consistency problem for Branching Algebra is NP-HARD. Branching Algebra has many potential applications in different areas of Artificial Intelligence; therefore, being able to efficiently solve classical problems expressed in Branching Algebra is very important. This can be achieved in two steps: first, by identifying expressive enough, yet tractable fragments of the whole algebra, and, second, by using such fragments to boost the performances of a backtracking algorithm for the whole language. In this paper we study the properties of several such fragments, both from the algebraic and the computational point of view, and we give an almost complete picture of tractable and non-tractable fragments of the Branching Algebra
Modeling opinion polarization on social media: Application to Covid-19 vaccination hesitancy in Italy
No full textThe SARS-CoV-2 pandemic reminded us how vaccination can be a divisive topic on which the public conversation is permeated by misleading claims, and thoughts tend to polarize, especially on online social networks. In this work, motivated by recent natural language processing techniques to systematically extract and quantify opinions from text messages, we present a differential framework for bivariate opinion formation dynamics that is coupled with a compartmental model for fake news dissemination. Thanks to a mean-field analysis we demonstrate that the resulting Fokker-Planck system permits to reproduce bimodal distributions of opinions as observed in polarization dynamics. The model is then applied to sentiment analysis data from social media platforms in Italy, in order to analyze the evolution of opinions about Covid-19 vaccination. We show through numerical simulations that the model is capable to describe correctly the formation of the bimodal opinion structure observed in the vaccine-hesitant dataset, which is witness of the known polarization effects that happen within closed online communities
Decomposition approaches for scheduling chronic outpatients' clinical pathways in Answer Set Programming
No full textChronic patients suffering from non-communicable diseases are often enrolled into a diagnostic and therapeutic care program featuring a personalized care plan. Healthcare is mostly provided at the patient's home, but those examinations and treatments that must be delivered at the hospital have to be explicitly booked. Booking is not trivial due to, on the one hand, the several time constraints that become particularly tight in the case of comorbidity, on the other hand, the limited availability of both staff and equipment at the hospital care units. This suggests that the scheduling of the clinical pathways for enrolled outpatients should be managed in a centralized manner, taking advantage of the fact that demand for services is known well in advance. The aim is to serve as many requests as possible (unattended requests are supplied by contracted private health facilities) in a timely manner, taking patients priority into account. Booking involves setting a date and a time for each selected health service, which is rather complex. In this work, we provide a declarative approach by encoding the problem in Answer Set Programming (ASP). In order to improve the scalability of the ASP approach, we present and compare two heuristic approaches, respectively based on service demand and time decomposition. All approaches are tested on instances of increasing size to assess scalability with respect to time horizon and number of requests
- …
