Lamia Belouaer

Maroua Bouzid

Malek Mouhoub

Extending Temporal Causal Graphs For Diagnosis Problems

Introduction

Abductive diagnosis [START_REF] Brusoni | A spectrum of definitions for temporal model-based diagnosis[END_REF]) consists in finding explanations for given observations by using rules of inference based on the causal dependences of the system. Time is important for abductive diagnosis [START_REF] Hamscher | Diagnosing circuit with state : an inherently underconstrained problem[END_REF], [START_REF] Hamscher | Readings in Model-Based Diagnosis[END_REF]. There are few works in litterature handling temporal diagnosis [START_REF] Kautz | Temporal reasoning[END_REF]. They differ in the expressiveness of the temporal knowledge.

We propose a new approach for Temporal Diagnosis Problems. This approach is an extension of Bouzid and Ligeza's method for temporal diagnosis problems. In this latter work, the authors define a Temporal Causal Graph (TCG) where time delays are expressed as temporal instants. We extend the TCG by including two quantitative relations in order to handle temporal intervals. We call ExTCG this new model. Solving a temporal diagnosis problem represented by the ExTCG consists of finding all possible explanations. It is performed using a backtrack search algorithm.

Extended Temporal Causal Graph

The language of temporal representation

We suppose that we are in a frame where time is linear and discrete. The ontology of time considers both the instant and the interval. First, we extend the TCG by introducing the notion of episode. Definition 1. An episode is defined by a pair (s, i) where s is a symptom. i is an interval or an instant. A symptom represents some phenomenon reflecting an occurence of partial characteristic of the system.

We are interested in the truth value of s over time. An episode can have dates of beginning noted start date or of end noted end date. The diagnosis is based on the analysis of several observations spaced out in a unpredictable way in time.

Relations

We keep the causal relation and the logical relations ({AN D, OR, N OT }) defined in [START_REF] Bouzid | Temporal Causal Abduction[END_REF].

Copyright c 2009, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

Temporal relations. R T = {r ql (∂t) | r ql ∈ R QL }, where ∂t is a positif integer indicating the delay and R QL the set of two temporal relations (af ter end, af ter start). af ter end represents that the effect is after the end of the cause. af ter start represents that the effect is after the beginning of the cause. These relations are transformed into equations and inequalities allowing to refer to an instant or to locate two episodes one to another. In a more precise way; we have e, c 1 and c 2 three episodes. If the relation is af ter start with a delay d 1 between c 1 and e then start time(c 1 ) = start time(e)d 1 . If the relation is af ter end with a delay d 2 between c 2 and e then end time(c 2 ) = start time(e)d 2 .

Let us note by R the set of relations proposed in our ap-

proach. R = {(r t , r c ) | r t ∈ R T , r c ∈ R C } where:
R C defines all the causal relations and R T defines all the temporal relations.

Extension of a TCG

An extended temporal causal graph noted ExTCG is a TCG where nodes are episodes, and edges are the relations defined above. Definition 2. An Extended Temporal Causal Graph (ExTCG) is a structure G = (E, F, R), where: Solving a Temporal Diagnostic Problem consists of finding all the episodes explaining the given observations and placing them in time.

• E : set of episodes • F = {(n, f, [n 1 , . . . , n k ])}
Definition 4. Let us consider a temporal diagnostic problem P = {ExT CG, OBS}. A solution S to P is defined by a set of pairs of initial nodes: {(e 1 , i e1 ), . . . , (e n , i en )}, where i ej can be an interval or an instant, such that:

ExTCG ∪ S |= OBS and S is consistent. To solve a temporal abductif diagnostic problem, we propose an algorithm of temporal propagation in the ExTCG, in order to find all possible explanations. We proceed in the following two steps.

Step 1 : Abduction and Propagation

For the sake of the presented approach abduction is considered as a backward search procedure.

It allows to generate all sets of explanations as well as the equations and inequalites corresponding to temporal information. A solution, noted sol is a couple (explanation, {equations/inequalities}). Let us note by Sol solve , all the solutions sol generated in this step. Given an observation o, we visit the ExTCG using a depthfirst strategy, moving backward from o to non abductibles episodes. In every step of abduction, we replace a node by its possible cause. Every temporal relation is converted into equation and inequality. In a more formal way :

• At abductive step k, o is an AND node, caused by {c 1 , c 2 , . . . , c n } so : for each c i , we convert r t (r t temporal relation between c i and o) in equations and ineqalities, and o is replaced by {c 1 , c 2 , . . . , c n }. • At abductive step k, o is an OR node, caused by {c 1 , c 2 , . . . , c n } so : we select one by one the causes of o. For the number of causes, we duplicate the solution sol for every c i , so we have one sol ci by node c i . We replace o by every cause c i and we do the same thing. Finally, we add every sol ci to Sol solve . • At abductive step k, o is a NOT node, caused by c. The steps are the same as for the link AND. Furthermore, it is necessary to modify the truth value of c; if the truth value of o is true (resp. false) then we set c to false (resp. true). If in a step one node is not abductible, it is considered to be explaining o. It will be added to the explanation corresponding to sol. This step generates the set Sol solve .

Step 2 : Resolution This step consists in solving equations and inequalities generated in the first step. The intention is to locate the explanation temporally. We consider these equations and inequalities as numeric temporal constraints. For this reason we use Simple Temporal Problem (STP) [START_REF] Planken | P 3 c : A new algorithm for the simple temporal problem[END_REF]. To see how an STP can be used to find the ansewer to our question, we first consider :

• the set of temporal variables V = {x 1 , . . . , x 2n } representing the start and the end of n episodes (x i =start date or end date), • the domain : N + , • and the set C of eqautions and inequalities.

Then we define the relation of precedence between two episodes E 1 and E 2 as :

