Probabilistic sampling methods have become very popular to solve single-shot path planning problems. Rapidly-exploring Random Trees (RRTs) in particular have been shown to be very efficient in solving high dimensional problems. Even though several RRT variants have been proposed to tackle the dynamic replanning problem, these methods only perform well in environments with infrequent changes. This paper addresses the dynamic path planning problem by combining simple techniques in a multi-stage probabilistic algorithm. This algorithm uses RRTs as an initial solution, informed local search to fix unfeasible paths and a simple greedy optimizer. The algorithm is capable of recognizing when the local search is stuck, and subsequently restart the RRT. We show that this combination of simple techniques provides better responses to a highly dynamic environment than the dynamic RRT variants.

The present paper investigates consequence relations that are both non-monotonic and paraconsistent. More precisely, we put the focus on preferential consequence relations, i.e. those relations that can be defined by a binary preference relation on states labelled by valuations. We worked with a general notion of valuation that covers e.g. the classical valuations as well as certain kinds of many-valued valuations. In the many-valued cases, preferential consequence relations are paraconsistant (in addition to be non-monotonic), i.e. they are capable of drawing reasonable conclusions which contain contradictions. The first purpose of this paper is to provide in our general framework syntactic characterizations of several families of preferential relations. The second and main purpose is to provide, again in our general framework, characterizations of several families of preferential discriminative consequence relations. They are defined exactly as the plain version, but any conclusion such that its negation is also a conclusion is rejected (these relations bring something new essentially in the many-valued cases).

In case-based reasoning, the adaptation of a source case in order to solve the target problem is at the same time crucial and difficult to implement. The reason for this difficulty is that, in general, adaptation strongly depends on domain-dependent knowledge. This fact motivates research on adaptation knowledge acquisition (AKA). This paper presents an approach to AKA based on the principles and techniques of knowledge discovery from databases and data-mining. It is implemented in CABAMAKA, a system that explores the variations within the case base to elicit adaptation knowledge. This system has been successfully tested in an application of case-based reasoning to decision support in the domain of breast cancer treatment.

The on-line shortest path problem is considered under various mode ls of partial monitoring. Given a weighted directed acyclic graph whose edge weights can c hange in an arbitrary (adversarial) way, a decision maker has to choose in each round of a game a path between two distinguished vertices such that the loss of the chosen path (defin ed as the sum of the weights of its composing edges) be as small as possible. In a setting generalizing the multi-armed bandit problem, after choosing a path, the decision maker learns only the w eights of those edges that belong to the chosen path. For this problem, an algorithm is given who se average cumulative loss in n rounds exceeds that of the best path, matched off-line to the ent ire sequence of the edge weights, by a quantity that is proportional to 1 / n and depends only polynomially on the number of edges of the graph. The algorithm can be implemented with linear complexity in the number of rounds n and in the number of edges. An extension to the so-called label efficie nt setting is also given, in which the decision maker is informed about the w eights of the edges corresponding to the chosen path at a total of m n time instances. Another extension is shown where the decision maker competes against a time-varying pa th, a generalization of the problem of tracking the best expert. A version of the multi-armed b andit setting for shortest path is also discussed where the decision maker learns only the total weight of the chosen path but not the weights of the individual edges on the path. Applications to routing in packet switched networks along with simulation results are also presented.

In the recent years rule-based programming in terms of decla rative logic programming has formed the basis for many Artificial In telligence (AI) applications and is well integrated in the mainstream infor mation technology capturing higher-level decision logics. Typically, the st andard rule systems and rule-based logic programming languages such as Prolog deri vatives are based on the untyped theory of predicate calculus with untyped logic al objects (untyped terms), i.e. the logical reasoning algorithms apply pure sy ntactical reasoning. From a rule engineering perspective this is a serious restri ction which lacks major Software Engineering principles such as data abstracti on or modularization, which become more and more important when rule applications grow larger and more complex. To support such principles in logic programmi ng and capture the rule engineer's intended meaning of a logic program, types a nd typed objects play an important role. Moreover, from a computational poin t of view, the use of types drastically reduces the search space, i.e. proofs c an be kept at a more abstract level and it offers the option to restrict the applic ation of rules and to control the level of generality in queries.

