Reasoning with Sets of Defaults in Default Logic

We present a general approach for representing and reasoning with sets of defaults in default logic, focusing on reasoning about preferences among sets of defaults. First, we consider how to control the application of a set of defaults so that either all apply (if possible) or none do (if not). From this, an approach to dealing with preferences among sets of default rules is developed. We begin with an ordered default theory , consisting of a standard default theory, but with possible preferences on sets of rules. This theory is transformed into a second, standard default theory wherein the preferences are respected. The approach differs from other work, in that we obtain standard default theories and do not rely on prioritized versions of default logic. In practical terms this means we can immediately use existing default logic theorem provers for an implementation. Also, we directly generate just those extensions containing the most preferred applied rules; in contrast, most previous approaches generate all extensions, then select the most preferred. In a major application of the approach, we show how semimonotonic default theories can be encoded so that reasoning can be carried out at the object level. With this, we can reason about default extensions from within the framework of a standard default logic. Hence one can encode notions such as skeptical and credulous conclusions, and can reason about such conclusions within a single extension.     

Automated instructional design for CSCL: A hierarchical task network planning approach

In Computer Supported Collaborative Learning (CSCL), one of the most important tasks for instructional designers is to define scenarios that foster group learning. Such scenarios, defined as Units of Learning (UoLs), comprise different components and are organized according to pedagogical approaches to orchestrate group learning processes. Examples of UoL components are learning objects, student roles, student characteristics (e.g., background, preferences, learning styles, etc.), instructional/learning goals, and activities, among others. Thus, the instructional design (ID) of a proper UoL for CSCL is a complex task that requires practice and experience. This is particularly true when designing, developing, adapting, and customizing UoLs, taking into consideration different instructional/learning goals and individual preferences of students. This paper therefore proposes using a Hierarchical Task Network (HTN) planning approach to automate and optimize the tasks of designers. To accomplish that, we define an initial CSCL scenario as “an ID task” and “a set of information related to students and the domain to be taught.” Then we propose a model that formally describes ID for CSCL as HTN planning, where the initial CSCL scenario is adapted and refined according to student needs. In this model, the ID strategies are defined as hierarchical tasks and methods into a planning domain definition, and the initial CSCL scenario is defined as a planning problem definition. To validate our approach, we develop a CSCL courseware generator that (i) helps designers to set up an initial CSCL scenario; (ii) automatically generates a personalized UoL based on a given initial scenario; and (iii) supports the adaptation of UoLs.     

A heuristic search approach to planning with temporally extended preferences

Planning with preferences involves not only finding a plan that achieves the goal, it requires finding a preferred plan that achieves the goal, where preferences over plans are specified as part of the planner's input. In this paper we provide a technique for accomplishing this objective. Our technique can deal with a rich class of preferences, including so-called temporally extended preferences (TEPs). Unlike simple preferences which express desired properties of the final state achieved by a plan, TEPs can express desired properties of the entire sequence of states traversed by a plan, allowing the user to express a much richer set of preferences. Our technique involves converting a planning problem with TEPs into an equivalent planning problem containing only simple preferences. This conversion is accomplished by augmenting the inputed planning domain with a new set of predicates and actions for updating these predicates. We then provide a collection of new heuristics and a specialized search algorithm that can guide the planner towards preferred plans. Under some fairly general conditions our method is able to find a most preferred plan—i.e., an optimal plan. It can accomplish this without having to resort to admissible heuristics, which often perform poorly in practice. Nor does our technique require an assumption of restricted plan length or make-span. We have implemented our approach in the HPlan-P planning system and used it to compete in the 5th International Planning Competition, where it achieved distinguished performance in the Qualitative Preferences track.     

Efficient and non-parametric reasoning over user preferences

