The project aims at designing innovative, fondamental models and methods for enabling autonomous agents (e.g., mobile robots, personal software assistants) to learn and to act using all type of information. We target two specific types of information, namely: numerical information, like statistics or probabilities modelling effectors and sensors, and symbolic information, as typically provided by humans when they specify norms, obligations, constraints, etc.
The goals of the project are of fundamental nature. We aim at providing methods bridging the gap between series of work, some of which have considered the probabilistic aspects of decision problems, while others have considered the symbolic aspects. What is at stake here is application domains like robotics at the service of humans or spacial exploration. <br /> <br />In the first type of applications, in domotics, for instance, the issue is to enable a user to interact with robots in a natural (symbolic) manner, e.g., by specifying quantitative preferences: «I prefer my automated vacuum cleaner to start with the first floor before the second one«, while keeping the ability to deal with uncertain, probabilistic environments, for planning (uncertainty on the duration of some task, for example). <br /> <br />In the second type of applications, the issues are to provide means for symbolically specifying behaviours, which are nevertheless meant to be executed in an uncertain environment. Such issues are of primary importance in applications to space exploration by autonomous machines, or in military applications, since the behaviours of autonomous machines must systematically be verified and validated by human experts. Having expressions of these behaviours in a language which is symbolic, natural for experts, is thus a major issue.
The project addresses its objectives from the viewpoint of modelling and algorithmics. We search for formal models which take into account all aspects of the problems which we tackle: uncertainty, symbolic knowledge, objectives of the agents, etc. We propose algorithms for the decision, learning, and reasoning problems in such models. The proposed algorithms must be efficient, as evaluated by theory, but also in practice, as evaluated by benchmarking.
A concrete application, to a problem of spatial mapping of adventices in fields, is also studied in the context of the project. This application serves as a testbed for methods and for the adequacy of models to a real-life problem.
We proposed a new language for representing action plans (to be followed by an agent exécuting a task). In this representation, the knowledge of the agent at some point are made explicit, which makes plans more compact as well as more readable. Readibility makes verification and validation by humans easier, and compacity makes it easier, for instance, to send such plan to a satelite from a base on Earth.
We also proposed models and approaches for decision problems involving uncertainty, when the available rewards (feedbacks) are of qualitative (ordinal) nature. This way we allow, for instance, a human user to «punish« or «reward« an agent at her service in a qualitative rather than by a value on some numerical sclae (which is always difficult to interpret). So one can imagine an automated system for medical diagnosis learning to diagnose better using feedback from physicians such as «this diagnosis was good« or «this diagnosis was less good than the former one«, etc.
We plan to extend the representation of plans using explicit knowledge to action policies for multi-agent systems, viz. to decentralized policies. Such extensions are of great interest, for instance in application in which teams of autonomous machines, rather than isolated agents, are concerned by a given mission.
We also plan to use the results obtained for learning from qualitative feedback for a real-life application. The application is to the improvement of an automated process of information extraction, in the context of a PhD thesis in collaboration with a company.
A Java library providing the methods and algorithms designed in the project is currently under development. Our objective is to integrate to this library a large panel of standard techniques of Artificial Intelligence and to release it under an open-source licence, to as to allow the scientific community, but also industrial projects, to use the techniques and tools.
On the international scene, the project produced scientific publications in important conferences and journals:
* 5 publications (in collboration between several partners of the project) in international conferences, among which 2 ranked A and 2 ranked A* (Australian CORE ranking)
* 2 publications in international journals (ranked A)
* 7 publications in international conferences (4 ranked A*, 2 ranked A, among which 2 with collaborators not part of the project)
* 4 publications in international workshops
This project addresses the question of decision-making for autonomous agents equipped with knowledge. In most real-world applications, such agents have to face a lot of challenges for taking optimal decisions: the environment is typically dynamic, uncertain, and only partially observable; it is described over an extremely large number of attributes; decision must be very fast.
In order to design agents which are able to handle these problems, the Artificial Intelligence community has developed complementary approaches, in particular symbolic (logical) and numerical formalisms. Numerical formalisms (in particular, Markov networks, Bayesian networks, Markov Decision Processes and their derivatives) are typically suited for representing the stochastic effects of actions and the stochastic evolution of the environment, and can be learned and solved with various techniques. On the other hand, logical formalisms (e.g., attribute-value, relational, epistemic) are well suited for expressing hard constraints, norms, epistemic knowledge, goals, etc. In particular, logic is more declarative in essence, making it easier for humans to manipulate. Again, these formalisms come with various techniques for learning and reasoning.
Our proposal stems from the observation that an agent placed in a real-world environment has typically access to some information through numerical models, and to some other in logical form. Then, a natural rationality requirement is that its decisions take all this information into account. Typically, a soccer robot needs a numerical model of its effectors (obtained by simulation or training), but also a logical model of the game rules. Another typical situation is medicine, where both numerical estimates of the efficiency of treatments or the exactness of analyses and logical expert knowledge are needed.
So, the problem we will attack can be formulated as follows: design approaches for taking rational decisions when part of the information about the environment, actions, and rewards is given in numerical form, and part in logical form.
A complete approach for handling this problem must take into account the following three subproblems: representation of the problem; optimal policy computation; reinforcement learning.
We will attack these problems from the point of view of complexity-theory and algorithmics, hence identifying the complexity of problems, identifying tractable restrictions and designing efficient algorithms (both in terms of complexity and in practice). This is justified by the fact that most problems are already known to be computationally hard even when numerical and logical information are not considered together (e.g., in Partially Observable Markov Decision Processes - POMDPs). To that aim, we will build on existing factored representations of (PO)MDPs, especially by Dynamic Bayesian Networks and Probabilistic STRIPS Operators, which are based on propositional attributes. The focus on propositional logic rather than more expressive relational formalisms will ensure decidability of most problems, reasonable complexity, and possible reuse of very efficient software, e.g., for satisfiability.
The proposed representations and algorithms will be illustrated on two large-scale applications. The first one consists in building occurrence maps of spatial processes, where the decisions to be taken are the locations to visit for getting information about the occurrence of the process. A real application is studied at INRA where the process to be mapped is the growth of invasive species. The second application concerns nonplaying characters in video games.
Monsieur BRUNO ZANUTTINI (UNIVERSITE DE CAEN - BASSE-NORMANDIE) – firstname.lastname@example.org
The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.
LAMSADE UNIVERSITE PARIS IX [DAUPHINE]
INRA INRA -CENTRE DE RECHERCHE DE TOULOUSE
GREYC UNIVERSITE DE CAEN - BASSE-NORMANDIE
LIP6 UNIVERSITE PARIS VI [PIERRE ET MARIE CURIE]
Help of the ANR 303,499 euros
Beginning and duration of the scientific project: - 48 Months