One of the serious problems in answer set programming is that relatively small pieces of information can cause a total absence of answer sets. To cope with this problem, this paper introduces a class of normal extended logic programs which are extended logic programs, whose defeasible rules are comparable to normal defaults in default logic. Under suitable program transformations, we show that every normal extended logic program always yields at least one answer set.
Particle filtering (PF) for dynamic Bayesian networks (DBNs) with discrete-state spaces includes a resampling step which concentrates samples according to their relative weight in regions of interest of the state-space. We propose a more systematic approach than resampling based on regularisation (smoothing) of the empirical distribution associated with the samples, using the kernel method. We show in our experiments that the smoothed particle filtering (SPF) leads to more accurate estimates than the PF.
Célia da Costa Pereira, Andrea G.B. Tettamanzi, Leila Amgoud
747 - 748
We propose a general framework to represent changes in the mental state of a rational agent due to the acquisition of new information and/or to the arising of new desires; fundamental postulates and properties of the function which generates the goal set are also provided.
Viktor de Boer, Maarten van Someren, Bob J. Wielinga
749 - 750
The Semantic Web requires automatic ontology population methods. We developed an approach, that given existing ontologies, extracts instances of ontology relations, a specific subtask of ontology population. We use generic, domain independent techniques to extract candidate relation instances from the Web and exploit the redundancy of information on the Web to compensate for loss of precision caused by the use of these generic methods. The candidate relation instances are then ranked based on co-occurrence with a seed set. In an experiment, we extracted instances of the relation between artists and art styles. The results were manually evaluated against selected art resources.
We present a novel approach to adaptive multi-agent programming, which is based on an integration of the agent programming language GTGolog with adaptive dynamic programming techniques. GTGolog combines explicit agent programming in Golog with game-theoretic multi-agent planning in stochastic games. In GTGolog, the transition probabilities and reward values of the domain must be provided with the model. The adaptive generalization of GTGolog proposed here is directed towards letting the agents themselves explore and adapt these data. We use high-level programs for the generation of both abstract states and optimal policies.
We present an approach to building libraries of tasks in complex action languages, such as Golog, for query answering. Our formalization is based on a situation calculus framework that allows probabilistic, temporal actions. Once a knowledge base is built containing domain knowledge including type information and a library of tasks and the goals they can achieve, we are interested in queries about the achievability of goals. We consider cases where, using domain object type and goal information in the KB, a user is able to get specific answers to a query while leaving some of the details for the system to figure out. In some cases where the specifics are missing from the KB, the user is provided with possible alternative answers that are compatible with the incomplete information in the KB. This approach is being explored in the context of a military operations planning domain for decision support.
Laura Giordano, Valentina Gliozzi, Nicola Olivetti, Gian Luca Pozzato
757 - 758
We present a tableau calculus for the rational logic R of default reasoning, introduced by Kraus, Lehmann and Magidor. Our calculus is obtained by introducing suitable modalities to interpret conditional assertions, it makes use of labels to represent possible worlds, and it can be used to provide a decision procedure for R.
In order to analyse motion patterns for the purpose of making predictions and to explain the behaviour of systems methods are required for dealing with them. Difficulties in verbalising motion patterns for the purpose of communicating spatiotemporal situations, or in order to index spatiotemporal databases, indicate the importance of means which are simple to handle by human users. This paper proposes a set of sixteen atomic motion patterns which form the basis of a relation algebra. The relations are coarse but crisp, they allow imprecise knowledge about motion patterns to be dealt with, and they are easily accessible from the point of view of the user.
Representing (and reasoning about) preference relations over combinatorial domains is computationally expensive. For many problems involving such preferences, it is relevant to simplify them by projecting them on a subset of variables. We investigate several possible definitions, focusing without loss of generality on propositional (binary) variables.
Christian Anger, Martin Gebser, Tomi Janhunen, Torsten Schaub
769 - 770
Concepts in Answer Set Programming (ASP) are normally defined in terms of atoms.We show that the treatment of atoms and bodies (of rules) as equitable computational objects may yield exponential speed-ups, even for standard ASP-solvers such as smodels. To this end, we give simple transformations providing solvers with access to both kinds of objects and show that some families of examples can be solved exponentially faster after they have been transformed. We prove that these transformations may yield exponentially smaller search spaces.
Planning under uncertainty attracted significant attention in AI and in other fields. To overcome computational problems associated with Markov Decision Processes (MDPs) in large scale domains researchers often take advantage of structural properties and look for approximately optimal solutions. DTGolog, a decision-theoretic agent programming language based on the situation calculus, was proposed to ease some of the computational difficulties by using natural ordering constraints on execution of actions. Using DTGolog, domain specific constraints on the set of available policies can be expressed in a high-level program and this program helps to reduce significantly computation required to find a policy optimal in this set. Our paper explores whether the DTGolog framework can be used to evaluate different designs of a decision making agent in a large real-world domain. Each design is understood as combination of a template (expressed as a Golog program) for available policies and a reward function. To evaluate and compare alternative designs we estimate the probability of goal satisfaction for each design. As a domain, we choose the London Ambulance Service (LAS) case study that is well known in software engineering, but remains unknown in AI. In our paper we demonstrate that DTGolog can be applied successfully to quantitative evaluation of alternative designs in terms of their ability to satisfy a system goal with a high probability. We provide a detailed axiomatization of the domain in the temporal situation calculus with stochastic actions. The main advantage of this representation is that neither actions, not states require explicit enumeration. We do an experimental analysis using an on-line implementation of DTGolog coupled with a simulator that models real time actions of many external agents.
As far as we know, there is no multi-agent system allowing to talk both about choices of agents or groups of agents, strategies, and about sufficiently rich actions. This paper aims at offering a path towards a new more expressive logical framework by mixing a STIT-like logic of agency with a PDL-like logic of action. We present the syntax and ontological motivations, and we highlight the expressivity of the resulting framework on an example.
I want to propose a general framework for user-oriented and content-based recommender systems aimed at providing preferential multicriteria rating on Web Pages and automatic user's profile generation and updating through logic programming techniques.
We empirically study the computational complexity of diagnosing systems with real-world structure. We adopt the structure specified by a small-world network, which is a graphical structure that is common to a wide variety of naturally-occurring systems, ranging from biological systems, the WWW, to human-designed mechanical systems. We randomly generate a suite of digital circuit models with small-world network structure, and show that diagnosing these models is computationally hard.
Shlomo Berkovsky, Dan Goldwasser, Tsvi Kuflik, Francesco Ricci
789 - 790
Providing accurate personalized information services to the users requires knowing their interests and needs, as defined by their User Models (UMs). Since the quality of the personalization depends on the richness of the UMs, services would benefit from enriching their UMs through importing and aggregating partial UMs built by other services from relatively similar domains. The obvious question is how to determine the similarity of domains? This paper proposes to compute inter-domain similarities by exploiting well-known Information Retrieval techniques for comparing textual contents of the Web-sites, classified under the domain nodes in Web-directories. Initial experiments validate feasibility of the proposed approach and raise open research questions.
The two objectives when estimating the conditional density function in a regression problem are to maximise sharpness (the density rewarded to the actual observation), while maintaining calibration (the empirical validity of the probability estimates). In this paper we outline a process of optimisation that maximises both these objectives simultaneously to make better probabilistic predictions.