We consider the problem of modeling and reasoning about statements of ordinal preferences expressed by a user, such as monadic statement like “X is good,” dyadic statements like “X is better than Y,” etc. Such qualitative statements may be explicitly expressed by the user, or may be inferred from observable user behavior. This paper presents a novel technique for efficient reasoning about sets of such preference statements in a semantically rigorous manner. Specifically, we propose a novel approach for generating an ordinal utility function from a set of qualitative preference statements, drawing upon techniques from knowledge representation and machine learning. We provide theoretical evidence that the new method provides an efficient and expressive tool for reasoning about ordinal user preferences. Empirical results further confirm that the new method is effective on real-world data, making it promising for a wide spectrum of applications that require modeling and reasoning about user preferences.     

Learning classifier systems from a reinforcement learning perspective

 We analyze learning classifier systems in the light of tabular reinforcement learning. We note that although genetic algorithms are the most distinctive feature of learning classifier systems, it is not clear whether genetic algorithms are important to learning classifiers systems. In fact, there are models which are strongly based on evolutionary computation (e.g., Wilson's XCS) and others which do not exploit evolutionary computation at all (e.g., Stolzmann's ACS). To find some clarifications, we try to develop learning classifier systems “from scratch”, i.e., starting from one of the most known reinforcement learning technique, Q-learning. We first consider thebasics of reinforcement learning: a problem modeled as a Markov decision process and tabular Q-learning. We introduce a formal framework to define a general purpose rule-based representation which we use to implement tabular Q-learning. We formally define generalization within rules and discuss the possible approaches to extend our rule-based Q-learning with generalization capabilities. We suggest that genetic algorithms are probably the most general approach for adding generalization although they might be not the only solution.     

Utility Models for Goal‐Directed, Decision‐Theoretic Planners

AI planning agents are goal-directed : success is measured in terms of whether an input goal is satisfied. The goal gives structure to the planning problem, and planning representations and algorithms have been designed to exploit that structure. Strict goal satisfaction may be an unacceptably restrictive measure of good behavior, however.
A general decision-theoretic agent, on the other hand, has no explicit goals: success is measured in terms of an arbitrary preference model or utility function defined over plan outcomes. Although it is a very general and powerful model of problem solving, decision-theoretic choice lacks structure, which can make it difficult to develop effective plan‐generation algorithms.
This paper establishes a middle ground between the two models. We extend the traditional AI goal model in several directions: allowing goals with temporal extent, expressing preferences over partial satisfaction of goals, and balancing goal satisfaction against the cost of the resources consumed in service of the goals. In doing so we provide a utility model for a goal-directed agent.
An important quality of the proposed model is its tractability. We claim that our model, like classical goal models, makes problem structure explicit. This structure can then be exploited by a problem-solving algorithm. We support this claim by reporting on two implemented planning systems that adopt and exploit our model.     

Reasoning about Actions and Planning with Preferences Using Prioritized Default Theory

This paper shows how action theories, expressed in an extended version of the language     , can be naturally encoded using Prioritized Default Theory . We also show how prioritized default theory can be extended to express preferences between rules . This extension provides a natural framework to introduce different types of preferences in action theories— preferences between actions and preferences between final states . In particular, we demonstrate how these preferences can be expressed within extended prioritized default theory. We also discuss how this framework can be implemented in terms of answer set programming.     

Assumption‐Based Argumentation Equipped with Preferences and its Application to Decision Making,Practical Reasoning,and Epistemic Reasoning

The existing approaches that map the given explicit preferences into standard assumption‐based argumentation (ABA) frameworks reveal some difficulties such as generating a huge number of rules. To overcome them, we present an assumption‐based argumentation framework equipped with preferences (p_ABA). It increases the expressive power of ABA by incorporating preferences between sentences into the framework. The semantics of p_ABA is given by extensions, which are maximal among extensions of ABA with regard to the extension ordering “lifted” from the given sentence ordering. As a theoretical contribution of this study, we show that prioritized logic programming can be formulated as a specific form of p_ABA. The advantage of our approach is that not only does p_ABA enable us to express different kinds of preferences such as preferences over rules, over goals, or over decisions by means of sentence orderings but we can also successfully obtain solutions from extensions of the p_ABA expressing the respective knowledge for various applications such as epistemic reasoning, practical reasoning, and decision making with preferences in a uniform and domain‐independent way without suffering from difficulties of the existing approaches.     

