Arrow Research search

Author name cluster

Pierre Régnier

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers
2 author rows

Possible papers

11

AIJ Journal 2021 Journal Article

A lightweight epistemic logic and its application to planning

  • Martin C. Cooper
  • Andreas Herzig
  • Faustine Maffre
  • Frédéric Maris
  • Elise Perrotin
  • Pierre Régnier

We study multiagent epistemic planning with a simple epistemic logic whose language is a restriction of that of standard epistemic logic. Its formulas are boolean combinations of observability atoms: sequences of ‘knowing whether’ operators followed by propositional variables. This compares favourably with other restricted languages where formulas are boolean combinations of epistemic literals: sequences of ‘knowing that’ epistemic operators and negations followed by propositional variables; or in other terms: epistemic formulas without conjunctions or disjunctions. The reason is that our language enables a richer theory of mind: we can express statements such as “I don't know whether p, but I know that you know whether p” which are important in communication and more generally in interaction and which cannot be expressed with epistemic literals. Going beyond previous work, we also introduce a ‘common knowledge whether’ operator. We show that satisfiability is nevertheless NP-complete. We then define simple epistemic planning tasks as generalisations of classical planning tasks: action descriptions have sets of observability atoms as add- and delete-lists, initial states are sets of observability atoms, and goals are boolean combinations of observability atoms. We show that simple epistemic planning tasks can be polynomially translated into classical planning tasks. It follows that checking solvability of simple epistemic planning tasks is PSpace-complete. We present some application examples such as the gossip problem and some experimental results and clarify the relationship with Dynamic Epistemic Logic-based planning.

Details DOI

IJCAI Conference 2020 Conference Paper

TouIST: a Friendly Language for Propositional Logic and More

  • Jorge Fernandez
  • Olivier Gasquet
  • Andreas Herzig
  • Dominique Longin
  • Emiliano Lorini
  • Frédéric Maris
  • Pierre Régnier

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.

PDF Details DOI

ECAI Conference 2016 Conference Paper

A Simple Account of Multi-Agent Epistemic Planning

  • Martin C. Cooper
  • Andreas Herzig
  • Faustine Maffre
  • Frederic Maris
  • Pierre Régnier

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.

Details

ECAI Conference 2016 Conference Paper

Simple Epistemic Planning: Generalised Gossiping

  • Martin C. Cooper
  • Andreas Herzig
  • Faustine Maffre
  • Frederic Maris
  • Pierre Régnier

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.

Details

TIME Conference 2013 Conference Paper

Relaxation of Temporal Planning Problems

  • Martin C. Cooper
  • Frederic Maris
  • Pierre Régnier

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.

Details

ICAPS Conference 2012 Conference Paper

Tractable Monotone Temporal Planning

  • Martin C. Cooper
  • Frederic Maris
  • Pierre Régnier

This paper describes a polynomially-solvable sub-problem of temporal planning. 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, difference constraints). Our class includes temporally-expressive problems, which we illustrate with an example of chemical process planning.

Details

TIME Conference 2010 Conference Paper

Solving Temporally-Cyclic Planning Problems

  • Martin C. Cooper
  • Frederic Maris
  • Pierre Régnier

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.

Details

TIME Conference 2008 Conference Paper

TLP-GP: Solving Temporally-Expressive Planning Problems

  • Frederic Maris
  • Pierre Régnier

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.

Details

AIJ Journal 2001 Journal Article

Least commitment in Graphplan

  • Michel Cayrol
  • Pierre Régnier
  • Vincent Vidal

Planners of the Graphplan family (Graphplan, IPP, STAN, …) are currently considered to be the most efficient ones on numerous planning domains. Their partially ordered plans can be represented as sequences of sets of actions. The sets of actions generated by Graphplan satisfy a strong independence property which allows one to manipulate each set as a whole. We present a detailed formal analysis that demonstrates that the independence criterion can be partially relaxed in order to produce valid plans in the sense of Graphplan. Indeed, two actions at a same level of the planning-graph do not need to be marked as mutually exclusive if there exists a possible ordering between them that respects a criterion of “authorization”, less constrained than the criterion of independence. The ordering between the actions can be set up after the plan has been generated, and the extraction of the solution plan needs an extra checking process that guarantees that an ordering can be found for actions considered simultaneously, at each level of the planning-graph. This study lead us to implement a modified Graphplan, LCGP (for “Least Committed GraphPlan”), which is still sound and complete and generally produces plans that have fewer levels than those of Graphplan (the same number in the worst cases). We present an experimental study which demonstrates that, in classical planning domains, LCGP solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN, …). In most cases, LCGP also outperforms the other planners.

Details DOI

ICAPS Conference 2000 Conference Paper

New Results about LCGP, a Least Committed GraphPlan

  • Michel Cayrol
  • Pierre Régnier
  • Vincent Vidal 0001

Planners from the family of Graphplan(Graphplan, IPP, STAN...)are presently considered as the most efficient ones on numerous planning domains. Their partially ordered plans can be represented as sequencesof sets of simultaneousactions. Usingthis representation and the criterion of independence, Graphplanconstrains the choice of actions in such sets. Wedemonstratethat this criterion can be partially relaxed in order to producevalid plans in the sense of Graphplan. Our planner LCGPneeds fewer levels than Graphplanto generate these plans (the same number in the worst cases). Then we present an experimentalstudy whichdemonstratesthat, in classical planning domains, LCGP"practically" solves more problems than planners from the family of Graphplan (Graphplan, IPP, STAN...). In most cases, these tests demonstrate the best performances of LCGP. Then, we present a domain-independent heuristic for variable and domain ordering. LCGPis thus improved using this heuristic, and comparedwith HSP-R, a very efficient non-optimal sequential planner, based on an heuristic backwardstate space search.

Details

AAAI Conference 1999 Conference Paper

Total Order Planning Is More Efficient than We Thought

  • Vincent Vidal
  • Pierre Régnier
  • IRIT
  • Paul Sabatier University

In this paper, we present VVPLAN, a planner based on a classical state space search algorithm. The language used for domain and problem representation is ADL (Pednault 1989). We have compared VVPLAN to UCPOP (Penberthy and Weld 1992)(Weld 1994), a planner that admits the same representation language. Our experiments prove that such an algorithm is often more efficient than a planner based on a search in the space of partial plans. This result is achieved as soon as we introduce in VVPLANs algorithm a loop test relating to previously visited states. In particular domains, VVPLAN can also outperform IPP (Koehler et al. 1997), which makes a planning graph analysis as GRAPHPLAN. We present here the details of our comparison with UCPOP, the results we obtain and our conclusions.

PDF Details