This work deals with logical formalization and problem solving using automated solvers. We present the automatic translator TouIST that provides a simple language to generate logical formulas from a problem description. Our tool allows us to model many static or dynamic combinatorial problems and to benefit from the regular improvements of SAT, QBF or SMT solvers in order to solve these problems efficiently. In particular, we show how to use TouIST to solve different classes of planning tasks in Artificial Intelligence.

A realistic model of multi-agent planning must allow us to formalize notions which are absent in classical planning, such as communication and knowledge. We investigate multi-agent planning based on a simple logic of knowledge that is grounded on the visibility of propositional variables. Using such a formal logic allows us to prove the existence of a plan given the description of the individual actions. We present an encoding of multi-agent planning problems expressed in this logic into the standard planning language PDDL. The solvability of a planning task is reduced to a model checking problem in a dynamic extension of our logic, proving its complexity. Feeding the resulting problem into a PDDL planner provides a provably correct plan for the original multi-agent planning problem. We apply our method on several examples such as the gossip problem.

The gossip problem, in which information (secrets) must be shared among a certain number of agents using the minimum number of calls, is of interest in the conception of communication networks and protocols. We extend the gossip problem to arbitrary epistemic depths. For example, we may require not only that all agents know all secrets but also that all agents know that all agents know all secrets. We give optimal protocols for the generalised gossip problem, in the case of two-way communications, one-way communications and parallel communication. In the presence of negative goals testing the existence of a successful protocol is NP-complete.

This paper describes a polynomially-solvable class of temporal planning problems. Polynomiality follows from two assumptions. Firstly, by supposing that each sub-goal fluent can be established by at most one action, we can quickly determine which actions are necessary in any plan. Secondly, the monotonicity of sub-goal fluents allows us to express planning as an instance of STP≠ (Simple Temporal Problem with difference constraints). This class includes temporally-expressive problems requiring the concurrent execution of actions, with potential applications in the chemical, pharmaceutical and construction industries. We also show that any (temporal) planning problem has a monotone relaxation which can lead to the polynomial-time detection of its unsolvability in certain cases. Indeed we show that our relaxation is orthogonal to relaxations based on the ignore-deletes approach used in classical planning since it preserves deletes and can also exploit temporal information.

Relaxation is ubiquitous in the practical resolution of combinatorial problems. If a valid relaxation of an instance has no solution then the original instance has no solution. A tractable relaxation can be built and solved in polynomial time. The most obvious application is the efficient detection of certain unsolvable instances. We review existing relaxation techniques in temporal planning and propose an alternative relaxation inspired by a tractable class of temporal planning problems. Our approach is orthogonal to relaxations based on the ignore-all-deletes approach used in non-temporal planning. We show that our relaxation can even be applied to non-temporal problems, and can also be used to extend a tractable class of temporal planning problems.

To correctly model certain real‐world planning problems, it is essential to take into account time. This is the case for problems requiring the concurrent execution of actions (known as temporally expressive problems). In this paper, we define and study the notion of temporally cyclic problems, that is problems involving sets of cyclically dependent actions. We characterize those temporal planning languages, which can express temporally cyclic problems. We also present a polynomial‐time algorithm, which transforms a temporally cyclic problem into an equivalent acyclic problem. Applying our transformation allows any temporal planner to solve temporally cyclic problems without explicitly managing cyclicity. We first present our results for temporal PDDL (Planning Domain Description Language) 2.1 and then extend them to a language that allows conditions over arbitrary intervals and effects at arbitrary instants.

Cost-optimal planning, in which the aim is to minimise the sum of costs of actions, is a challenging problem due to its computational complexity. A linear program derived from a relaxation which ignores the constraints on the ordering of actions can be used to obtain a lower bound on the cost of a solution-plan. We show that the dual of this linear program provides a transformation of the problem into an equivalent optimal planning problem in which the cost of the goal-achieving action is exactly equal to this lower bound. This transformation is of universal utility since it can be applied as a preprocessing technique and can thus be combined with any of the diverse techniques which have been developed for optimal planning.

An important aspect of any automatic planner is the language in which the user expresses problem instances. A rich language is an advantage for the user, whereas a simple language is an advantage for the programmer who must write a program to solve all planning problems expressible in the language. Considering the temporal planning language PDDL 2.1 as a low-level language, we show how to automatically compile a much richer language into PDDL 2.1. The worst-case complexity of this transformation is quadratic. Our high-level language allows the user to declare time-points and impose simple temporal constraints between them. Conditions and effects can be imposed at time-points, over intervals and over sliding intervals within fixed intervals. Non-instantaneous transitions can also be modelled.

In order to correctly model certain real-world planning problems, it is essential to take into account time. This is the case for problems requiring the concurrent execution of actions (known as temporally-expressive problems). However, we show in this paper that certain existing planners which solve this type of problem are, in fact, incomplete. They cannot guarantee to find a solution to a problem involving sets of cyclically-dependent actions (which we call temporally-cyclic problems). We characterize those temporal planning languages which can express temporally-cyclic problems. We also present a polynomial-time algorithm which transforms a temporally-cyclic problem into an equivalent acyclic problem. Applying our transformation restores the completeness of these temporal planners.

One of the major challenges for planning is to take into account the time dimension. In this paper, we present a simple approach to deal with temporally expressive problems, that is problems for which all possible solutions require concurrency of actions. Our planner TLP-GP mixes some of the advantages of GRAPHPLAN search with a constraint-based and flexible temporal formalism. Its language is consistent with PDDL 2.1 and extends its expressivity. Experimental trials on new temporally expressive benchmarks show the efficiency of our approach and demonstrate the practical possibility of solving temporally expressive problems which up until now were unsolvable by existing techniques.

This article describes an algorithm which solves temporally-expressive planning problems, that is problems for which all possible solutions require concurrency of actions. The planner TLP-GP which implements this algorithm constructs a simplified planning graph until the goals are attained, as in classic atemporal planners. It then establishes temporal constraints between actions and searches backward for a solution-plan in the planning graph using a disjunctive temporal constraint solver. If the search fails, the graph is extended to the next level and the search is restarted. This method can solve problems in a language whose expressivity is greater than PDDL 2.1. Preconditions can be required and effects can take place on any temporal interval relative to the start-time of an action. This algorithm can also take into account, in a very natural way, exogenous events as well as temporally extended goals. We also propose several different means of extending expressivity even further. TLP-GP is complete for the temporally-expressive sublanguages of PDDL 2.1.We compared our planner with two state-of-the-art temporally-expressive planners such as LPGP and VHPOP. These experimental trials not only show the efficiency of our approach but also demonstrate the practical possibility of solving temporally expressive problems which up until now were unsolvable by existing techniques.