Multi-Agent Constraint Systems with Preferences: Efficiency, Solution Quality, and Privacy Loss

In this paper, we consider multi-agent constraint systems with preferences, modeled as soft constraint systems in which variables and constraints are distributed among multiple autonomous agents. We assume that each agent can set some preferences over its local data, and we consider two different criteria for finding optimal global solutions: fuzzy and Pareto optimality. We propose a general graph-based framework to describe the problem to be solved in its generic form. As a case study, we consider a distributed meeting scheduling problem where each agent has a pre-existing schedule and the agents must decide on a common meeting that satisfies a given optimality condition. For this scenario we consider the topics of solution quality, search efficiency, and privacy loss, where the latter pertains to information about an agent's pre-existing meetings and available time-slots. We also develop and test strategies that trade efficiency for solution quality and strategies that minimize information exchange, including some that do not require inter-agent comparisons of utilities. Our experimental results demonstrate some of the relations among solution quality, efficiency, and privacy loss, and provide useful hints on how to reach a tradeoff among these three factors. In this work, we show how soft constraint formalisms can be used to incorporate preferences into multi-agent problem solving along with other facets of the problem, such as time and distance constraints. This work also shows that the notion of privacy loss can be made concrete so that it can be treated as a distinct, manipulable factor in the context of distributed decision making.     

Termination for Hybrid Tableaus

This article extends and improves work on tableau-based decisionmethods for hybrid logic by Bolander and Braüner. Theirpaper gives tableau-based decision procedures for basic hybridlogic (with unary modalities) and the basic logic extended withthe global modality. All their proof procedures make use ofloop-checks to ensure termination.  Here we take a closer look at termination for hybrid tableaus.We cover both types of system used in hybrid logic: prefixedtableaus and internalized tableaus. We first treat prefixedtableaus. We prove a termination result for the basic language(with n-ary operators) that does not involve loop-checks. Wethen successively add the global modality and n-ary inversemodalities, show why various different types of loop-check arerequired in these cases, and then re-prove termination. Followingthis we consider internalized tableaus. At first sight, suchsystems seem to be more complex. However, we define a internalizedsystem which terminates without loop-checks. It is simpler thanpreviously known internalized systems (all of which requireloop-checks to terminate) and simpler than our prefix systems(no non-local side conditions on rules are required).     

Travel Plans in Public Transit Networks Using Artificial Intelligence Planning Models

Users of public transit networks require tools that generate travel plans to traverse them. The main issue is that public transit networks are time and space dependent. Travel plans depend on the current location of users and transit units, along with a set of user preferences and time restrictions. In this work, we propose the design and development of artificial intelligence (AI) planning models for engineering travel plans for such networks. The proposed models consider temporal actions, bus locations, and user preferences as constraints, to restrict the set of travel plans generated. Our approach decouples model design from algorithm construction, providing a greater level of flexibility and richness of solutions. We also introduce an integer linear programming formulation, and a fast preprocessing procedure, to evaluate the quality of the solutions returned by the proposed planning models. Experimental results show that AI planning models can efficiently generate close to optimal solutions. Furthermore, our analysis identifies user preferences as the most critical factor that increases solution complexity for planning models.     

Logic-based automated multi-issue bilateral negotiation in peer-to-peer e-marketplaces