• start date(E 2 ) -start date(E 1 ) ∈ [d , +∞[ and, • start date(E 2 ) -end date(E 1 ) ∈ [d , +∞[,
where d is a positif integer indicating the delay. We use STP in order to verify the coherence of the given temporal information and to solve equations/inequalities.

To solve the formed STPs we use the P 3 C algorihtm presented in [START_REF] Planken | P 3 c : A new algorithm for the simple temporal problem[END_REF].

Conclusion and Future Work

We have extended the TCG [START_REF] Bouzid | Temporal Causal Abduction[END_REF] by including two qualitative relations in order to manipulate time intervals.

We have developed search algorithms respectively for solving the ExTCG. These algorithms consists in a backward search by propagating temporal information. Temporal information is considered as constraints. Thus, we formalize a set of constraints associated to each possible explanation as an STP. To solve an STP we use the P 3 C algorithm.

One possible improvement to this work is to integrate more powerfull models into the ExTCG in order to manipulate the causality as weights expressing preferences. These models can be qualitative such as CP-nets [START_REF] Boutilier | CP-nets: A tool for representing and reasoning with conditional ceteris paribus preference statements[END_REF] or quantitative such as c-semiring [START_REF] Bistarelli | Semiring-Based Constraint Satisfaction and Optimization[END_REF].

  Definition 3. A Temporal diagnostic problem P is defined by an ExTCG and a set of observations OBS as follows: {ExT CG, OBS = ((o 1 , i o1 ), . . . , (o n , i on ))}, where the ExTCG represents the theoretical domain and OBS the set of observations o k at the instants i o k .

	Solving Method
	A temporal diagnosis problem is defined by an ExTCG and
	a set of observations.

denotes the set of logical connections such that f ∈ {AN D, OR, N OT }, n 1 , . . . , n k are the input nodes and n the output node.

• R : set of causal and temporal relations between episodes.


Lamia Belouaer

Maroua Bouzid

Abdel-Illah Mouaddib

SPATIAL KNOWLEDGE IN PLANNING LANGUAGE

Keywords: Spatial Representation and Reasoning, Spatial Ontolgy, Fuzzy Information, Rules, Task and Path Planning

This paper describes the integration of spatial knowledge in a planning problem. For example, in the case of evacuation problem of a building during a fire, we must know the fastest paths (the shortest, least congested, . . . ). Such applications require spatial knowledge to perform spatial planning. This planning taste becomes more complex when knowledge are shared by many actors. Indeed, our interest concerns collaborative work between agents, in particular the case of human-robot interaction. In such contexts, considering the space information in planning, we use a spatial ontology called SpaceOntology which handles different representations and abstraction levels of spatial information. We integrate this ontology in the planning by defining a formal language planning: Spatial-PDDL. Spatial-PDDL combines PDDL concepts with this ontology. Also, we distinguish between three types of actions: non spatial, spatial and navigation actions.

INTRODUCTION

In this paper, we focus on the spatial knowledge management in planning problem where the tasks consider spatial and non-spatial representations. Such problems could be met in human-robot interaction. Most typical scenarios include a human instructing a robot to perform some actions on some objects in the environment. To achieve this task, the human and the robot establish a similar description of the concerned environment. This requires not only that the scene descriptions created by the robot and the human match but also needs a system which can successfully mediate between these descriptions. However, the space representation from human's and robot's points of view is not the same. Indeed, the robot's spatial representation is numeric and the human's spatial representation uses natural language. The natural language employs incomplete and fuzzy information about space (for example, the book is near the bottle). Thus, we propose to find a representation for planning problems that can be used by robots to communicate with humans, analyze scenes and build maps.

To do this, we use an ontology called SpaceOntology [START_REF] Belouaer | Ontology based spatial planning for human-robot interaction[END_REF]. It permits a knowl-edge representation for modeling space, spatial relations and fuzzy information. This ontology allows us: a complex spatial description, an easy management of various spatial aspects, an easily extensible structure and to infer spatial information. It provides a structured knowledge about the environment to explore in planning process.

Planning process in artificial intelligence is decision making about the actions to be taken. As input, this process takes a planning problem (initial state and goal state) returns a plan (a sequence of ordered actions) to solve this problem (achieve the goal state from the initial state). To express spatial knowledge in planning process, we need a formal language. We use language PDDL [START_REF] Ghallab | PDDL the planning domain definition language[END_REF] (Planning Domain Definition Language).

We propose a planner incorporating spatial representation and reasoning by integrating SpaceOntology. SpaceOntology in the planning, is not used for verification or control, but as information needed for planning. We adapt the PDDL actions and concepts definition to express spatial information if it is necessary. In other words, we extend PDDL to spatial knowledge: Spatial-PDDL.

The rest of paper is organized as follows. Sec-tion 2 gives an overview about different approaches to solve planning problems taking spatial knowledge into account. Section 3 describes the spatial representation and reasoning. Section 4 describes the planning process with spatial knowledge and its impact on complexity. Section 5 presents some results. Finally, we conclude in Section 6.

RELATED WORK

Different techniques for spatial representation and reasoning have been proposed. Most are based on constraints, logical and algebraic approaches [START_REF] Balbiani | A new tractable subclass of the rectangle algebra[END_REF]. However, these approaches can not manage numeric, topological and imprecise knowledge at the same time. In planning, we need to combine these knowledge. Thus, we must use an unified framework to cover large classes of problems and to give rise to instantiations adapted to each particular application. Ontologies appear as an appropriate tool toward this aim. Spatial ontologies can be found in some fields such as Virtual Reality [START_REF] Dasiopoulou | Knowledge-assisted semantic video object detection[END_REF], Robotics [START_REF] Dominey | Building an adaptive spoken language interface for perceptually grounded human-robot interaction[END_REF], etc. All these ontologies are focused on the representation of spatial concepts according to the application domains. A major weakness of usual ontological technologies is their inability to represent and to reason with imprecision. An interesting work presented in [START_REF] Hudelot | Fuzzy spatial relation ontology for image interpretation[END_REF] overcomes this limit.

The concept of exploiting ontology to represent spatial knowledge in planning has been explored. [START_REF] Bouguerra | Monitoring the execution of robot plans using semantic knowledge[END_REF] describes a new approach for monitoring the execution of plans where spatial knowledge is defined by an ontology called LOOM. This ontology permits a region classification and verifies the plan execution. However, it does not describe spatial relations and it is not used in planning.

To express spatial knowledge in planning process, we use PDDL [START_REF] Ghallab | PDDL the planning domain definition language[END_REF]. The first version of PDDL is extended to consider several aspects in a planning problem definition that improve the quality of the solution, such as the temporal dimension [START_REF] Fox | PDDL2. 1: An extension to PDDL for expressing temporal planning domains[END_REF]. Despite the importance of the spatial dimension in planning problem, PDDL with spatial definition is not yet integrated.

Our main contribution is the extension of PDDL to spatial knowledge: Spatial-PDDL. To do this, we use SpaceOntology that considers several spatial knowledge aspects; the space hierarchy, spatial relations (numeric, topological and fuzzy).

SPATIAL REPRESENTATION AND REASONING

In the following, we present SpaceOntology [START_REF] Belouaer | Ontology based spatial planning for human-robot interaction[END_REF], a framework for spatial representation and reasoning.

Spatial Representation

We opted for OWL 1 DL 2 [START_REF] Baader | The description logic handbook: theory, implementation, and applications[END_REF] as a formal language 3 . An important characteristic of DL is its expressivity and its capability of inferring knowledge from the known information. A spatial entity is described by two concepts Regions and Space. The concept Space (Space⊑ Thing) is used to model space: the name of places, the hierarchical level, the boundaries definition, etc. It represents a global environment (a country, a city, a building, . . . ). The concept Regions (Regions⊑ Space) is a sub-space included in a given space. A region is itself considered as a space that can be decomposed into different sub-regions. From a geometric point of view, a region rg is defined by the smallest rectangle rect corresponding to its axis-aligned bounding rectangles. These concepts include some attributes. The hierarchical space organization has an impact on the distance evaluation. Indeed, the distance of 10 meters in a city is considered as close, however in a corridor this distance is considered as far. Each region has the attributes alpha and beta depending on the scale of its level. These two parameters evaluate the distance between two spatial objects [START_REF] Belouaer | Ontology based spatial planning for human-robot interaction[END_REF]

Regions

(section 3.2.3).
A spatial relation is defined by the concept SpatialRelations (SpatialRelations⊑ Thing) which includes TopologicalRelations and DistanceRelations.

A spatial relation is a concept on its own.

A Topological relation 1 Web Ontology Language 2 Description Logics 3 All notations used here are defined in the DL. (TopologicalRelations) is an ABLR relation [START_REF] Laborie | A spatial algebra for multimedia document adaptation[END_REF]. This relation is a couple r X , r Y , where:

r X ∈ {L, O L ,C x , I x , O R , R} and r Y ∈ {A, O A ,C y , I y , O B , B}.
A Distance relation (DistanceRelations) can be an Euclidean distance (NumericDistance) between the symmetry points of two rectangles representing two regions (r referent object and ε target object) noted d(ε, r) (in R + ) or fuzzy distance (FuzzyDistance) evaluating a distance between the symmetry points of two rectangles representing two regions. A fuzzy distance is defined by four linguistic variables: close to, close enough, far enough and far.

To define a spatial relation between spatial entities, we use the concept HasRelation. This concept links with a spatial relation between a reference region and one or more target regions (Example 1).

There are several relations (or predicates) to link these concepts to provide a spatial semantic. For example to express a hierarchical relation between two regions, we consider the links:

• consistsOf: Space ⊑ Thing ⊓ ∃ consistsOf.Regions ⊓ 1 consistsOf • isPartOf: Regions ⊑ Space ⊓ ∃ isPartOf.Space ⊓ 1 IsPartOf
Example 1 Let us consider a part of a floor with two offices (O1, O2) and a hall (H1) (Fig. 3). Figure 2 models4 the space domain defined in Figure 3 by using SpaceOntology. We consider that each spatial entity is a Regions concept. Then, spatial relation between these different spatial entities are described by combining SpatialRelations and HasRelation.

In Example 1, the relation1 is an instance of the concept HasRelation describing the topological relation between offices O2 and O1:

relation1:HasRelation ⊓ ∃ concernsSpatialRelation.inside below ⊓ ∃ hasReferent.O1 ⊓ ∃ hasTarget.O2
The relation inside below is defined as follow:

inside below:TopologicalRelations ⊓ ∃ isAnHorizontalRelation.I x ⊓ ∃ isAVerticalRelation.B

Spatial Reasoning

The reasoning methods infer spatial information in order to enrich the description of the environment and/or to manage the lack of information.

Spatial Hierarchical Reasoning

To express a hierarchical relation between two regions (for example, a region includes another region, or a region is in another one), we use the predicates consistsOf and isPartOf. The predicate isPartOf is the inverse of the relation consistsOf. These relations are transitive. The transitivity rules for the predicate consistsOf and isPartOf are: To consider a space as a whole with the different abstraction levels is not always necessary and makes spatial reasoning very expensive. The hierarchical organization can simplify this reasoning, depending on abstraction level. To do so, we exploit the two predicates: consistsOf and isPartOf in order to define the function hierarchical interest zone denoted Z l (r). This function Z l (r) defines an interest zone (An interest zone defines a region in a considered space to be reached and/or localized) of a region r in the hierarchical level l. To compute this function we query SpaceOntology (details in Section 4.2.1).

consistsOf(r 1,r 2) ⊓ consistsOf(r 2,r 3) -→ consistsOf(r 1,r 3) isPartOf(r 1,r 2) ⊓ isPartOf(r 2,r 3) -→ isPartOf(

Spatial Reasoning Based on Topological Relations

In order to enrich SpaceOntology with new knowledge, we consider two different aggregations of spatial relations: combination ⊕ and composition ⊗. The composition mechanism The composition mechanism infers new spatial information. Let us consider three regions defined by three rectangles rect1, rect2 and rect3 (Fig. 5). The idea is to infer which relation R3 links between rect1 and rect3 where R1 is a relation between rect1 and rect2 and R2 is a relation between rect2 and rect3. The topological relation R 3 is defined by

R3 = R1 ⊗ R2, then rx3, ry3 = rx1, ry1 ⊗ rx2, ry2 (1) = rx1 ⊗ rx2, ry1 ⊗ ry2 (2)
The composition results of (rx1 ⊗ rx2) and (ry1 ⊗ ry2) are given by the composition table of rectangle algebra by preserving the directionality property as defined in ABLR. Formally, we define in SpaceOntolgy a set of rules reflecting the composition table. The composition mechanism returns a disjunction of possible relations between two rectangles. However, not all inferred relations are valid. To reduce the number of possible relations between two rectangles, by keeping only the valid relations, we proceed as follows. First, we select the necessary knowledge for the inference and we formalize it as a constraint network called spatial relation network (Fig. 5). Then, we apply the required rules, and we complete this network. Thus, a network is defined by :

• V a set of nodes representing rectangles describing regions,

• C a set of constraints representing topological relations. An arc is labeled by a topological relation (constraint) between two rectangles connected to this arc. Arcs labeled with disjunctions are arcs that are inferred by composition.

The idea is to remove all spatial relations does not ensure the consistency of the network. Thus, we aim to establish arc consistency in this network. We produce an equivalent network to the first one which checking the arc consistency property (Def. 1).

Definition 1 A network is arc consistent if all its arcs are arc consistent Thus, the network produced is arc-consistent, i.e. it does not contain topological relations does not ensure the arc consistency of the network. Practically, for the rules application, we use the Pellet inference engine [START_REF] Sirin | Pellet: A practical owl-dl reasoner[END_REF], and for the verification of the arc consistency, we rely on the MAC algorithm [START_REF] Prosser | Mac-cbj: maintaining arc consistency with con ict-directed backjumping[END_REF].

Example 3 Let us consider the following problem, a robot is in the office o2. Its mission is to go to the office o3 . However, it has no spatial information enabling it to define its trajectory between o2 and o3. We have a set of spatial information, depicted in Figure 6: the office o3 is right and is overlaps above the office o1: o3 R, O A o1. Also, in Figure 3, the office o2 is inside and is below of the office o1: o2 I x , B o1.

Our goal is to found the spatial relation between the offices o3 and o2. First, we apply a symmetry rule, then, o1 L, O B o3 is the inverse of o3 R, O A o1. Second, we apply composition rule between o2 I x , B o1 and o1 L, O B o3 (Fig. 7).

isATopologicalRelation(?t relation1) ⊓ isAnHorizontalRelation(?t relation1,"I X") ⊓ isAVerticalRelation(?t relation1,"B") Thus, from this information we can plan our trajectory to reach the office o3 without considering the entire second floor but only the northeastern part of the floor from the office o2. The information o2 L, B o3 is added in SpaceOntology.

⊓ isATopologicalRelation(?t relation2) ⊓ isAnHorizontalRelation(?t relation2,"L") ⊓ isAVerticalRelation(?t relation2,"O B") -→ [isATopologicalRelation(?t relation3) ⊓ isAnHorizontalRelation(?t relation3,"L") ⊓ isAVerticalRelation(?t relation3,"B")]

Spatial Fuzzy Reasoning

In this work, the fuzzy representation concerns only distance relations. Indeed, we use linguistic variables to evaluate a distance (close, close enough, far enough and far). We aim to give a numeric representation to each variable and vice versa. SpaceOntology allows this translation, by defining some rules based on functions N α,β and F α,β [START_REF] Schockaert | Reasoning about fuzzy temporal and spatial information from the web[END_REF]. The function N (α,β) (p, q) (resp. F (α,β) (p, q)) measures the degree with which p is close to q (resp. the degree with which p is far from q) (α, β > 0).

  0 1 d(p,q) N  ,   p , q F  ,   p , q Figure 9: Distance evaluation. (1) if d ∈ [0, α] , then d is close , (2) if d ∈]α, α + β 2 ] then d is close enough, (3) if d ∈]α + β 2 , α + β] then d is far enough, (4) if d ∈]α + β, +∞[ then d is far.
Figure 9 illustrates the translation of a distance from a numeric definition to symbolic definition and vice versa. The parameters α and β allow us to evaluate the numeric distance. These parameters depend on the current region. Figure 8

SPACEONTOLOGY BASED PLANNING

Now, we explore the potential uses of spatial representation and reasoning offered by SpaceOntology in planning. Our goal is to propose a planner incorporating spatial representation and reasoning: Spatial Planner (Fig. 10). As input, the spatial planner (Fig. 10) takes a planning problem defined by: • a domain is a set of actions. Each action specifies preconditions that must be present in the current state so it can be applied, and effects on the current state, • a description of the initial state of a world,

• a description of a goal.

As output, it generates a plan: a sequence of actions.

This planner consists of a task planner and a path planner and SpaceOntology. The task planner's aim is to define the sequence of actions which will be executed to achieve the goals of the entry problem. Path planner defines possible paths to reach the execution of tasks to accomplish. It finds a path between two positions (fuzzy positions or well defined positions). SpaceOntology manages spatial information about the space.

There is a communication between these components (Fig. 10). This communication is in the form of queries/answers. These one is in charge of planners which at some steps require spatial preconditions to be satisfied. To this end, it sends a query to SpaceOntology to answer to the request.

Example 4 (Study Case) A team (human and robot) is in the office O B 1

11 in the first floor of the building B 1 (the human position is h) (Fig. 11). The human asks the robot to pick up a book (b) located in the office (o) close to the coffee machine. This machine is on the second floor of the building B 6 (Fig. 11). 11 ,o)). The office o is defined as the office close to the coffee machine, i.e. how to evaluate the relation close to the coffee machine? (2) how to move between different areas to accomplish actions? i.e to define the robot's navigation during and between each action; for example, finding a path between the current position o and the human position h. (3) how to order the action execution with respect to navigation?

