In this article, we present the main results of the feasibility study we have carried out about autonomous decision making on board an Earth‐observing agile satellite, equipped with a cloud detection instrument. We explain the requirements in terms of autonomy. Then, we describe the online decision‐making problem to manage on board, the reactive/deliberative architecture we used, the decision rules used by the reactive part, and the iterated stochastic greedy search used by the deliberative part. At each step, we try to justify the design choices we made by comparing them with other possible choices. Finally, we present results of experiments performed on offline and online realistic scenarios.

Knowledge compilation [6, 5, 14, 8] consists in transforming a problem offline into a form which is tractable online. In this paper, we introduce new structures, based on the notion of interval automaton (IA), adapted to the compilation of problems involving both discrete and continuous variables, and especially of decision policies and transition tables, in the purpose of controlling autonomous systems.

Controller synthesis consists in automatically building controllers taking as inputs observation data and returning outputs guaranteeing that the controlled system satisfies some desired properties. In system specification, these properties may be safety properties specifying that some conditions must always hold. In planning, they express that the evolution of the controlled system must terminate in a goal state. In this paper, we propose a generic approach able to synthesize memoryless or finite-memory controllers for both safety-oriented and goal-oriented control problems. This approach relaxes some restrictive assumptions made by existing work on controller synthesis with non-determinism and partial observability and is shown to induce potentially significant gains. The proposed “Simulate and Branch” algorithm consists in exploring the possible evolutions of the controlled system and in adding new control elements when uncovered states are discovered. The approach developed is constraint-based in the sense that control problems are formulated using the flexibility of constraint programming languages and that our implementation uses the Gecode constraint programming library.

Numerous formalisms and dedicated algorithms have been designed in the last decades to model and solve decision making problems. Some formalisms, such as constraint networks, can express "simple" decision problems, while others are designed to take into account uncertainties, unfeasible decisions, and utilities. Even in a single formalism, several variants are often proposed to model different types of uncertainty (probability, possibility...) or utility (additive or not). In this article, we introduce an algebraic graphical model that encompasses a large number of such formalisms: (1) we first adapt previous structures from Friedman, Chu and Halpern for representing uncertainty, utility, and expected utility in order to deal with generic forms of sequential decision making; (2) on these structures, we then introduce composite graphical models that express information via variables linked by "local" functions, thanks to conditional independence; (3) on these graphical models, we finally define a simple class of queries which can represent various scenarios in terms of observabilities and controllabilities. A natural decision-tree semantics for such queries is completed by an equivalent operational semantics, which induces generic algorithms. The proposed framework, called the Plausibility-Feasibility-Utility (PFU) framework, not only provides a better understanding of the links between existing formalisms, but it also covers yet unpublished frameworks (such as possibilistic influence diagrams) and unifies formalisms such as quantified boolean formulas and influence diagrams. Our backtrack and variable elimination generic algorithms are a first step towards unified algorithms.

In the frame of classical constraint satisfaction problems (CSPs), the backtrack tree search, combined with learning methods, presents a double advantage: for static solving, it improves the search speed by avoiding redundant explorations; for dynamic solving (after a slight change of the problem) it reuses the previous searches to build a new solution quickly. Backtrack reasoning concludes the rejection of certain combinatorial choices. Nogood Recording memorizes these choices in order to not reproduce. We aim to use Nogood Recording in the wider scope of the Valued CSP framework (VCSP) to enhance the branch and bound algorithm. Therefore, nogoods are used to increase the lower bound used by the branch and bound to prune the search. This issue leads to the definition of the "Valued Nogoods" and their use. This study focuses particularly on penalty and dynamic VCSPs which require special developments. However our results give an extension of the Nogood Recording to the general VCSP framework.

Many AI synthesis problems such as planning, scheduling or design may be encoded in a constraint satisfaction problem (CSP). A CSP is typically defined as the problem of finding any consistent labeling for a fixed set of variables satisfying all given constraints between these variables. However, for many real tasks, the set of constraints to consider may evolve because of the environment or because of user interactions. The problem considered here is the solution maintenance problem in such a dynamic CSP (DCSP). The authors propose a new class of constraint recording algorithms called Nogood Recording that may be used for solving both static and dynamic CSPs. It offers an interesting compromise, polynomially bounded in space, between an ATMS-like approach and the usual static constraint satisfaction algorithms.