We present a novel logic-based framework to automate multi-issue bilateral negotiation in e-commerce settings. The approach exploits logic as communication language among agents, and optimization techniques in order to find Pareto-efficient agreements. We introduce , a propositional logic extended with concrete domains, which allows one to model relations among issues (both numerical and non-numerical ones) via logical entailment, differently from well-known approaches that describe issues as uncorrelated. Through it is possible to represent buyer’s request, seller’s supply and their respective preferences as formulas endowed with a formal semantics, e.g., “if I spend more than 30000 € for a sedan then I want more than a two-years warranty and a GPS system included”. We mix logic and utility theory in order to express preferences in a qualitative and quantitative way. We illustrate the theoretical framework, the logical language, the one-shot negotiation protocol we adopt, and show we are able to compute Pareto-efficient outcomes, using a mediator to solve an optimization problem. We prove the computational adequacy of our method by studying the complexity of the problem of finding Pareto-efficient solutions in our setting.     

Geometric stable roommates

We consider instances of the Stable Roommates problem that arise from geometric representation of participants' preferences: a participant is a point in a metric space, and his preference list is given by the sorted list of distances to the other participants. We show that contrary to the general case, the problem admits a polynomial-time solution even in the case when ties are present in the preference lists.We define the notion of an α-stable matching: the participants are willing to switch partners only for a (multiplicative) improvement of at least α. We prove that, in general, finding α-stable matchings is not easier than finding matchings that are stable in the usual sense. We show that, unlike in the general case, in a three-dimensional geometric stable roommates problem, a 2-stable matching can be found in polynomial time.     

Beyond organisational agendas: using boundary critique to facilitate the inclusion of societal concerns in information systems planning

As the development of the information society takes place worldwide, individuals, groups and organisations face the challenge of taking advantage of information and communication technologies (ICTs). ‘Digital divides’ are emerging: some sections of society are gaining access to information, knowledge and technologies while others are being excluded. There also seems to be an over-concentration on the use of ICTs for organisational purposes, with traditional information systems (IS) planning approaches largely ignoring the needs and concerns that people express outside formal organisations. One answer to this problem might be to adopt a systems approach to IS planning. At first sight this appears to be a good idea because of the aspiration of systems approaches to comprehensiveness, presumably looking beyond organisational concerns. However, a review of two popular systems methodologies employed in IS planning suggests that there is potential for their scope to be equally limited by organisational boundaries. There is a need to enhance the critical review of the boundaries of IS planning processes, enabling people to consider family, community and other concerns. In this paper, we use the systems theory of boundary critique to derive a set of questions to help practitioners reflect on different possible boundaries for IS planning exercises. These should be seen as complementary to existing systems approaches rather than as a replacement for them, enabling the latter to be practised more critically. We end by presenting our reflections on using these questions in the context of an IS planning project in a Colombian University.     

Learning opponent’s preferences for effective negotiation: an approach based on concept learning

We consider automated negotiation as a process carried out by software agents to reach a consensus. To automate negotiation, we expect agents to understand their user’s preferences, generate offers that will satisfy their user, and decide whether counter offers are satisfactory. For this purpose, a crucial aspect is the treatment of preferences. An agent not only needs to understand its own user’s preferences, but also its opponent’s preferences so that agreements can be reached. Accordingly, this paper proposes a learning algorithm that can be used by a producer during negotiation to understand consumer’s needs and to offer services that respect consumer’s preferences. Our proposed algorithm is based on inductive learning but also incorporates the idea of revision. Thus, as the negotiation proceeds, a producer can revise its idea of the consumer’s preferences. The learning is enhanced with the use of ontologies so that similar service requests can be identified and treated similarly. Further, the algorithm is targeted to learning both conjunctive as well as disjunctive preferences. Hence, even if the consumer’s preferences are specified in complex ways, our algorithm can learn and guide the producer to create well-targeted offers. Further, our algorithm can detect whether some preferences cannot be satisfied early and thus consensus cannot be reached. Our experimental results show that the producer using our learning algorithm negotiates faster and more successfully with customers compared to several other algorithms.     

Strong order equivalence