To solve this problem, we use the Spatial Planner (Fig. 10). This planner requires different types of knowledge encoded in Spatial-PDDL. It is an extension of PDDL with spatial information made by the communication between planners (task and path planner) and SpaceOntology (Fig. 10). We focus here on Spatial-PDDL definition and the planner operation.

From PDDL to Spatial-PDDL

We extend PDDL with spatial knowledge using SpaceOntology in order to improve the expressiveness of the planning language. Formally, SpaceOntology is a triple (Φ, R, I), where Φ is a set of concepts, R is a set of relations (or predicates) between concepts and I is a set of instances which depends on the described environment.

Our planner takes three inputs (Fig. 10). (1) An initial state S 0 , (2) a goal state S G ; these states describe a set of objects (O) by specifying their type (T ) and relations between them (Π), (3) A set of actions (A) described in a domain (D). We extend PDDL language with SpaceOntology.

Notations

The main extensions are summarized in Table 1. A concept, a relation or an instance always has a prefix. [START_REF] Dou | The Formal Syntax and Semantics of Web-PDDL[END_REF] expresses that the domain is extended by an ontology, where the notion of " : extends" and "@ns1 : " were introduced. Each concept in SpaceOntology defines a spatial type. All the concepts defined in SpaceOntology (Φ) are introduced and exploited for extending PDDL (Table. 1).

Notions PDDL Extend PDDL with SpaceOntology Predicate Π Π ← Π ∪ R Type T T ← T ∪ Φ Domain D use
A predicate π (π ∈ Π) expresses a relation. All the relations (R) defined in SpaceOntology are introduced and exploited for extending PDDL (Table. 1).

Our contributions concerning the action definition consist of the extension of geometric preconditions/effects in order to take the different spatial representations (topological and fuzzy information) into account. In addition, it consists of the definition of the spatial fuzzy actions (Def. 2).

Definition 2 (A Spatial Fuzzy Action) A spatial fuzzy action a is defined by a = ( at , pr, q, e) , where : at, pr and e are respectively parameters for the action, preconditions, effects as defined in the extended action [START_REF] Guitton | Architecture hybride pour la planification d'actions et de dplacemen[END_REF] and q is a set of queries.