The models of statistical physics used to study collective phenomena in some interdisciplinary contexts, such as social dynamics and opinion spreading, do not consider the effects of the memory on individual decision processes. On the contrary, in the Naming Game, a recently proposed model of Language formation, each agent chooses a particular state, or opinion, by means of a memory-based negotiation process, during which a variable number of states is collected and kept in memory. In this perspective, the statistical features of the number of states collected by the agents becomes a relevant quantity to understand the dynamics of the model, and the influence of topological properties on memory-based models. By means of a master equation approach, we analyze the internal agent dynamics of Naming Game in populations embedded on networks, finding that it strongly depends on very general topological properties of the system (e.g. average and fluctuations of the degree). However, the influence of topological properties on the microscopic individual dynamics is a general phenomenon that should characterize all those social interactions that can be modeled by memory-based negotiation processes.

Standard game theory assumes that the structure of the game is common knowledge among players. We relax this assumption by considering extensive games where agents may be unaware of the complete structure of the game. In particular, they may not be aware of moves that they and other agents can make. We show how such games can be represented; the key idea is to describe the game from the point of view of every agent at every node of the game tree. We provide a generalization of Nash equilibrium and show that every game with awareness has a generalized Nash equilibrium. Finally, we extend these results to games with awareness of unawareness, where a player i may be aware that a player j can make moves that i is not aware of, and to subjective games, where payers may have no common knowledge regarding the actual game and their beliefs are incompatible with a common prior.

The failure diagnosis for {\it discrete event systems} (DESs) has been given considerable attention in recent years. Both on-line and off-line diagnostics in the framework of DESs was first considered by Lin Feng in 1994, and particularly an algorithm for diagnosability of DESs was presented. Motivated by some existing problems to be overcome in previous work, in this paper, we investigate the minimal cost algorithm for diagnosability of DESs. More specifically: (i) we give a generic method for judging a system's off-line diagnosability, and the complexity of this algorithm is polynomial-time; (ii) and in particular, we present an algorithm of how to search for the minimal set in all observable event sets, whereas the previous algorithm may find {\it non-minimal} one.

The task is to find a functional dependence between x and y, f: x null y, subject to certain optimality conditions. Representative tasks include binary classification, multi-class classification, regression and ranking. We often want to reduce the dimension of the data (the number of features) before the actual learning (Guyon & Elisseeff, 2003); a larger number of features can be associated with higher data collection cost, more difficulty in model interpretation, higher computational cost for the classifier, and decreased generalisationAppearing in Proceedings of the 24 th International Conference on Machine Learning, Corvallis, OR, 2007.

Some alternatives to probability in the literature include sets of probability measure [Huber 1981; Walley 1991], Dempster-Shafer belief functions [Shafer 1976] and the closely related nonadditive measures [Schmeidler 1989], and possibility measures [Dubois and Prade 1990]. In this paper, we consider the notion of expectation for all these representations of uncertainty. We do not take a stand here on what the "right" way is to represent uncertainty; we simply investigate characterizations of expectation and reasoning about expectation, both for probability and for other representations of uncertainty. It is well known that a probability measure determines a unique expectation function that is linear (i.e., E (aX + bY) = aE (X) + bE (Y)), monotone (i.e., X Y implies E ( X) E (Y)), and maps constant functions to their value. Conversely, given an expectation function E (that is, a function from random variables to the reals) that is linear, monotone, and maps constant functions to their value, there is a unique probability measure µ such that E = E µ. That is, there is a 1-1 mapping from probability measures to (probabilistic) expectation functions. One of the goals of this paper is to provide similar characterizations of expectation for other representations of uncertainty. Some work along these lines has already been done, particulary with regard to sets of probability measures [Huber 1981; Walley 1991; 1981]. 1 However, there seems to be surprisingly little work on characterizing expectation in the context of other measures of uncertainty, such as belief functions [Shafer 1976] and possibility measures [Dubois and Prade 1990].