Recently, strong equivalence for Answer Set Programming has been studied intensively, and was shown to be beneficial for modular programming and automated optimization. In this paper we define the novel notion of strong order equivalence for logic programs with preferences (ordered logic programs). Based on this definition we give, for several semantics for preference handling, necessary and sufficient conditions for programs to be strongly order equivalent. These results allow us also to associate a so-called SOE structure to each ordered logic program, such that two ordered logic programs are strongly order equivalent if and only if their SOE structures coincide. We also present the relationships among the studied semantics with respect to strong order equivalence, which differs considerably from their relationships with respect to preferred answer sets. Furthermore, we study the computational complexity of several reasoning tasks associated to strong order equivalence. Finally, based on the obtained results, we present – for the first time – simplification methods for ordered logic programs.     

A heuristic technique for multi‐agent planning

The subject of multi‐agent planning has been of continuing concern in Distributed Artificial Intelligence (DAI). In this paper, we suggest an approach to multi‐agent planning that contains heuristic elements. Our method makes use of subgoals, and derived sub‐plans, to construct a global plan. Agents solve their individual sub‐plans, which are then merged into a global plan. The suggested approach reduces overall planning time and derives a plan that approximates the optimal global plan that would have been derived by a central planner, given those original subgoals. We explore three different scenarios. The first involves a group of agents with a common goal. The second considers how agents can interleave planning and execution when planning towards a common, though dynamic, goal. The third examines the case where agents, each with their own goal, can plan together to reach a state in consensus for the group. Finally, we consider how these approaches can be adapted to handle rational, manipulative agents. This revised version was published online in June 2006 with corrections to the Cover Date.     

Modelling and learning user preferences over sets

Although there has been significant research on modelling and learning user preferences for various types of objects, there has been relatively little work on the problem of representing and learning preferences over sets of objects. We introduce a representation language, DD-PREF, that balances preferences for particular objects with preferences about the properties of the set. Specifically, we focus on the depth of objects (i.e. preferences for specific attribute values over others) and on the diversity of sets (i.e. preferences for broad vs. narrow distributions of attribute values). The DD-PREF framework is general and can incorporate additional object- and set-based preferences. We describe a greedy algorithm, DD-Select, for selecting satisfying sets from a collection of new objects, given a preference in this language. We show how preferences represented in DD-PREF can be learned from training data. Experimental results are given for three domains: a blocks world domain with several different task-based preferences, a real-world music playlist collection, and rover image data gathered in desert training exercises.     

An agent specific planning algorithm

Planning algorithms are often applied by intelligent agents for achieving their goals. For the plan creation, this kind of algorithm uses only an initial state definition, a set of actions, and a goal; while agents also have preferences and desires that should to be taken into account. Thus, agents need to spend time analyzing each plan returned by these algorithms to find one that satisfies their preferences. In this context, we have studied an alternative in which a classical planner could be modified to accept a new conceptual parameter for a plan creation: an agent mental state composed by preferences and constraints. In this work, we present a planning algorithm that extends a partial order algorithm to deal with the agent’s preferences. In this way, our algorithm builds an adequate plan in terms of agent mental state. In this article, we introduce this algorithm and expose experimental results showing the advantages of this adaptation.     

Learners’ navigation behavior identification based on trace analysis

Identifying learners’ behaviors and learning preferences or styles in a Web-based learning environment is crucial for organizing the tracking and specifying how and when assistance is needed. Moreover, it helps online course designers to adapt the learning material in a way that guarantees individualized learning, and helps learners to acquire meta-cognitive knowledge. The goal of this research is to identify learners’ behaviors and learning styles automatically during training sessions, based on trace analysis. In this paper, we focus on the identification of learners’ behaviors through our system: Indicators for the Deduction of Learning Styles. We shall first present our trace analysis approach. Then, we shall propose a ‘navigation type’ indicator to analyze learners’ behaviors and we shall define a method for calculating it. To this end, we shall build a decision tree based on semantic assumptions and tests. To validate our approach, and improve the proposed calculation method, we shall present and discuss the results of two experiments that we conducted.