Example 5 The semantic of the action take (Fig. 13) is: the robot r takes the book b located in the office defined in a fuzzy way ?o. The office ?o is defined in Spatial-PDDL as a query variable [START_REF] Dou | The Formal Syntax and Semantics of Web-PDDL[END_REF]. ?rel -SpatialRelations ?hr -HasRelation) (and(@ns:isPartOf ?o Z Level(CM)-1 (CM))

(@ns:hasTarget ?hr ?o)(@ns:hasReferent ?hr CM) (@ns:concernsRelation ?hr ?rel) (if(instanceOf ?rel NumericDistance) (and(owl:DatatypeProperty rdf:ID="α" ?α Z Level(CM) (CM)) (owl:DatatypeProperty rdf:ID="β" ?β Z Level(CM) (CM)) (bounded-int owl:DatatypeProperty rdf:ID="distance" ?α (?α+ ?β)))) (if(instanceOf ?rel FuzzyDistance) (= ?rel "close_to"))))) (At r pr)(@ns:isPartOf pr ?o) (bounded-int distance(pr r. To delimit this region, we query SpaceOntology (details in Section 4.2.1). The fuzzy relation close can be described in a numeric way. So, we seek an office satisfying the fuzzy relation close by translating it in a numerical representation [START_REF] Belouaer | Ontology based spatial planning for human-robot interaction[END_REF]. Moreover, the action execution requires that the precondition (At r p r ) is satisfied. However, the satisfaction of this precondition requires the definition of the position p r . This position is defined as follows. First, it must be in the office ?o. Then, it must allow us to reach the target; the book. This requires that the robot is at a position p r close to the book. The evaluation of this distance is made by the function bounded-int. Also, there are two functions like frontOf and sameLevel which must be satisfied in order to grab the book.

Integrating SpaceOntology in PDDL:

Spatial-PDDL

We translate any spatial knowledge described in SpaceOntology to the domain and problem definitions in PDDL. SpaceOntology has an open world assumption and PDDL a closed one. To overcome this difficulty, the translation concerns only known types (Example 6).

Example 6 (Spatial Type and Predicate Extension) Figure 14 show a translation of an extract from SpaceOntology to PDDL in order to define Spatial-PDDL.

<owl:DatatypeProperty rdf:ID="labelhasrelation"> <rdfs:domain rdf:resource="#HasRelation"/> <rdfs:range rdf:resource="http://www.w3.org/2001/XMLSchema#string"/> <rdf:type rdf:resource="http://www.w3.org/2002/07/owl#FunctionalProperty"/> </owl:DatatypeProperty> (:spatial-predicates (@sponto:labelhasrelation hasrel -@sponto:HasRelation str -@xsd:string) (:spatial-axioms (forall (hasrel -@sponto:HasRelation str -@xsd:string str1 -@xsd:string) (if(and(@sponto:labelhasrelation hasrel str) (@sponto:labelhasrelation hasrel str1)) (= str str1))) ) A spatial relation in SpaceOntology is described by the concept HasRelation. This concept connects two regions by a spatial relation. Each relation instantiating this concept is identified by a label (labelhasrelation). This label is defined as a predicate in Spatial-PDDL (Fig. 14). The axioms concerning (Fig. 14) this predicate express that each label corresponds to a single instantiation of the concept HasRelation.

Spatial Predicates SpaceOntology Relations

Our model requires as an input : (1) a planning domain describes each action of a system in Spatial-PDDL, (2) a planning problem describing the initial state and goals in Spatial-PDDL, (3) SpaceOntology gives spatial description of space, and (4) some required information.

Definition 3 (A Domain) A planning domain D = (A, Π), where A = {a 1 , a 2 , . . . , a n } a set of actions, where a i is an action and Π set of relations between objects O. Definition 4 (A Spatial Planning Problem) A Spatial Planning Problem P = < O, S 0 , S G >, where O is a set of spatial and non-spatial objects, S 0 is an initial state that could be associated to fuzzy position and S G is the goal state that could be associated to fuzzy position.

In Figure 15 Note by "?α" and "?β" query variables to determine the α and β of the current level. The relation owl:DatatypeProperty rdf:ID="β" identifies for a given region the β (Fig. 15).

The fuzzy spatial information the office close to the coffee machine is defined by a query variable: "?o". There are some functions. (distance?ip?t pposition) used to compute the Euclidean distance between two positions.

(maxhdistance) (resp. (minhdistance)) indicates the maximum distance (resp. minimum) from which the interaction with humans can not be executed. path (Fig. 16) checks the existence of a path and computes it.

Communication Between Components

The planner has three components: task planner, path planner and SpaceOntology. The communication between them is in form of request/response. Planners (task and path) formulate queries to spatial ontology. They are encapsulated in the preconditions of the actions or they are directly in the problem definition.

In this section, we start by specifying the types of queries necessary for the planner function. Then, we describe the operation.

Requests for SpaceOntology

Several types of queries that are needed for the system operation. We can classify them into three categories: Adjacency query, Proximity Query and Hierarchical Interest Zone Query Adjacency query We assume that each region is adjacent to its neighbors with access points (doors, intersection of corridors, . . . ) called gates. A gate allows transitions between adjacent regions (in the same hierarchical level or in different hierarchical levels). A gate allows us to connect more than two regions.

Two regions are adjacent if there is a/or a set of transition between these two regions. Two types of adjacency: direct adjacency (i.e, the longer of the path between these two regions is equal to 1 (number of gates), of course several possibilities may exist, this represents a multiple choice of paths) and indirect adjacency (i.e, the longer of the path between these two regions is more than 1 (number of gates))

To extract the gates between regions or neighbors for a given region, we use adjacency query to SpaceOntology. This request is used to return the area of interest for the region rg level hierarchical level.

Spatial Planning Process

During the selection of these actions, the planner asks the satisfaction of these preconditions using SpaceOntology. Then, it calculates the required displacements and returns an answer to the result thereof. If the navigation is possible so action can be executed. Otherwise another action must be found to achieve the mission. The execution of the action take the book (Fig. 13) requires that the robot is in the office close to the coffee machine (in which the book is). However, the robot is in another office : O B1 11 . Thus, a navigation between the current position and target position is required. The target position is defined in a fuzzy way. Formally, we assume that the general planning problem includes a fuzzy path planning problem.

Definition 5 (Fuzzy Path Planning Problem) Let us consider two fuzzy positions ( ĩp , tp ) and a spatial description given by SpaceOnology (Φ, R, I). A path solution Pth between ĩp , tp is a continuous sequence of positions/regions that allows the robot to move from the initial state to the goal state while avoiding obstacles.

Path Planning

Our main contributions to the path planning focus on using space hierarchy, topological spatial relations and spatial fuzzy information.

Let us consider that the initial position i p is accurate 5 and the target position tp is fuzzy. The path 5 To simplify the explanation, the initial position is crisp. This work may well be applied in the context of precise positions.

planning operation is summarized in the main algorithm 1.

Algorithm 1 main

Require: (Φ, R, I), ip, t p , KC Σ 1: Γ G ←-developΓ G (Φ, R, I, ip, t p, KC Σ ) 2: P ←-search(Γ G , ip, t p )
3: target zone t p delimitation 4: return A best path P from ip, t p • Modeling the environment; it is based on SpaceOntology (Φ, R, I), for spatial reasoning in order to define a structure called Crossing Network Graph, Γ G (line 1). • In this graph, we try to find a path between two positions i p , tp according to the optimality criteria (line 2). A path solution is a list of regions that the robot must visit to reach its target position. • then defining the target position (line 3).

Generation of Crossing Network Graph

A Cross- ing Network Graph Γ G is a directed graph.
Nodes are organized hierarchically. Edges represent hierarchical relation between nodes. A node in this graph represents a Crossing Network or a region.

Definition 6 (Crossing Network Γ) A graph Γ = (V ,E), where; V = (v 1 , . . . , v n ) is a set of vertices, each v i is a crossing network and E = (e 1 , . . . , e n ) is a set of edges, each e i defines an adjacency relation, a gateway and a congestion.

Algorithm 2 developΓ G Require: (Φ, R, I), ip, t p,KC Σ 1: Γ G ←-lowLevelNetwork((Φ, R, I), ip, t p, KC Σ ) 2: l ←-Γ G .getLowLevel() 3: highlevel ←-t p.getLevel() 4: while l < highlevel do 5: g ←-develop(Γ G .getGraph(l), ip, t p, Φ, R, I, KC Σ ) 6: add g to Γ G in level l + 1 7: l ←-l + 1 8: end while 9: return Γ G
The algorithm 2 constructs the Crossing Network Graph Γ G . Each element of this graph is related to the mission. This graph defines all possible paths between ip and t p. The function developΓ G is executed in two steps. The first, generation of the abstract graph (lines 1, 2). The second, incremental development of the abstract graph (lines 3 to 7).

Abstract Graph Generation : The idea consists in finding the first same ancestor of the two places i p , tp and returning the hierarchical level l of this ancestor. After this, the abstract Crossing Network is generated (algorithm3).

Algorithm 3 lowLevelNetwork

Require: (Φ, R, I), ip, t p , KC Σ 1: l ← lowLevel(Φ, R, I, ip, t p) -1 2: N ←-/ 0, E ←-/ 0 3: initialzone ←-Z l (ip) , targetzone ←-Z l ( t p ) 4: N ←-initialzone, N ←-N ∪ targetzone 5: rg ←-targetzone 6: R ←-{ regions form I in level l } 7: while rg = initialzone do 8: Select r from R | 9:
r check that r is concerned by the mission 10:

r is not a dead end 11:

rg and r are directly connected 12:

gateways ←-(rg, r) | they satisfy KC Σ 13: N ←-N ∪ r
14:

E ←-E ∪ Edge(rg, r) 15: rg ←-r 16: end while 17: g ←-(N, E) 18: return g = (N, E)
Note, by g = (N, E) the abstract Crossing Network. N is a sub set of regions in the abstract level (lines 9, 10). For each n ∈ N, n must satisfy the selection criteria (lines 14 to 18). E is a set of edges. Edges represent spatial adjacency relations between two nodes giving gateways. The selection of gateways depends on kinematic constraints of the robot. The function lowLevel gives the level of the most same abstract ancestor of i p , tp . This algorithm is a query submitted to the ontology. In SpaceOntology, the relation isPartOf is transitive. The inference mechanisms provided by the ontology help to deduce for a given region, the region encompassing it.

Hierarchical Development : The algorithm 4 develops each node of level l until reaching the target hierarchical level highlevel. This taking the various constraints into account . Graph generation is mainly based on topological relations. Based on the notion of hierarchical interest zone, we manage the fuzzy information. We consider the most abstract region encompassing the region in which the coffee machine is. But, this is not enough. Indeed, we will generate all possible paths between buildings B1 and B6 by considering B2 ,B3, B4 and B5. However, the passing through the buildings B2, B4 and B5 is not necessary (Fig. 12). For B2 and B5 they are not included in the mission; they are a deadlocks regions (one gate to exit/entrance). For B4, it is not included in the mission. Also, this region is connected to a deadlock region B5. So, B4 is also a deadlock region. By combining all these concepts we can generate the crossing network graph (Fig. 17). and the target is in floor E B6 2 . These offices are not in the same hierarchical level. In addition, these regions (O B1 11 and E B6 2 ) are not adjacent. Thus, finding a path between these two regions exploits the space hierarchy and adjacency links defined in SpaceOntology. 11 and E B6 2 in the same level, there are B1 and B6. Then, we look for the adjacency links between B1 and B6. We assume that each region is adjacent to its neighbors with gates. To extract gates between regions, we query the ontology. So, we generate all possible paths between buildings B1 and B6 by considering B2 ,B3, B4 and B5. However, the passing through the buildings B2, B4 and B5 is not necessary (Fig. 12). For B2 and B5 they are not included in the mission; they are a deadlocks regions (one gate to exit/entrance). For B4, it is not included in the mission. Also, this region is connected to a deadlock re-gion B5. So, B4 is also a deadlock region. By combining all these concepts we generate a directed graph: Crossing Network Graph (Fig. 17). Nodes are organized hierarchically. Edges represent hierarchical relation between nodes. A node in this graph represents a Crossing Network (a graph given the adjacency relations between regions in the same hierarchical level). Each node of one level l is developed until reaching the target hierarchical level. We assume that N l is a subset of regions in the level l. E l is a set of edges. Edges represent spatial adjacency relations between two nodes giving gateways. For each n ∈ N l , n must satisfy the selection criteria.

Path Computing We search a path between two positions i p (accurate position) and tp (fuzzy position) in the Crossing Network Graph, based on two criteria measures [START_REF] Mouaddib | Multi-objective decision-theoretic path planning[END_REF]: (1) minimize the Euclidean distance between i p and tp and (2) facilitate access to a region, to ensure fast and simple actions. We combine these concepts in order to improve the path solution quality. These criteria, allow the robot to execute its actions in an easy and quick way (the choice of paths that are short in terms of distance) and to maintain the speed of navigation. We define a measure:

Θ(p 1 , p 2 ) = (d(p 1 , p 2 ), c(p 1 , p 2 ))
, where d(p 1 , p 2 ) is the euclidean distance between p 1 et p 2 and c(p 1 , p 2 ) measures the congestion in the region between p 1 and p 2 . Pathfinding in crossing network graph consists of path search in crossing network for each hierarchical level. A path solution is a sequence of paths pth 0 , . . . , pth k , where pth i contains nodes of the i-th level and that are a specialization of nodes on pth i-1 (i.e the path solution in level 1 is B1-C6-B6, the pathfinding in level 2 will not consider the sub nodes of the node B3 (Fig. 17). In each level, we use multi-criteria Dijkstra's algorithm with a single source Z i (i p ). It returns the shortest path between the source node and the target one Z i ( tp ) (i is the abstract level). The shortest path is the path minimizing the measure Θ i = (d, c) i , where d is the Euclidean distance and c is a congestion measure. In order to minimize Θ i , we compute it as described in [START_REF] Mouaddib | Multi-objective decision-theoretic path planning[END_REF]: Regret(crit). The concept is to minimize the regret (Fig. 18). We compute θ * , where this measure is θ * = (0, 5) * = [Min(3, 0), Min(5, 9)]. Then, for each edge e, we compute the distance between θ * and θ e :

Θ i = ∑ crit∈{d,c}
Min(Dist) = Dist(θ c B6 12 , θ * ) = Dist((3, 5), (0, 5)) = 3 Dist(θ c B6 42 , θ * ) = Dist((0, 9), (0, 5)) = 4
Finally, we select the edge allowing us the minimum distance with θ * : edge c B6 12 (Fig. 18).

Level 1

Level 2

Level 3

O B1 11 H B1 11 H B1 31 H B3 21 C B3 21 C B3 12 H B6 21 C B6 11 C B6 21 d11 c B1 13 C1 d21 c B3 21 C3 c B6 12 d21 E B1 1 E B1 3 E B3 2 E B3 1 E B6 1 E B6 2 c B1 13 C1 c B3 21 C3 c B6 12 B1 B3 B6 C1 C3
Figure 19: Hierarchical Path Solution.

We are not interested in the global network in level i. Indeed, we consider that the nodes and edges belonging to the path solution of level i -1. We can generate the path for each node in the next level and exploit the hierarchical aspect of space which reduces the search time. Indeed, only nodes of the at level i are extended in level i + 1 and thus some edges in the graph are not explored (Fig. 19).

Delimitation of the Fuzzy Region This step uses the proximity queries that allows for a region to define the set of regions that are close/far to it. Let us consider our scenario (Example 4). The robot found the coffee machine. However, it does not reach its target position.

SELECT ?target " WHERE {"?x ns:concerns \"close\"."

"?x ns:hasReferent \"CM\". " "?x ns:hasTarget ?target."} To achieve/define its target, we use the proximity query defined in Figure 20. This query defines the set of regions which verifies the close (close) relation with the coffee machine (CM).

Plan Solution

A plan solution is sequence of a set actions where each set of primitive actions is a partial plan performed on a single hierarchical level to reach the state goal starting from a certain initial condition. For the generation of the plan several techniques are possible, mainly GraphPlan, HTN. According to the reasoning described here, we have the plan solution depicted in Figure 21 for the mission defined in the Example 4. This plan is generated by applying the algo-rithm Graphplan 6 . The satisfaction of spatial preconditions is based on querying SpaceOntology. The disambiguation of fuzzy positions is also based on this ontology. Indeed, in Example 4, the target office is defined in a fuzzy way. Using our model we found the office o22b6.

go(Bobo, o11b1, o22b6) pick-up (Bobo,book,table,o22b6) go (Bobo,o22b6,o11b1) give (Bobo,book,Arnaud,o21b1) Figure 21: Solution Plan.

The robot moves between 011b1 and 022b6. The navigation action respect the path solution given in Figure 19. Then, it takes the book, it joins the human and finally, it gives the book to the human. The execution of the action give requires that the robot is at a distance between 0.5 and 1 meters as specified in the definition of the problem (Fig. 15).

EXPERIMENTS

We present the resolution complexity and some experimental results to solve planning described with Spatial-PDDL.

Complexity Analysis

The global complexity of the plan generation of a plan depends on the complexity of inference, the complexity of the graph generation and the complexity of plan solution generation. In this section, we present the complexity analysis for the generation of the graph and path computation. The complexity of plan generation depends on the algorithm used, we use Graphplan. The inference complexity depends on the number of rules. It correpsonds to the complexity given by the reasoner Pellet [START_REF] Sirin | Pellet: A practical owl-dl reasoner[END_REF].

Generation of Crossing Network

The Crossing Network generation is based on the adjacency relations between the regions of mission. Two ways to define an adjacency relation with SpaceOntology (Fig 22): (1) by exploiting hierarchical relations or (2) by exploiting the adjacency relations. Formally, this crossing network generation depends on the gates number used; |G|. In the case of hierarchical relation, the complexity is O(|G|). In the case of topological relation, the complexity is O(|G| 2 ). So, we use inclusion relation.

Path Computing

Let N be the nodes number in the Crossing Network Graph generated. The branching factor b n corresponds to the number of sub-nodes of an abstract node n. We assume that b n l gives the number of sub-nodes of a node n in level l. So N = ∑ max l l=min l ∑ n min l -1 i=1 bi l , where; (1) n min l -1 is the set of nodes in the most abstracted level in the Crossing Network Graph, (2) min l is the most abstracted level in the Crossing Network Graph, (3) max l is the most detailed level in the Crossing Network Graph, (4) bi l is the number of new nodes that can be generated from a node i in the level l and (5) ∑ n min l -1 i=1 b i min l -1 corresponds to the number of nodes in the level min l .

We used multi-criteria Dijkstra's single-source shortest path algorithm.

In fact, implementing the priority queue with a Fibonacci heap makes the complexity O(E + V logV ), where E is the number of edges and V the nodes number. So in each Level , l the complexity of path finding is O(E l + ∑ i=1 bi l-1 ))). The impact of the hierarchical multi-criteria Dijkstra's single-source approach in the pathfinding, is depicted in Table 2. In our context, real scenarii do not exceed 6 levels and maximum branching factor of 5 sub-nodes (b). According to table 2, we noted that our approach returns a path solution in a time (in seconds) ∈ [0, 100] which is acceptable. Finally, the proposed pathfinding method in an environment, based on its description via SpaceOntology is not complex or expensive (in our application context). Whatever, it depends on several factors namely, the Crossing Network Graph generation time (due to quantity / quality and structure of spatial information) and the size of this graph.

Experimental Results

The computation time to solve a spatial planning problem described in Space-PDDL depends on computing time of answering to queries (Table 2).

Table 3 shows that the computation time depends on the number of requests and the response time. The latter depends on the rules number defined in SpaceOntology. This computing time is very reasonable even if we have a large number of requests. In-

Figure 1 :

 1 Figure 1: Graphical representation of SpaceOntology.

Figure 2 :

 2 Figure 2: Graphical illustration of SpaceOntology to describe structures in specific domains.

Figure 3 :

 3 Figure 3: Partial Map.

Figure 5 :

 5 Figure 5: Spatial Relation Network.

Figure 6 :

 6 Figure 6: Spatial Relation Between o1 and o3.

Figure 7 :

 7 Rule definition for left below with composition.

  Figure 9 illustrates the translation of a distance from a numeric definition to symbolic definition and vice versa. The parameters α and β allow us to evaluate the numeric distance. These parameters depend on the current region. Figure 8 is a rule allowing us to evaluate a distance relation. The rule Def close relation (fig. 8) translates a numeric distance (NumericDistance) (distanceValue (?relation)) in symbolic evaluation (FuzzyDistance) given by the instance close which indicates the close relation. This rule is apply for distance (distanceValue (?relation)) between 0 and α.

  Figure 10: Spatial Planner

Figure 12

 12 Figure 11: Abstract Map.

  take(r,b,?o) (robot r) (book b)(empty-arm r) (¬(has r b))(region ?o)(At r ?o) (:query (freevars (?o -Region ?α ?β -@xsd:int

  Figure 13: Modeling the Action take in Spatial-PDDL.

Figure 14 :

 14 Figure 14: Extension of PDDL with Spatial Predicates.

Figure 15 :

 15 Figure 15: An Example of Spatial-PDDL Problem.

  Figure 16: An Example of Spatial-PDDL Domain.

Figure 17 :

 17 Figure 17: Crossing Network Graph First, we consider the most abstract regions for O B111 and E B6 2 in the same level, there are B1 and B6. Then, we look for the adjacency links between B1 and B6. We assume that each region is adjacent to its neighbors with gates. To extract gates between regions, we query the ontology. So, we generate all possible paths between buildings B1 and B6 by considering B2 ,B3, B4 and B5. However, the passing through the buildings B2, B4 and B5 is not necessary (Fig.12). For B2 and B5 they are not included in the mission; they are a deadlocks regions (one gate to exit/entrance). For B4, it is not included in the mission. Also, this region is connected to a deadlock re-

Figure 18 :

 18 Figure 18: Regret Based Path Selection.

Figure 20 :

 20 Figure 20: Proximity Query.

Figure 22 :

 22 Figure 22: In the left, the adjacency relation is presented by hierarchical relation and in the right, by topological one.6 http://www.cs.cmu.edu/ avrim/graphplan.html.

  translate(?link,?t link) ⊓ translate(?relation, ?t relation) ⊓ concerns(?link,?relation) ⊓ hasTarget(?link,?tgt) ⊓ hasReferent(?link,?ref) ⊓ isANumericDistance(?relation) ⊓ isPartOf(?ref,?region) ⊓ isPartOf(?tgt,?region)

	⊓ swrlb:greaterThan(distanceValue(?relation),0)
	⊓ swrlb:lessThanOrEqual(distanceValue(?relation),alpha(?region))
	-→
	[concerns(?t link,?t relation) ⊓ hasTarget(?t link,?tgt) ⊓ hasTarget(?t link,?tgt)
	⊓ hasReferent(?t link,?ref) ⊓ isAFuzzyDistance(?t relation) ⊓ is(?t relation,"close")]
	Figure 8: Rule Definition of Def close relation.

Table 1 :

 1 Extended Notions with SpaceOntology Elements.

			of extends and @ns
	Objects	O	spatial/non spatial objects
	Actions	A	non spatial/spatial/navigation actions

  This query takes as parameter a gate (gate) and defines the regions connected to this gate. The indirect adjacency is inferred by the existence of a path (of length greater than one see next section).

	WHERE {"?x ns:concerns \"close\"."
	"?x ns:hasReferent ?referent. "
	"?x ns:hasTarget ?target."}
	This query takes a parameter relation (close) and
	defines the regions that are close.
	Hierarchical Interest Zone Query To define the
	function Z l (r), we define the hierarchical interest
	zone query.
	SELECT * "
	WHERE {"?region rdf:type ns:Regions ."
	"?region ns:label \"" + rg +"\" ."
	"?region ns:isPartOf ?father . "
	"?father ns:level ?level." }
	"Filter ( ?level = " + level + " ).
	SELECT ?referent ?target "
	WHERE {"?x ns:label ?relation."
	"?x ns:hasintersection \"gate\"."
	"?x ns:hasReferent ?referent. "
	"?x ns:hasTarget ?target."}
	Proximity query A proximity query defines re-
	gions that are close to a given region or if a region
	is near or far from another region.
	SELECT ?referent ?target "

  Require: graph = (N,V ), ip, t p ,Φ, R, I, KC Σ

	Algorithm 4 develop
	1: l ←-graph.getLevel()
	2: nodes ←-/ 0, edges ←-/ 0
	3: for n ∈ N do 4: gates ←-n.getVertex.getGateways()
	5:	if (n == Z l+1 (ip)) then
	6:		iz ←-Z l+1 (ip)
	7:		gr ←-graph(iz, gates, KC Σ , Φ, R, I, )
	8:		nodes ←-gr.nodes
	9:		edges ←-gr.edges
	10:	else if (n == Z l+1 ( t p)) then
	11:		tz ←-Z l+1 ( t p)
	12:		gr ←-graph(tz, gates, KC Σ , Φ, R, I, )
	13:		nodes ←-nodes ∪ gr.nodes
	14:		edges ←-edges ∪ gr.edges
	15: 16:	else	g ←-gates
	17:		gr ←-graph(g, g, KC Σ , Φ, R, I, )
	18:		nodes ←-nodes ∪ gr.nodes
	19:		edges ←-edges ∪ gr.edges
	20: 21: end for end if 22: graph l+1 ←-(nodes, edges)
	23: return graph l+1 = (N l+1 ,V l+1 )
	Example 7 In example 4, the team is in office O B1 11

For more readability, we omit certain classes and attributes.

deed, in Table 3, for a query number between 21 and 30, solving the problem is done in 15.01 seconds.

CONCLUSION

Our main contribution was the extension of PDDL to spatial knowledge: Spatial-PDDL. To do this, we uses SpaceOntology that considers several spatial knowledge aspects; the space hierarchy, spatial relations (numeric, topological and fuzzy). This permits to consider not only numeric spatial information in preconditions but also topological and fuzzy information. Moreover, spatial reasoning (the inference mechanisms) provided by this ontology permits a complex reasoning. SpaceOntology in the planning, is not used for verification or control, but as information needed for planning.

Future work will concern the improvement of spatial interaction between human and robots. In other words, we aim to formalize communication between them, especially in the case where the set of fuzzy rules are not sufficient to find a solution.


R Balasubramanian

C R Subramanian

On Sampling Colorings of Bipartite Graphs †

Keywords: Graph Colorings, Markov Chains, Analysis of Algorithms

We study the problem of efficiently sampling k-colorings of bipartite graphs. We show that a class of markov chains cannot be used as efficient samplers. Precisely, we show that, for any k, 6 ≤ k ≤ n 1/3-ǫ , ǫ > 0 fixed, almost every bipartite graph on n + n vertices is such that the mixing time of any ergodic markov chain asymptotically uniform on its k-colorings is exponential in n/k 2 (if it is allowed to only change the colors of O(n/k) vertices in a single transition step). This kind of exponential time mixing is called torpid mixing. As a corollary, we show that there are (for every large n) bipartite graphs on 2n vertices with ∆(G) = Ω(ln n) such that for every k, 6 ≤ k ≤ ∆/(6 ln ∆), each member of a large class of chains mixes torpidly.

We also show that these negative results hold true for H-colorings of bipartite graphs provided H contains a spanning complete bipartite subgraph. We also present explicit examples of colorings (k-colorings or H-colorings) which admit 1-cautious chains that are ergodic and are shown to have exponential mixing time.

While, for fixed k or fixed H, such negative results are implied by the work of [2], our results are more general in that they allow k or H to vary with n.

Introduction

We consider the problem of efficiently sampling uniformly at random the k-colorings of a graph. This problem is related to the corresponding problem of counting the number of such structures which arise in statistical physics (see the survey of [START_REF] Jerrum | The Markov chain Monte Carlo method : an approach to approximate counting and integration[END_REF]). The Monte Carlo Markov chain (MCMC) approach has been very successful in obtaining efficient samplers for this problem under various assumptions about the input graph. This naturally leads to the question of how far can the MCMC approach take us. In this paper, we present some negative results on obtaining efficient samplers for colorings based on markov chains.

Several heuristics have been proposed and analyzed for efficiently sampling k-colorings [START_REF] Jerrum | A very simple algorithm for estimating the number of k-colorings of a low-degree graph[END_REF][START_REF] Salas | Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem[END_REF][START_REF] Bubley | Beating the 2∆ bound for approximately counting colorings: A computer-assisted proof of rapid mixing[END_REF][START_REF] Dyer | A more rapidly mixing Markov chain for graph colorings[END_REF][START_REF] Vigoda | Improved bounds for sampling colorings[END_REF]. The currently best known positive result is due to Vigoda [START_REF] Vigoda | Improved bounds for sampling colorings[END_REF] who showed that the chains associated with the so-called (WSK) heuristic and the Glauber dynamics both mix in polynomial time for arbitrary G provided k ≥ (11/6)∆(G) where ∆(G) denotes the maximum degree of G. See [START_REF] Dyer | Randomly colouring graphs with lower bounds on girth and maximum degree[END_REF][START_REF] Molloy | The Glauber dynamics on colorings of a graph with high girth and maximum degree[END_REF][START_REF] Hayes | Randomly Coloring Graphs of Girth at least Five[END_REF][START_REF] Hayes | A Non-Markovian Coupling for Randomly Sampling Coloring[END_REF] for further improvements on special classes of graphs.

For arbitrary G, the focus has been on k ≥ ∆ because, for k < ∆, it is not even guaranteed that G has a k-coloring and moreover determining if it has such a coloring is N P -complete. But, a bipartite G always has a k-coloring for k ≥ 2 and a natural question is whether MCMC approach succeeds for k < ∆. In view of the previous successes, it appears to be likely. However, no such positive result has appeared so far and only some negative results have been obtained.

For example, recently, Luczak and Vigoda [START_REF] Luczak | Torpid mixing of the Wang-Swendsen-Kotecky algorithm for sampling colorings[END_REF] showed that WSK heuristic has exponential mixing time for a family of ∆-regular (constant ∆) bipartite graphs G(k, n) when 3 ≤ k ≤ ∆/20 log ∆. Such chains with exponential mixing times are said to be torpidly mixing.

Similarly, the negative results of Cooper, Dyer and Frieze [START_REF] Cooper | On Markov chains for randomly H-colouring a graph[END_REF] on sampling H-colorings imply that for every fixed k ≥ 3, there exist constants ∆ = ∆(k), δ = δ(k) > 0, τ = τ (k) > 1 and ∆-regular bipartite graphs G (on 2n vertices) such that for every δn-cautious ergodic chain M which is uniform on k-colorings of G, its mixing time is at least τ n . Here, by a δn-cautious chain, we mean a chain which does not change the colors of more than δn vertices in a single transition. But these results are true only for fixed values of k and the arguments do not seem to carry over when k is allowed to grow with n.

In this paper, we further strengthen these results by establishing that, for any s = Ω(ln n) and any k, 6 ≤ k ≤ s/(6 ln s), for almost every bipartite graph on 2n vertices with ∆(G) ≈ s, the mixing time of every member of a large class of chains for sampling k-colorings is exponentially large in n. This result is derived as a corollary of a more general statement (given below) we prove. We use C k (G) to denote the set of all (labelled) k-colorings of G.

Theorem 1.1 Define d = d(k) = 1/8k and γ = γ(k) = 1/(385k 2 ).
The following is true for every sufficiently large n and for every k, 6 ≤ k ≤ n 1/3-ǫ , ǫ > 0 fixed but arbitrary :

Let G ∈ G(n, n, p) with np ≥ 6k(ln k). Then, with probability at least 1e -n/(k 2 ln n) , G satisfies the following : For any dn-cautious ergodic markov chain M(G) which is asymptotically uniform on C k (G), its mixing time is Ω(e γn ).

In this, by the phrase "G ∈ G(n, n, p)", we mean a random bipartite graph formed between two sets A and B of equal size n. Each edge joining A and B is chosen independently with probability p. Note that np is essentially the average degree of a vertex in G.

Note that Theorem 1.1 allows k to grow with n and does not require it to be fixed. In fact, we can even suitably choose the random model so that G is a random element drawn from specific classes (see Section 5 for more details). Thus, for example, we can assume that G is a random graph of maximum degree ≈ s where s is any suitably large value. Similarly, we can assume that G = K n,n . In particular, any (n/8k)-cautious chain (this includes the well-known Glauber dynamics) mixes torpidly on C k (G) if G = K n,n and k lies in the stated range. (i) The overall approach of our proof is similar to that employed by Dyer, Frieze and Jerrum [START_REF] Dyer | On counting independent sets in sparse graphs[END_REF] and is based on showing that almost surely, C k (G) is such that one can obtain an exponentially small upper bound on the conductance of any dn-cautious chain. Sections 3 and 4 contain the proof of this theorem.

It is easy to check that Theorem 1.1 holds even if we redefine C k (G) to the set of those k-colorings of G in which some color is not used on any vertex of some partite set (A or B). For such colorings, even such simple chains as Glauber dynamics is ergodic on any bipartite graph. See Section 6 for further discussion.

We also present some explicit examples of colorings for which the 1-cautious chain Glauber dynamics can be shown both to be ergodic and to require exponential mixing time. These explicit examples are (i) Actually, for Kn,n, one can show, by slightly modifying an argument in [START_REF] Luczak | Torpid mixing of the Wang-Swendsen-Kotecky algorithm for sampling colorings[END_REF], that Glauber dynamics is torpidly mixing for any

k ≤ n 1-ǫ , ǫ > 0 is fixed.
illustrations of the applicability of Theorem 1.1. These examples are presented in Section 7.

Generalizations to H-colorings

A careful study of the proof of Theorem 1.1 shows that the proof can be modified to prove a similar theorem for a more general scenario of sampling H-colorings of bipartite graphs. The details are given below.

Given graphs G = (V, E) and H = (U, F ), a H-coloring of G is a mapping c : V → U such that (c(x), c(y)) is an edge of H whenever (x, y) is an edge of G. The standard proper k-coloring is a K k -coloring where K k is a simple complete graph on k vertices. We use C H (G) to denote the set of all Hcolorings of G. Note that if H has at least one edge, then any bipartite G admits a H-coloring and if H has no edges, then a bipartite G admits a H-coloring if and only if G also has no edges. Hence a H-coloring of a bipartite G (for arbitrary H) (or equivalently a starting point in C H (G)) can be found in polynomial time. Using the arguments of the proof of Theorem 1.1, we can prove the following generalization :

Theorem 1.2 Define d = d(k) = 1/8k and γ = γ(k) = 1/(385k 2 ).
The following is true for every sufficiently large n and for every k, 6 ≤ k ≤ n 1/3-ǫ , ǫ > 0 fixed but arbitrary :

Let G ∈ G(n, n, p) with np ≥ 6k(ln k) and let H be any simple (without self-loops) graph on k vertices such that H has a K ⌈k/2⌉,⌊k/2⌋ as a subgraph. Then, with probability at least 1e -n/(k 2 ln n) , G satisfies the following : For any dn-cautious ergodic markov chain M(G) which is asymptotically uniform on C H (G), its mixing time is Ω(e γn ).

A sketch of the proof of this theorem is given in Subsection 3.1. Note that H is not required to be fixed and H and its size can vary with n. The results of [START_REF] Cooper | On Markov chains for randomly H-colouring a graph[END_REF] require H to be fixed.

Preliminaries

A discrete-time Markov chain M over a finite space Ω and with transition matrix P is said to be ergodic if there is a limiting distribution π : Ω → [0, 1] such that for all x, y ∈ Ω, Lim t→∞ P t (x, y) = π(y). Two conditions which together are sufficient to ensure ergodicity are (1) M is aperiodic, i.e., gcd{t : P t (x, y) > 0} = 1 for all x, y ∈ Ω, and (2) M is irreducible, i.e., for each x, y ∈ Ω, there is a finite t such that P t (x, y) > 0. But if M is ergodic and is asymptotically uniform over Ω, then M is also irreducible and aperiodic. The mixing time τ (ǫ), ǫ > 0, of M is the least integer t > 0 such that the L 1 distance between the t-th step distribution and π is at most 2ǫ, irrespective of the starting point. For our negative results, it is enough to prove a lower bound on the value of τ (1/e).

We use the following notion introduced in [START_REF] Dyer | On counting independent sets in sparse graphs[END_REF]. For a graph G, let M(G) be any such chain (on C k (G)) with transition matrix P G . For any b ≤ n, we say that

M(G) is b-cautious if, for any two k-colorings σ 1 , σ 2 ∈ C k (G), h(σ 1 , σ 2 ) > b ⇒ P G (σ 1 , σ 2 ) = 0.
Here, h(σ 1 , σ 2 ) refers to their hamming distance (number of vertices in which σ 1 and σ 2 differ).

Proof of Theorem 1.1

The proof is based on establishing an upper bound on the conductance of the chains for sampling kcolorings. Its major outline is similar to that employed in [START_REF] Dyer | On counting independent sets in sparse graphs[END_REF] and is given below.

Broad outline of the proof

We prove by showing that, almost surely, G satisfies : For every dn-cautious ergodic chain M(G), shortly M, with asymptotic uniform distribution π on Ω =C k (G) and whose transition matrix is P : there exists S ⊆ C k (G) with 0 < |S| ≤ 0.5|Ω| and ψ S ≤ e -γn where ψ S = i∈S,j ∈S π(i)P (i, j) π(S) .

The quantity ψ S is called the conductance of the set S. It then follows from a well-known fact [START_REF] Sinclair | Randomized Algorithms for Counting and Generating Combinatorial Structures[END_REF][START_REF] Sinclair | Approximate counting, uniform generation, and rapidly mixing Markov chains[END_REF] that τ (1/e) = Ω(e γn ).

Before we proceed with the proof, we introduce some definitions and assumptions which will be used later

. Let V 1 , V 2 , . . . , V k denote the k (ordered) color classes of an arbitrary k-coloring of G ∈ G(n, n, p). For every C ∈ C k (G), we can associate a 2k-vector (α, β) denoting a sequence (α 1 , . . . , α k , β 1 , . . . , β k ) of nonnegative real values defined by α i n = |V i ∩ A| and β i n = |V i ∩ B| for each i ≤ k. Note that i α i = i β i = 1. Proof: Define for any k : c 1 (k) = 1 4k , c 2 (k) = 1 2k and c 3 (k) = 1 384k 2 . Note that 2d(k) = c 2 (k) -c 1 (k).
We introduce two specific k-tuples γ and δ of reals which will be used in the definition of the set S. For even k, γ is defined as

γ i = 2/k for i ≤ k/2 and γ i = 0 for k/2 < i ≤ k. δ is defined by δ i = 0 for i ≤ k/2 and δ i = 2/k for k/2 < i ≤ k. Thus, for even k, the point (γ, δ) looks like γ δ = 2 k , . . . , 2 k , 0, . . . , 0 0, . . . , 0, 2 k , . . . , 2 k For odd k, γ i = 2/(k + 1
) and δ i = 0 for i ≤ (k + 1)/2 and and γ i = 0 and

δ i = 2/(k -1) for i > (k + 1)/2.
We provide the proof for even k. For odd k, the arguments are almost identical. Define S 1 to be the set of all k-colorings with part sizes corresponding to some (α, Note that this claim holds true with probability 1, i.e., the claim is true for every possible value of G.

Without loss of generality, assume that S = S 1 . For any chain M with transition matrix P , the boundary ∂S of S is defined as ∂S = {i ∈ S : P (i, j) > 0 for some j ∈ S} It then follows (as noticed in [START_REF] Luczak | Torpid mixing of the Wang-Swendsen-Kotecky algorithm for sampling colorings[END_REF]) that

ψ S ≤ i∈∂S π(i) /π(S) = π(∂S)/π(S) = |∂S|/|S|
Hence it suffices to show that, for almost every G, for every dn-cautious M, we have |∂S|/|S| = O(e -γn ).

For an arbitrary coloring C, let (α C , β C ) denote its corresponding vector. Consider any two k-colorings C, D of G. The proof of the following claim is given later.

Claim 3.2 h(C, D) ≥ 0.5n||(α C , β C ) -(α D , β D )|| 1 .
We claim that for every ergodic dn-cautious chain M(G),

∂S ⊆ {C ∈ S : c 1 ≤ ||(γ, δ) -(α C , β C )|| 1 ≤ c 2 }.
To see this, consider any arbitrary C ∈ ∂S. Then, there exists a D ∈ S such that h(C, D) ≤ dn and hence

||(α C , β C ) -(α D , β D )|| 1 ≤ 2h(C, D)/n ≤ 2d = c 2 -c 1 .
As a result, it follows that ||(γ, δ)

-(α C , β C )|| 1 ≥ c 1 .
For otherwise, we will have

||(γ, δ) -(α D , β D )|| 1 ≤ ||(γ, δ) -(α C , β C )|| 1 + ||(α C , β C ) -(α D , β D )|| 1 < c 1 + (c 2 -c 1 ) = c 2
which violates our assumption that D ∈ S. Hence our claim is true.

Let n max (G) denote the number of k-colorings with part sizes corresponding to (γ, δ). Let n bd (G) denote the number of k-colorings with part sizes corresponding to some (α,

β) with c 1 ≤ ||(γ, δ) - (α, β)|| 1 ≤ c 2 . Thus, |∂S| ≤ n bd (G) and |S| ≥ n max (G).
It is shown later (Theorem 3.1) that, with probability at least 1e -n/(k 2 ln n) , G satisfies

|∂S| |S| ≤ n bd (G) n max (G) < e -γn
This completes the proof of Theorem 1.

h A (C, D) = 0.5 i #(C i (A) ⊕ D i (A)) ≥ 0.5 i | #(C i (A)) -#(D i (A)) | = 0.5n i | α i (C) -α i (D) | = 0.5n ||α C -α D || 1 .

✷

It only remains to prove Theorem3.1 stated formally below. Before we proceed with the proof of this theorem, we introduce and study some notions which are required in its derivation.

For each pair (α, β) of two k-tuples of non-negative reals each summing to 1, let C G (α, β) denote the set of all k-colorings of G with part sizes |V i ∩ A| = α i n and |V i ∩ B| = β i n for each i ≤ k. Let N G (α, β) denote the expected number of such k-colorings. First, we estimate the expectation N G (α, β) for each (α, β) and bound these expections. We then apply Markov's inequality to get an upper bound on bd (G). For a given (α, β), note that

N G (α, β) = n α 1 n, . . . , α k n n β 1 n, . . . , β k n (1 -p) (α1β1+...+α k β k )n 2 = n! (α 1 n)! . . . (α k n)! n! (β 1 n)! . . . (β k n)! e a(α1β1+...+α k β k )n ( 1
)
where a is defined to be a = a(n, p) = n ln(1p). (ii) Note that a ≤ 0 and |a| ≥ np always. Using Stirling's approximation of factorials, it is easy to see that : For some large constant D > 0,

n -k e ψ(α,β)n ≤ n! (α1n)!...(α k n)! n! (β1n)!...(β k n)! ≤ D k e ψ(α,β)n (2)
where 1) and ( 2), we get

ψ(α, β) is defined by ψ(α, β) = i≤k -α i ln α i + i≤k -β i ln β i . Combining (
n -k e φ(α,β)n ≤ N G (α, β) ≤ D k e φ(α,β)n (3)
(i) For each (α, β) with c 1 ≤ ||(γ, δ) -(α, β)|| 1 ≤ c 2 , φ(α, β) ≤ φ(γ, δ) -c 3 .
(ii) (γ, δ) is not a local maximum of φ. (iv) (ii) ln α denotes the logarithm of α to the natural base e. (iii) Note that φ is a continuous function defined over the interior of the set (α k = 1 -P i<k α i and

β k = 1 - P i<k β i ) B = {(α 1 , . . . , α k-1 , β 1 , . . . , β k-1 ) : 0 ≤ X α i , X β i ≤ 1}
and is symmetrical between the values of α i , β i , i.e., φ(α, β) = φ(β, α). φ can be extended to the boundary by taking the limits which are obtained by defining 0 ln 0 = Lt x→0 x ln x = 0. For our purposes, each α i (β i ) is a non-negative integral multiple of 1/n. This is because the sizes of the color classes are integer valued. (iv) Statement (ii) is only for the sake of information, it is not required in the analysis of mixing time.

Proof: See Section 4. ✷

For even k, φ(γ, δ) = 2 ln(k/2) and for odd k, φ(γ, δ) = ln(k + 1) + ln(k -1) -2 ln 2. Using Theorem 3.2, we prove Proof: (of Theorem 3.1) By definition, each k-coloring counted for n max (G) does not depend on any potential edge joining A and B and hence n max (G) is the same whatever the value of G is. Hence

Pr( n max (G) = E[n max (G)] ) = 1
Thus, by [START_REF] Dyer | Randomly colouring graphs with lower bounds on girth and maximum degree[END_REF], n max (G) ≥ e φ(γ,δ)n /n k . Also,

E[n bd (G)] = c1≤||(α,β)-(γ,δ)||1≤c2 N G (α, β) ≤ c1≤||(α,β)-(γ,δ)||1≤c2
D k e φ(α,β)n by (3)

< (n + 1) 2k D k e -c3n e φ(γ,δ)n by Theorem 3.2 ≤ (n + 1) 3k D k e -c3n n max (G) ≤ e -c3n[1-o(1)] n max (G) using k = O(n 1/3-ǫ ).
Hence, by Markov's inequality, with probability at least 1e -n/(k 2 ln n) ,

n bd (G) ≤ e n/(k 2 (ln n)) e -c3n[1-o(1)] n max (G) < e -γn n max (G) ✷ 3.1 Proof of Theorem 1.2
The proof of this generalization is essentially the same as the proof of Theorem 1.1. As before, we show that the conductance of the set S (where S is essentially the same as before) is exponentially small. We need to change the definition of φ(α, β) as follows.

φ(α, β) = ψ(α, β) + a   i∈V (H) α i β i + i =j,(i,j) ∈E(H) (α i β j + α j β i )   .
The definition of ψ(α, β) remains the same. Here, we assume that H is a labeled graph on k vertices {1, . . . , k}. Because of the assumption that H contains a K k/2,k/2 subgraph, n max (G) remains the same. Also, the expectation of n bd (G) decreases because of the extra additive term which takes negative values.

Analysis of φ at (γ, δ)

Proof of Theorem 3.2i Recall that |a| ≥ 6k ln k. We prove the statement for even k. For odd k, the arguments are similar. Define c

1 (k) = 1 4k , c 2 (k) = 1 2k and c 3 (k) = 1 384k 2 . The point (γ, δ) is (2/k, . . . , 0, . . . , 0, . . . , 2/k, . . .). Consider any point (α, β) with c 1 ≤ ||(γ, δ) -(α, β)|| 1 ≤ c 2 . For i ≤ k/2, write α i = 2/k + κ i and β i = τ i . For i > k/2, write α i = τ i and β i = 2/k + κ i . Each τ i ≥ 0. Since 2 = i α i + i β i = 2 + i κ i + i τ i , we have i κ i ≤ 0. We have, φ(α, β) = T + a i (2/k + κ i )τ i where T = - i (2/k + κ i ) ln(2/k + κ i ) - i τ i ln τ i = - i (2/k + κ i ) ln(2/k) - i (2/k + κ i )(kκ i /2 -(kκ i /2) 2 /2 + . . .) - i τ i ln τ i = 2 ln(k/2) - i κ i (1 + ln(2/k)) - i kκ 2 i /4 -k 2 κ 3 i /24 + . . . - i τ i ln τ i . Hence φ(γ, δ) -φ(α, β) = (1 + ln(2/k)) i κ i + i τ i (ln τ i -a(2/k + κ i )) + i kκ 2 i /4 -k 2 κ 3 i /24 + . . . .
Let T 1 , T 2 , T 3 denote (respectively in that order) the three terms in the above expression. By our notation, i κ i ≤ 0. Also, since k ≥ 6 ≥ 2e, 1 + ln(2/k) ≤ 0. Hence T 1 is non-negative.

T 3 ≥ i kκ 2 i /4 - i k 2 |κ i | 3 /24(1 -k|κ i |) ≥ i kκ 2 i /4 - i k|κ i | 2 /24 = (5k/24) i κ 2 i ≥ (5/24) i |κ i | 2 ≥ (5/96)||(κ, τ )|| 2 1 ≥ 5/1536k 2 .
In the second term, by our choice of (α, β),

|κ i | ≤ 1/2k. Hence i τ i (-a)(2/k + κ i ) ≥ 3|a|/2k ( i τ i ).
Divide the sum i τ i ln τ i into two sums S 1 (summing over τ i ≤ 1/k 9 ) and S 2 (summing over the remaining).

S 1 ≥ -k(9 ln k)/k 9 = -(9 ln k)/k 8 . Also, S 2 ≥ -(9 ln k)( i τ i ). Hence T 2 ≥ 3|a| 2k -9 ln k i τ i - 9 ln k k 8 .
Combining all these,

φ(γ, δ) -φ(α, β) ≥ 5 1536k 2 - 9 ln k k 8 + 3|a| 2k -9 ln k i τ i (4) ≥ 1 384k 2 = c 3 (k) if we choose |a| ≥ 6k ln k.
Thus, for k ≥ 6, this proves Theorem 3.2i].

Proof of Theorem 3.2 ii We only consider the case of even k. To prove (ii) Consider the point (γ ǫ , δ ǫ ) defined for every small ǫ > 0. It is defined as follows. For even k,

γ ǫ i = δ ǫ k/2+i = 2/k -ǫ/k and δ ǫ i = γ ǫ k/2+i = ǫ/k for 1 ≤ i ≤ k/2. φ(γ ǫ , δ ǫ ) = -k 2 k - ǫ k ln 2 k - ǫ k -k ǫ k ln(ǫ/k) + ak 2 k - ǫ k ǫ k = φ(γ, δ) + ǫ ln 2 k -ln ǫ k + 1 - ǫ 2 4 + aǫ k (2 -ǫ) + O(ǫ 3 )
> φ(γ, δ) for all sufficiently small ǫ > 0.

Hence (γ, δ) is not a local maximum of φ.

Consequences

The following corollary shows that Theorem 1.1 holds even if our random G is conditioned to satisfy some property which holds with "not a too small" probability. We also illustrate the immediate consequences of this corollary with some specific examples. Throughout, k is a value such that 6 ≤ k ≤ n 1/3-ǫ . Also, d, γ have the same meaning given in Theorem 1.1. Definition : Let P denote an arbitrary property of bipartite graphs which is satisfied with positive probability by a random G ∈ G(n, n, p). Given p = p(n), we define s p (P, n) as the probability that G satisfies P. The random model G(n, n, p) | P is defined to the model obtained by conditioning G(n, n, p) to the event "G ∈ G(n, n, p) satisfies P".

Corollary 5.1 Let P be any property such that there is a p = p(n) with np ≥ 6k(ln k) and e -n/(k 2 ln n) = o(s p (P, n)). Then, almost surely, (v) G 0 ∈ G(n, n, p) | P satisfies the claim of Theorem 1.1.

Corollary 5.2 For any k, 6 ≤ k = O(n 1/3-ǫ ), for any dn-cautious ergodic markov chain M(K n,n ) which is asymptotically uniform on C k (K n,n ), its mixing time is Ω(e γ(k)n ).

Proof: Let P denote the property that G = K n,n and choose p = 1 leading to np = n. Also, s p (P, n) = 1 satisfying the requirements of Corollary 5.1. ✷ Corollary 5.3 Let G ′ denote any one of the random bipartite graphs G 1 and G 2 on n + n vertices defined below. Then, almost surely, G ′ satisfies : For any dn-cautious ergodic markov chain M(G ′ ) which is asymptotically uniform on C k (G ′ ), its mixing time is Ω(e γ(k)n ).

(v) In other words, most of bipartite graphs satisfying P also satisfy the torpid mixing property.

(i) G 1 is random with edge-density dens(G 1 ) = |E(G 1 )|/|V (G 1 )| ≤ s, for any s ≥ 4k(ln k).

(ii) G 2 is random with 0.9s ≤ ∆(G 2 ) ≤ 1.1s, for any s ≥ 850(ln n) and any k where 6 ≤ k ≤ min{s/(6 ln s), n 1/3-ǫ }.

Proof: Let G ∈ G(n, n, p) be a random bipartite graph on n + n vertices.

(i) Choose p = 3s/2n. Then, np ≥ 6k(ln k). Let P denote the property that dens(G) ≤ s and let G 1 ∈ G(n, n, p) | P. Then s p (P, n) = 1o(1) satisfying the requirements of Corollary 5.1.

(ii) Choose p = s/n. Then, np ≥ 6k(ln k). Let P denote the property that 0.9s ≤ ∆(G) ≤ 1.1s and let G 2 ∈ G(n, n, p) | P. For an arbitrary vertex u, by Chernoff-Hoeffding bounds (see [START_REF] Motwani | Randomized Algorithms[END_REF]),

Pr( ∆(G) > 1.1s ) ≤ 2n Pr( deg u (G) > 1.1(np) ) ≤ 2n e -np/400 = o(n -1 ). Also, Pr( ∆(G) < 0.9s ) ≤ Pr( ∀u ∈ A ∪ B, deg u < 0.9(np) ) ≤ e -np/200 = o(n -1 ). Hence s p (P, n) = 1 -o(1)
satisfying the requirements of Corollary 5.1. (vi) ✷ 6 Ergodicity and cautiousness Theorem 1.1 assumes that there are some dn-cautious ergodic chains on C k (G), otherwise there is no need to worry about mixing time. So it becomes important to study the conditions under which such ergodic chains exist. We answer this question partially by providing some positive answers and also some negative answers. There are O(1)-cautious ergodic chains which are uniform on C k (K n,n ) for k ≥ 3. Glauber dynamics (GD) which tries to recolor a uniformly chosen vertex with a uniformly chosen new color, is one such example. It is easy to verify that this chain is ergodic on the s-colorings of any complete l-partite graph G l , for any s > l. In particular, it is ergodic on k-colorings (for k ≥ 3) of any complete bipartite graph. The same is true of some variants of Glauber dynamics also (see [START_REF] Dyer | A more rapidly mixing Markov chain for graph colorings[END_REF]).

But, there exist some bipartite graphs for which GD is not ergodic (see the Fact 6.1 for a more general statement). As noted in [START_REF] Luczak | Torpid mixing of the Wang-Swendsen-Kotecky algorithm for sampling colorings[END_REF], the chain associated with WSK algorithm is ergodic for any bipartite graph even though it is not (n/k)-cautious. However, if we restrict our sample space to those k-colorings of G in which some color is not used on any vertex of some partite set (A or B), then Glauber dynamics is ergodic for each k ≥ 3 and for every bipartite graph. Also, Theorem 1.1 holds true for such colorings.

Also, a large value of b alone cannot guarantee that some ergodic b-cautious chain can be designed for sampling uniformly from C k (G) for each bipartite G and k. This is shown in the following proposition. (vi) The lower bound on s in Corollary 5.3 is close to optimal within a multiplicative factor of O(ln k). This is because if s ≤ (6/11)k (or equivalently, k ≥ (11/6)s), then for every G with ∆(G) ≤ s, the 1-cautious chain Glauber Dynamics is ergodic and mixes rapidly as shown by [START_REF] Vigoda | Improved bounds for sampling colorings[END_REF].

Proof: Let b 1 = ⌈b/2⌉ and b 2 = ⌊b/2⌋. H has two partite sets L and R defined by

L = {u i,j : 1 ≤ i ≤ k, 1 ≤ j ≤ b 1 }, R = {v i,j : 1 ≤ i ≤ k, 1 ≤ j ≤ b 2 }
There is an edge between u i,j and v i ′ ,j ′ if and only if i = i ′ . H is bipartite and has n vertices. Consider a k-coloring C of H defined as C(u i,j ) = C(v i,j ′ ) = i for any i, j, j ′ . For any u i,j , if we try to change its color to some i ′ = i, then it forces each v i ′ ,j ′ to take a color i ′′ = i ′ . This further changes the colors of at least ⌈b/2⌉ vertices in L. Hence, at least b vertices are forced to change their colors. Hence h(C, C ′ ) ≥ b for every C ′ = C. Thus, there is no b ′ -cautious (b ′ < b) chain irreducible on C k (H). ✷ Fact 6.1 does not weaken the statement of Theorem 1.1. It only shows that there are bipartite graphs for which less powerful chains cannot be ergodic. Theorem 3.1, on the other hand, looks at some graphs for which such less powerful but ergodic chains exist and show that they do not mix rapidly. However, it is very likely that there are O(n/k)-cautious chains (on k-colorings) which are ergodic on all or almost all bipartite graphs.

Examples of colorings admitting cautious ergodic chains

In this section, we provide some explicit examples of colorings which admit ergodic chains that are 1cautious and which can be shown (as in Theorem 1.1) to have exponential mixing time.

Example

Let C 1,k+1 (G) be the set of all (k + 1)-colorings of G = (A ∪ B, E) such that (i) color 1 is used only for vertices of A, (ii) color k + 1 is used only for vertices of B and (iii) color 2 through k are used for vertices of both A and B.

Let H be the complete bipartite graph on X = {u 1 , . . . , u k }∪Y = {v 1 , . . . , v k } minus the near perfect matching {(u 2 , v 2 ), . . . , (u k , v k )}. It can be seen that sampling uniformly from C 1,k+1 (G) is equivalent to sampling uniformly from C H (G, X, Y ) where

C H (G, X, Y ) = {c ∈ C H (G) | c(A) ⊆ X, c(B) ⊆ Y }.
This is seen from the following bijection which maps a c ∈ C H (G, X, Y ) to the coloring

c -1 (u 1 ), c -1 ({u 2 , v 2 }), c -1 ({u 3 , v 3 }), . . . , c -1 ({u k , v k }), c -1 (v 1 )) .
One can derive negative results (similar to Theorem 1.1) on sampling from C H (G, X, Y ). The proof is essentially the same as the proof of Theorem 1.1. For i = 2, . . . , k, define α i and

β i by |A ∩ c -1 (u i )| = α i n and |B∩c -1 (v i )| = β i n. Also, let α 1 = |A∩c -1 (u 1 )|/n and β 1 = 0 and let β k+1 = |B∩c -1 (v 1 )|/n
and α k+1 = 0. Note that β 1 and α k+1 are forced to be zero always. Now, as in Theorem 1.1, we can define γ and δ suitably and show that the conductance of the set S is exponentially small. We leave the details to the reader. This shows that Theorem 1.1 applies to the ergodic cautious chains for sampling from C 1,k+1 (G).

The result of applying the procedure CLOSURE(H) (described in Section 3 of [START_REF] Cooper | On Markov chains for randomly H-colouring a graph[END_REF]) is a complete unlooped bipartite graph. Hence it follows from [START_REF] Cooper | On Markov chains for randomly H-colouring a graph[END_REF] (Theorem 3) that the 1-cautious chain Glauber dynamics is ergodic for all bipartite G and is uniform on the space C 1,k+1 (G). The Glauber dynamics for a H-coloring is a 1-cautious chain which tries at each step to re-color at random a single randomly chosen vertex. By the afore-said arguments, GD has exponential mixing time for G ∈ G(n, n, p).

Example

In general, for 0 ≤ a ≤ k, let C a,k (G) denote the set of all k-colorings of G = (A ∪ B, E) such that (i) colors 1 through a are used only for vertices of A, (ii) colors ka + 1 through k are used only for vertices of B and (iii) colors a + 1 through ka are used for vertices of both A and B.

Let H be the complete bipartite graph on X = {u 1 , . . . , u k-a } ∪ Y = {v a+1 , . . . , v k } minus the matching {(u a+1 , v a+1 ), . . . , (u k-a , v k-a )}. It can be seen that sampling uniformly from C a,k (G) is equivalent to sampling uniformly from C H (G, X, Y ) where

C H (G, X, Y ) = {c ∈ C H (G) | c(A) ⊆ X, c(B) ⊆ Y }.
This is seen from the following bijection which maps a c ∈ C H (G, X, Y ) to the coloring c -1 (u 1 ), . . . c -1 (u a ), c -1 ({u a+1 , v a+1 }), . . . , c -1 ({u k-a , v k-a }), c -1 (v k-a+1 ), . . . , c -1 (v k )) .

Just as in Example 7.1, one can derive negative results on sampling using cautious chains. The proof is again essentially the same as the proof of Theorem 1.1. Also, Glauber dynamics is ergodic for such H-colorings also.

Example

Suppose H is the complete graph plus just one loop. The preceding arguments also show that our torpid mixing results can be applied to H-colorings for this specific H. This is because if H is the complete graph on V = {1, 2 . . . , k} with a self-loop on vertex 1, then any H-coloring X 1 , . . . X k of G = (A ∪ B, E) can be thought of as a standard (k + 1)-coloring Y 1 , . . . Y k+1 of G where

Y 1 = X 1 ∩ A, Y k+1 = X 1 ∩ B, Y i = X i ∀i = 2, . . . , k.
This mapping establishes a bijection between C H (G) and C 1,k+1 (G) defined before. Hence, the negative results of Theorem 1.2 apply to this specific H. Also, the Glauber dynamics chain is ergodic in this case (follows from Theorem 2, [START_REF] Cooper | On Markov chains for randomly H-colouring a graph[END_REF]).

Conclusions

An interesting open problem is to design efficient samplers for k-colorings (k ≥ 3) of bipartite graphs? An affirmative answer would lead to efficient randomized approximate counters for this case. The results of this paper indicate that such samplers may have to use tools other than Markov chains.

It seems very likely that the negative results obtained can be extended to k-colorings of l-colorable (l ≥ 3) graphs where l < k = O(n δ ) for some positive δ which depends only on l. Finding a k-coloring is N P -hard for any fixed k ≥ 3 except for some special classes like bipartite graphs, chordal graphs, etc. Even if we ignore the complexity of finding a starting state, the previous remark shows that markov chains are not likely to be useful as efficient samplers.

It is known that approximate counting and almost uniform sampling problems are polynomial time reducible to each other provided k > ∆(G) (see [START_REF] Jerrum | A very simple algorithm for estimating the number of k-colorings of a low-degree graph[END_REF]). However, it would be interesting to see if this can be extended to k ≤ ∆(G) for some special classes of graphs. For example, this reduction works also for bipartite G and for any k ≥ 3. We can show this by a simple modification of the arguments of [START_REF] Jerrum | A very simple algorithm for estimating the number of k-colorings of a low-degree graph[END_REF]. But, we skip the proof of this observation since we present only negative results on efficiently sampling colorings of bipartite graphs. A related question is : Are there other classes of graphs where the equivalence is true for k ≤ ∆?

  β) with ||(γ, δ) -(α, β)|| 1 ≤ c 2 where (γ, δ) and c 2 are defined before. Here, ||(γ, δ) -(α, β)|| 1 denotes the L1-norm defined as 1≤i≤k |γ iα i | + |δ iβ i |. Similarly, define S 2 to be the set of all k-colorings whose corresponding vectors (α, β) satisfy ||(δ, γ) -(α, β)|| 1 ≤ c 2 . Both S 1 and S 2 are non-empty. Also, since ||(γ, δ) -(δ, γ)|| 1 = 2, it follows from triangle inequality of the L 1 metric that S 1 ∩ S 2 = ∅. Define S to be S 1 if |S 1 | ≤ |S 2 | and define S to be S 2 otherwise. It follows that Claim 3.1 |S| ≤ |Ω|/2.

  1. ✷ Proof: (of Claim 3.2 ) Let C i (A) denote the set of vertices in A colored (by C) with i. C i (B) is similarly defined. We can write h(C, D) = h A (C, D) + h B (C, D) where h A (C, D) and h B (C, D) denote respectively the contributions of A and B to h(C, D). We use ⊕ for the symmetric difference operation on sets. The claim follows from the following lower bound on h A (C, D) and a similar one for h B (C, D).

Theorem 3 . 1

 31 Let d, γ, k, G have the meaning stated in Theorem 1.1. Also, let n max G and n bd (G) have the meaning given in the proof of Theorem 1.1. Then, with probability at least 1e -n/(k 2 ln n) , n bd (G) < e -γn n max (G)

  where φ(α, β) = ψ(α, β) + a (α 1 β 1 + . . . + α k β k ).(iii) Hence if k ≤ n 1/3 and if φ(α, β) is bounded below by a positive constant, then what essentially determines the behavior of N G (α, β) (for large values of n) is the value of φ(α, β). As we will see later, this is indeed true for each (α, β) in our domain of interest. Analyzing φ, we get the following Theorem 3.2 Recall the assumptions mentioned and definitions of c 1 (k), c 2 (k), c 3 (k) and (γ, δ) stated in the proof of Theorem 1.1. Define a to be a = n ln(1p). It follows that |a| ≥ np ≥ 6k ln k. Then, for k ≥ 6,

Fact 6 . 1

 61 For every two positive integers k, b ≥ 2, there exists a bipartite graph H on n = kb vertices such that no b ′ -cautious (b ′ < b) chain is irreducible on C k (H). Hence no such chain is asymptotically uniform on C k (H).

Acknowledgements

We thank Eric Vigoda for the useful comments provided by him. We are also very grateful to the anonymous referee whose questions and comments prompted us to obtain the generalization to H-colorings (Subsection 1.2) and also to come up with explicit colorings admitting 1-cautious ergodic chains (Section 7).

† This research was partially supported by the EU ESPRIT LTR Project No. 20244 (ALCOM-IT), WP 3.3. 1365-8050