Search

In many applications, especially autonomous exploration, there is a trade-off between operational safety, forcing conservatism about resource usage; and maximising utility, requiring high resource utilisation. In this paper we consider a method of generating plans that maintain this conservatism whilst allowing exploitation of situations where resource usage is better than pessimistically estimated. We consider planning problems with soft goals, each with a violation cost. The challenge is to maximise utility (minimise the violation cost paid) whilst maintaining confidence that the plan will execute within the specified limits. We first show how forward search planning can be extended to generate such plans. Then we extend this to build branched plans: tree structures labelled with conditions on executing branches. Lower cost branches can be followed if their conditions are met. We demonstrate that the use of such plans can dramatically increase utility whilst still obeying strict safety constraints.

We summarise and provide pointers to recent advances in inference and identification for specific types of probabilistic graphical models using imprecise probabilities. Robust inferences can be made in so-called credal networks when the local models attached to their nodes are imprecisely specified as conditional lower previsions, by using exact algorithms whose complexity is comparable to that for the precise-probabilistic counterparts.

A basic task in preference reasoning is inferring a preference between a pair of outcomes (alternatives) from an input set of preference statements. This preference inference task for comparative preferences has been shown to be computationally very hard for the standard kind of inference. Recently, a new kind of preference inference has been developed, which is polynomial for relatively expressive preference languages, and has the additional property of being much less conservative; this can be a major advantage, since it will tend to make the number of undominated outcomes smaller. It derives from a semantics where models are weak orders that are generated by objects called cp-trees, which represent a kind of conditional lexicographic order. We show that there are simple conditions, based on the notion of importance, that determine whether a weak order can be generated by a cp-tree of the given form. This enables a simple characterisation of the less conservative preference inference. We go on to study the importance properties satisfied by a simple kind of cp-tree, leading to another characterisation of the corresponding preference inference.

Argumentation between agents through dialogue is an important cognitive activity. There have been a number of proposals for formalizing dialogical argumentation. However, each proposal involves a number of quite complex definitions, and there is significant diversity in the way different proposals define similar features. This complexity and diversity has hindered analysis and comparison of the space of proposals. To address this, we present a general approach to defining a wide variety of systems for dialogical argumentation. Our solution is to use an executable logic to specify individual systems for dialogical argumentation. This means we have a common language for specifying a wide range of systems, we can compare systems in terms of a range of standard properties, we can identify interesting classes of system, and we can execute the specification of each system to analyse it empirically.

The idea of classifier chains has recently been introduced as a promising technique for multi-label classification. However, despite being intuitively appealing and showing strong performance in empirical studies, still very little is known about the main principles underlying this type of method. In this paper, we provide a detailed probabilistic analysis of classifier chains from a risk minimization perspective, thereby helping to gain a better understanding of this approach. As a main result, we clarify that the original chaining method seeks to approximate the joint mode of the conditional distribution of label vectors in a greedy manner. As a result of a theoretical regret analysis, we conclude that this approach can perform quite poorly in terms of subset 0/1 loss. Therefore, we present an enhanced inference procedure for which the worst-case regret can be upper-bounded far more tightly. In addition, we show that a probabilistic variant of chaining, which can be utilized for any loss function, becomes tractable by using Monte Carlo sampling. Finally, we present experimental results confirming the validity of our theoretical findings.

International audience

International audience

Constraint Programming - CP 2007, 13th International Conference, Providence, RI, USA, September 23-27; International audience

International audience; Open-source platforms are very useful for development and experimentation in constraint programming. However, until recently, no such platform existed for distributed constraint programming. This paper presents DisChoco, a platform for distributed constraint programming. DisChoco is a Java library implemented using the Choco solver and simple agent communication infrastructure (SACI). DisChoco can be used for simulation of a multi-agents environment on a single Java virtual machine, or performed in an environment physically distributed for a realistic use. DisChoco takes into account agent with a complex local problem, message loss, message corruption, and message delay. The implementation of DisChoco was made to offer a modular software architecture which accepts extensions easily. This paper presents the software architecture and illustrates how to implement a specific protocol.

To be held at the 12th International Conference on Principles and Practice of Constraint Programming; International audience; N/A

We recently proposed a simple declarative language for specifying a wide range of counting and occurrence constraints. The language uses just two global primitives: the Range constraint, which computes the range of values used by a set of variables, and the Roots constraint, which computes the variables mapping onto particular values. In order for this specification language to be executable, propagation algorithms for the Range and Roots constraints should be developed. In this paper, we focus on the study of the Range constraint. We propose an efficient algorithm for propagating the Range constraint. We also show that decomposing global counting and occurrence constraints using Range is effective and efficient in practice.