L Amgoud

C Cayrol

M C Lagasquie-Schiex

On the bipolarity in argumentation frameworks

In this paper, we propose a survey of the use of bipolarity in argumentation frameworks, i.e. the presence of two kinds of entities (a positive entity and a negative entity). An argumentation process follows three steps: building the arguments and the interactions between them, valuating the arguments using or not the interactions and finally defining the acceptability of the arguments. This paper shows on various applications and with some formal definitions that bipolarity appears (in some cases since always) and can be used in each step of this process under different forms.

Introduction

A rational agent can express claims and judgements, aiming at reaching a decision, a conclusion, or informing, convincing, negotiating with other agents. Pertinent information may be insufficient or contrastedly there may be too much relevant but partially incoherent information. And, in case of multi-agent interaction, conflicts of interest are inevitable. So, agents can be assisted by argumentation, a process based on the exchange and the valuation of interacting arguments which support opinions, claims, proposals, decisions, . . . The argumentation process has been applied in various domains and applications (see [START_REF] Fox | On using arguments for reasoning about values and actions[END_REF][START_REF] Parsons | Normative argumentation and qualitative probability[END_REF][START_REF] Amgoud | Arguments, Dialogue and Negociation[END_REF][START_REF] Parsons | Agents that reason and negociate by arguing[END_REF][START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF][START_REF] Gordon | The zeno argumentation framework[END_REF][START_REF] Verheij | On the existence and multiplicity of extension in dialectical argumentation[END_REF]).

More generally, when abstracting from the internal structure of the arguments, the fundamental characteristics of an argumentation framework is the presence of interactions between arguments. For instance, in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF])'s work, there only is one kind of interaction: a defeat relation between arguments. In some other works (see [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF][START_REF] Verheij | On the existence and multiplicity of extension in dialectical argumentation[END_REF]), there also exists another kind of interaction: a support relation.

This suggests a notion of bipolarity, i.e. the existence of two independent kinds of information which have a diametrically opposed nature and which represent repellent forces. This notion of bipolarity appears in many domains and it is essential in order to represent realistic knowledge (see discussions in [START_REF] Boutilier | Towards a logic for qualitative decision theory[END_REF][START_REF] Tan | Specification and evaluation of preferences under uncertainty[END_REF][START_REF] Lang | Utilitarian desires[END_REF][START_REF] Benferhat | Bipolar representation and fusion of preferences in the possibilistic logic framework[END_REF]). For instance, in [START_REF] Benferhat | Bipolar representation and fusion of preferences in the possibilistic logic framework[END_REF], the authors distinguish between two kinds of preferences: positive preferences (what the agent really wants) and negative preferences (what the agent rejects). This distinction between positive and negative preferences is supported by studies in cognitive psychology which have shown that these two types of preferences are independent and processed separately in the mind. Note that bipolarity is not always related to the notion of preference.

So, the purpose of this paper is to present a survey on the use of bipolarity in argumentation frameworks.

The first section is devoted to the background about abstract argumentation frameworks. Then, the outline of this paper follows the structure of the argumentation process which can be viewed under the form of three steps:

1. the building of the arguments and, using the structure of the arguments, the definition of different interactions between arguments. An argument can take different forms depending on the domain, but it is generally required to be a structured set of linked propositions or claims. This step has a bipolar aspect illustrated with some applications.

2. the valuation of these arguments which can be based only on the interactions between arguments, or can also take into account an intrinsic strength for each argument. The resulting valuation can be crisp or gradual. In this step, the bipolarity appears on the form of the interactions between arguments (support and defeat relations between arguments). We present different formal approaches which take into account this bipolar aspect.

3. the selection of some arguments using the definition of the acceptability. In this step, different classes of arguments can be distinguished with different levels of acceptability, and the valuation results can be used in order to define these levels. The bipolar aspect of this step is illustrated by some examples.

The abstract framework developed by Dung

Abstracting from the structure of the arguments (so, after the step 1 of the argumentation process), in [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] Dung has studied the interactions between arguments. However, his work has focused only on the defeat relation between arguments. We briefly recall that abstract framework (it will be extended in the section devoted to the valuation process):

An argumentation framework is a pair <A, R> of a set A of arguments and a binary relation R on A called a defeat relation. A i RA j means that A i defeats A j . The notion of defence is defined from the notion of defeat by: an argument A i defends A j against B iff BRA j and A i RB. In Dung's framework, only the selection step of an argumentation process is taken into account1 . In this work, the acceptability of an argument depends on its membership of some sets (acceptable sets or extensions) characterised by particular properties. It is a collective acceptability. The main characteristic properties are:

Conflict-free: a subset S of A is conflict-free iff there exist no A i , A j in S such that A i RA j . Defends collectively: a subset S of A defends collectively an argument A i iff for each argument B, if BRA i there exists C in S such that CRB.

Then several semantics for acceptability have been defined by [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]:

Admissible: a subset S of A is an admissible set iff S is conflict-free and S defends collectively all its elements. Preferred: a subset S of A is a preferred extension iff S is maximal for the set inclusion among the admissible sets of A.

Grounded: a subset S of A is the grounded extension iff S is the least fixed point of the characteristic function

F of <A, R> (F : 2 <A,R> → 2 <A,R> with F (S) = {A such that A is defended collectively by S}).
These semantics are used in the selection step of the argumentation process and, sometimes, they are associated with the results of the valuation step (see for example (Cayrol & Lagasquie-Schiex 2003a)). They will be used in the section devoted to the selection process.

Bipolarity at the argument level

In an argumentation process some arguments are constructed in favour of a conclusion and others are constructed against that conclusion (called also defeaters). One might say that arguments are presented in a bipolar way since arguments in favour of a conclusion can be considered as positive and arguments against the conclusion as negative ones. In some sense this is true since the two kinds of arguments have different and opposite roles. However, generally these arguments are defined and handled in the same way. Within the negotiation framework, various natures of arguments have been distinguished in (Amgoud & Prade 2004a): instrumental arguments, explanatory arguments, treats and rewards. For each nature of argument, only one definition is proposed (for supporting or attacking) a conclusion. Let's consider the case of explanatory arguments. Explanations constitute the most common category of arguments. In classical argumentation-based frameworks which have been developed for handling inconsistency in knowledge bases, each conclusion is justified by arguments. They represent the reasons to believe in the conclusion. Such arguments have a deductive form. Indeed, from premises, a conclusion is entailed. Let L be a propositional language. ⊢ denotes classical inference and ≡ denotes logical equivalence. Let K = {k j ; j = 1, . . . , l} be a base representing the available knowledge of an agent with k j are formulas of L.

Definition 1 (Explanatory argument) An explanatory argument is a pair <H, h> such that:

H ⊆ K. H ⊢ h.
H is consistent and minimal (for set inclusion) among the consistent sets H satisfying the two previous items. H is the support of the argument and h its conclusion.

Example 1 Let K = {p, p → b, p → ¬f, b → f } where p means penguin, b means bird, f means fly. Let H = {p, p → b, b → f }, H ′ = {p, p → ¬f
} be two subsets of K. The fact that p flies is justified by the explanatory argument < H, f >. However, the conclusion f has a counter-argument which is < H ′ , ¬f >.

In the case of argumentation-based decision, things seem different. In [START_REF] Amgoud | Towards argumentationbased decision making: A possibilistic logic approach[END_REF] the decisions are based on the comparison of arguments and counterarguments which are defined in different ways. The idea is that a decision is justified if it leads to the satisfaction of some desires. Let D = {d i ; i = 1, . . . , m} represent the desires of the decision-maker and D e be a set of decisions. Arguments against a decision, however, show clearly that desires will not be satisfied by that decision. Formally:

Definition 3 (Argument against a decision) An argument against a decision is a triple

A = <S, C, d> such that: d ∈ D e S ⊆ K and C ⊆ D S ∪ {d} is consistent ∀ g i ∈ C, S ∪ {d} ⊢ ¬g i
S is minimal and C is maximal (for set inclusion) among the sets S and C satisfying the four previous items. S = Support(A) is the support of the argument and C = Consequences(A) its consequences (the desires which are not satisfied by the decision d).

Example 2

The example is about taking an umbrella or not, knowing that the sky is cloudy. The knowledge base is K = {u → ¬w, r ∧ ¬u → w, c, ¬r → ¬w, c → r} with: r: it rains, w: being wet, u: taking an umbrella, c: the sky is cloudy. The base of desires is D = {¬w, ¬u}. There is one argument in favour of the decision "u": <{u → ¬w}, {¬w}, u> and one argument against the decision "u": <∅, {¬u}, u>.

Note also that the above two arguments are handled in different ways. In (Amgoud & Prade 2004a), it has been showed that the use of arguments in favour of a decision is sufficient to capture the results of the pessimistic criteria defined in [START_REF] Dubois | Possibility theory as a basis for qualitative decision theory[END_REF] in qualitative decision making. Whereas, the use of arguments against a decision allows us to capture the results of the optimistic criteria.

Valuation in a bipolar argumentation framework

In the basic argumentation context recalled in the first section, only one kind of interaction is explicitly represented by the defeat relation. Within that framework, several approaches have been proposed for valuating the arguments, using or not the defeat relation2 , see for example [START_REF] Krause | A logic of argumentation for reasoning under uncertainty[END_REF][START_REF] Parsons | Normative argumentation and qualitative probability[END_REF][START_REF] Prakken | Argument-based extended logic programming with defeasible priorities[END_REF][START_REF] Jakobovits | Robust semantics for argumentation frameworks[END_REF][START_REF] Besnard | A logic-based theory of deductive arguments[END_REF]Cayrol & Lagasquie-Schiex 2003b;[START_REF] Amgoud | Contribution à l'intégration des préférences dans le raisonnement argumentatif[END_REF].

In this context, the support of an argument A by another argument B can be represented only if B defends A in the sense of [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF]. So, this support is a dependent notion of the defeat relation. It is not necessary a bad thing (many systems use this approach), but we are interested in modelling situations where two independent kinds of interactions are available: a positive and a negative one (see for example in the medical domain the work [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF]). So, following [START_REF] Karacapilidis | Computer supported argumentation and collaborative decision making: the HERMES system[END_REF][START_REF] Verheij | On the existence and multiplicity of extension in dialectical argumentation[END_REF], we propose a new argumentation framework: an abstract bipolar argumentation framework and an associated valuation procedure.

An abstract bipolar argumentation framework

An abstract bipolar argumentation framework is an extension of the basic argumentation framework introduced by [START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] in which we use a new kind of interactions between arguments: the support relation which represents the support, the help brought by some arguments to other arguments3 . This new relation is assumed to be totally independent of the defeat relation. So, we have a bipolar representation of the interactions between arguments.

Formal definition of an abstract bipolar argumentation framework An abstract bipolar argumentation frame

- work <A, R def , R sup > is a set A of
A i and A j ∈ A, A i R def A j (resp. A i R sup A j ) means that A i defeats A j (resp. A i supports A j ).
A bipolar argumentation framework is called wellfounded if and only if there is no infinite sequence A 0 , A 1 , . . . , A n , . . . such that ∀i, A i ∈ A and A i+1 RA i with R = R def or R sup .

Here, we are not interested in the structure of the arguments and we consider arbitrary defeat and support relations. The only assumption is that R def and R sup are independent of each other.

Notations Consider

A ∈ A, AR def B is represented by A → B and AR sup B is represented by A → B. The set {A i ∈ A|A i R def A} is denoted by R def -(A) and the set {A i ∈ A|AR def A i } is denoted by R def + (A).
In the same way, we define R sup

-(A) and R sup + (A). <A, R def , R sup > defines a directed graph G b called the bipolar graph. Example 3 The framework <A = {A 1 , A 2 , A 3 , A 4 }, R def = {(A 2 , A 3 ), (A 4 , A 3 ), (A 1 , A 2 )}, R sup = {(A 2 , A 4 ), (A 1 , A 3 )}>
A ∈ A such that R def -(A) = ∅ and R sup -(A) = ∅.

Path in the bipolar graph

A path from A to B is a sequence of arguments P = A 1 -. . . -A n such that A = A 1 , A 1 R 1 A 2 , . . . , A n-1 R n-1 A n , A n = B, and ∀i = 1, . . . , n -1, R i = R def or R sup .
The length of the path is n -1 (the number of edges that are used in the path) and will be denoted by l P . The defeat number of the path (resp. support number of the path) is the number of

R i = R def (resp. R i = R sup )
and will be denoted by n def (P) (resp. n sup (P)).

A homogeneous path from A to B is a path in which all the R i are the same. So, we can have homogeneous defeat paths or homogeneous support paths.

The set of the paths from A to B will be denoted by P(A, B).

Branch for an argument

A path from A to B is a branch for B iff A is a leaf of G b .
We assume that the bipolar graph is acyclic. We propose the notions of direct and indirect defeaters and defenders 4 , completed with the notion of direct and indirect supporters. Note that negative information (defeat edges) is considered as having priority over positive information (support edges). So, we do not have symmetrical definitions for indirect defeaters/defenders and indirect supporters 5 : Definition 5 (Direct/Indirect Defeaters/Defenders of an argument) Consider A ∈ A:

The direct defeaters of A are the elements of R def -(A).

The direct defenders of A are the direct defeaters of the elements of R def -(A).

The indirect defeaters of A are the elements A i defined by: ∃P ∈ P(A i , A) such that n def (P) = 2k + 1, with k ≥ 0 and A i is not a direct defeater. The indirect defenders of A are the elements A i defined by: ∃P ∈ P(A i , A) such that n def (P) = 2k, with k ≥ 1 and A i is not a direct defender.

Definition 6 (Direct/Indirect supporters of an argument)

Consider A ∈ A:

The direct supporters of A are the elements of R sup -(A).

The indirect supporters of A are the elements A i defined by: ∃P ∈ P(A i , A) such that n sup (P) = l P ≥ 2.

Remarks and examples

In a bipolar argumentation framework, the support relation carries positive information while the defeat relation carries negative information, and positive and negative information are represented in the same structure (the bipolar graph). It is a particularity of the argumentation context (in many other domains, positive and negative information are represented in two distinct frameworks, and sometimes they do not have the same nature).

We present below two illustrative examples.

Example 4 During a discussion between reporters about the publication of an information I concerning the person X, the following arguments are presented: A: I is an important information, we must publish it. B: I concerns the person X, X is a private person and we can not publish an information about a private person without her agreement, and X does not agree with the publication. C: X is a minister, so X is a public person, not a private person. D: X has resigned, so X is no more a minister. E: her resignation has been refused by the chief of the government.

lent: in (Dung 1995)'s work, direct defeaters (resp. defenders) are also indirect defeaters (resp. defenders) which is not true in our definitions. 5 As soon as the path Ai -A contains at least one defeat edge, it defines Ai as an indirect defeater or defender for A ! Contrastedly, an indirect supporter Ai for A excludes defeat edges in the path Ai -A. This illustrates that bipolarity is well represented by the relations defeat and support while no bipolarity exists with the relations defeat and defend.

F : I concerns a problem of public health, so I is an important information.

B E C D A F In this example, B is a direct defeater of A, F is a direct supporter of A, C is a direct defender of A, D is an indirect defeater of A and E is an indirect defender of A.

Example 5 During a discussion between doctors about the installation of a prosthesis on the patient X, the following arguments are presented:

A: X has difficulties for walking, we must install a prosthesis. B: the installation of a prosthesis needs a surgical operation with an anaesthesia which is very risked for the patient. C: we can use a local anaesthesia, so there is no more risk. D: a surgical operation presents also important risks of post-infections. E: there are more and more kinds of nosocomial infections in the hospital and it is very difficult to cure them. F : the classical treatments (injections) are unable to cure X's knee problem.

Gradual valuation in a bipolar argumentation framework

In the context of a bipolar argumentation framework, the valuation follows the same principles that have already been described in (Cayrol & Lagasquie-Schiex 2003b) completed with new principles corresponding to the "support" information. Here, we propose two kinds of valuations: a local valuation in which the value of an argument only depends on the values of the direct defeaters or supporters of this argument. a global valuation in which the value of an argument represents the set of all the branches leading to this argument.

Local valuation in a bipolar argumentation framework

Let v be a local gradual valuation in a bipolar argumentation framework, v must respect the following principles: Pl1 The valuation of an argument is a function of its direct defeaters and of its direct supporters. Pl2 If the quality of the support (resp. defeat) increases then the value of the argument increases (resp. decreases). Pl3 If the quantity of the supports (resp. defeats) increases then the quality of the support (resp. defeat) increases.

In the respect of these principles, we propose the following formal definition for a local gradual valuation.

Definition 7 Let <A, R def , R sup > be a bipolar argumentation framework. We assume that there exists a completely ordered set V with a minimum element (V Min ) and a maximum element (V Max ).

Consider

A ∈ A with R def -(A) = {B 1 , . . . , B n } and R sup -(A) = {C 1 , . . . , C p }. A local gradual valuation on <A, R def , R sup > is a function v : A → V such that v(A) = g(h sup (v(C 1 ), . . . , v(C p )), h def (v(B 1 ), . . . , v(B n ))) with: the function h def (resp. h sup ): V * → H def (resp. V * → H sup ) 6
valuating the quality of the defeat (resp. support) on A. the function g : H sup ×H def → V with g(x, y) increasing on x and decreasing on y.

The function h, h = h def or h sup , must respect the following constraints:

if x i ≥ x ′ i then h(x 1 , . . . , x i . . . , x n ) ≥ h(x 1 , . . . , x ′ i . . . , x n ), h(x 1 , . . . , x n , x n+1 ) ≥ h(x 1 , . . . , x n ), h() = α ≤ h(x 1 , . . . , x n ), for all x 1 , . . . , x n 7 , h(x 1 , . . . , x n ) ≤ β, for all x 1 , . . . , x n 8 .
Note that the definition 7 produces a generic local gradual valuation. There exist several instances for this generic valuation. One of them is the following:

V = [-1, 1] interval of reals, H def = H sup = [0, ∞[ interval of reals, h def (x 1 , . . . , x n ) = h sup (x 1 , . . . , x n ) = Σ n i=1 xi+1 2 , g(x, y) = 1 1+y -1 1+x .
So, we have α = 0, β = ∞ and g(α, α) = 0 9 . On the example 4, we obtain v(A) = 1 15 . On the example 5, we obtain v(A) = -1 6 . Note that the functions h def and h sup represent the two axes of an unipolar bivariate scale 10 Then, with the function g, we obtain a bipolar univariate scale 11 . So, after using g, we can not distinguish the case "balance between defeats and supports" and the case "no defeat and no support".

Global valuation in a bipolar argumentation framework

In the global approach, we have also some principles:

Pg1

The value of an argument is a function of all the branches leading to this argument in the bipolar graph.

Pg2

The set of the branches leading to this argument is partitioned in three parts, each part corresponding to a kind of "effect" on the argument (there are only three "effects", so we have the defeat part, the defence part, the support part).

Pg3

The improvement of the defence or the support parts or the degradation of the defeat part of an argument leads to an increase of the value of this argument.

Pg4

The improvement of the defeat part or the degradation of the defence or the support parts of an argument leads to a decrease of the value of the argument.

Here, the main problem is: how to determine the "effect" of a branch leading to the argument ? There exist different methods and each of them leads to a kind of global valuation. Here, we will present only one of these methods.

On the example 4, E -D -C -B -A is a defence branch for A and F -A is a support branch for A. In the example 5, C -B -A is a defence branch for A, E -D -A is a defeat branch for A and F -A is a support branch for A.

Using this definition, we can define the value of the argument under the form of three values (one for each part evoked in the principles -defeat part, defence part, support part of the set of the branches leading to the argument). These values must represent all the branches leading to the argument and having the same effect. So, following the encoding used in (Cayrol & Lagasquie-Schiex 2003b) in the case of a basic argumentation framework, we can consider each value as a tuple of informations (one information for each branch). In (Cayrol & Lagasquie-Schiex 2003b), these informations were only the lengths of branches, but here, it is more complex because of the mix of support edges and defeat edges in a same branch. So, one idea is to encode the description of the branch under the form of a sequence of bits (1 for a defeat edge and 0 for a support edge). With this encoding, it is very easy to distinguish defeat/defence branches and support branches.

In [START_REF] Cayrol | Bipolarité en argumentation[END_REF], the reader can find the complete definitions of these three tupled-values and some comparison algorithms on these values respecting the proposed principles.

Note that, although there are three tupled-values per each argument, we have an unipolar bivariate scale, because the defence-value and the defeat-value are used together "against" the support-value.

Note also that, with the global approach, we can distinguish the case "balance between defeats and supports" and the case "no defeat and no support".

Bipolarity in the selection of the acceptable arguments

Bipolarity appears also when defining the acceptability of arguments, even in the case of a basic argumentation framework 12 . In fact, using the Dung's framework, an argumentation process should return three categories of arguments:

The class of acceptable arguments. Beliefs or goals or decisions supported by such arguments are really justified.

In the case of handling inconsistency in knowledge bases, beliefs supported by such arguments will be inferred from the base. Similarly, goals supported by such arguments will be pursued by the agent.

The class of rejected arguments. For example, goals supported only by such arguments will be rejected by the agent even if they can be achieved. Decisions supported by such arguments will be discarded and beliefs supported by such arguments will not be inferred from the knowledge base.

The class of arguments in abeyance. Such arguments are neither acceptable nor rejected.

Depending on the nature of the arguments and the application which is considered, two kinds of bipolarity can be distinguished when defining the acceptability of arguments. In the first one, the two classes of rejected arguments and arguments in abeyance are defined on the basis of the class of acceptable arguments. For example, in the case of handling inconsistency in knowledge bases, the grounded extension (introduced in the first section) may be used to define the acceptable arguments.

Definition 9 An argument is acceptable if it belongs to the grounded extension and an argument is rejected if it is attacked by an acceptable argument.

In the second kind of bipolarity, the classes of acceptable and rejected arguments are defined separately and the class of arguments in abeyance is deduced from these two classes. We illustrate this kind of bipolarity in a particular application where we try to compute the intentions of an agent from its contradictory desires (see [START_REF] Amgoud | A formal framework for handling conflicting desires[END_REF] for more details).

Let L be a propositional language, an agent is supposed to be equipped with a base D of desires, a belief base Σ containing the plans to carry out in order to achieve the desires (we are not interested in the way in which these plans are generated), and finally a base C integrity constraints. D contains literals of L. The elements of D represent the initial desires of the agent. For example, an agent may have the following desires: to finish a publication, to go to a dentist, etc... Note that the set D may be inconsistent. This means that an agent is allowed to have contradictory desires.

Σ contains rules having the form ϕ 1 ∧. . .∧ϕ n → h where ϕ 1 , . . ., ϕ n , h are literals of L. Such a formula means that the agent believes that if he realizes ϕ 1 , . . ., ϕ n then he will be able to achieve h. C contains formulas of L. They represent a kind of integrity constraints.

A desire is any element of D. A desire h may have subdesires. For example, the desire of "going on a journey to central Africa" may have two sub-desires which are: "getting the tickets" and "being vaccinated". The sub-desire "getting the tickets" may have itself the two following subdesires: "having a friend who may bring the tickets" and "passing to an agency". Definition 10 (Desire/Sub-desire) Let us consider an agent equipped with the bases <D, Σ, C>.

1. D is the set of the desires of the agent. 2. SubD is the set of the sub-desires of the agent: A literal h ′ ∈ SubD iff there exists a rule ϕ 1 ∧h ′ . . .∧ϕ n → h ∈ Σ with h ∈ D or h ∈ SubD. In that case, h ′ is a sub-desire of h.

As noted above, an agent may have one or several ways to achieve a given desire. We bring the two notions together in a new notion of partial plan. Definition 11 (Partial plan) A partial plan for h is a pair a = < h, H > such that:

h is a desire or a sub-desire.

H = {ϕ 1 , . . . , ϕ n } if there exists a rule ϕ 1 ∧ . . . ∧ ϕ n → h ∈ Σ, H = ∅ otherwise.
The function Desire(a) = h returns the desire or sub-desire of a partial plan a and the function Support(a) = H returns the support of the partial plan. ℵ will gather all the partial plans that can be built from <D, Σ, C>.

Note 1 A desire may have several partial plans.

Note 2 Let a = < h, H > be a partial plan. Each element of the support H is a sub-desire of h.

Definition 12 A partial plan a = < h, H > is elementary iff H = ∅.
A partial plan shows the actions that should be performed in order to achieve the corresponding desire (or sub-desire). However, the elements of the support of a given partial plan are considered as sub-desires that must be achieved at their turn by another partial plan. The whole way to achieve a given desire is called a complete plan. A complete plan for a given desire d is an AND tree. Its nodes are partial plans and its arcs represent the sub-desire relationship. The root of the tree is a partial plan for the desire d. It is an AND tree because all the sub-desires of d must be considered. When for the same desire, there are several partial plans to carry it out, only one is considered in a tree. Formally: Definition 13 (Complete plan) A complete plan g for a desire h is a finite tree such that: h ∈ D and the root of the tree is a partial plan <h, H> . A node <h ′ , {ϕ 1 , . . ., ϕ n }> has exactly n children <ϕ 1 , H ′ 1 >, . . ., <ϕ n , H ′ n > where <ϕ i , H ′ i > is a partial plan for ϕ i . The leaves of the tree are elementary partial plans.

The function Root(g) = h returns the desire of the root. The function N odes(g) returns the set of all the partial plans of the tree g. G denotes the set of all the complete plans that can be built from the triple <D, Σ, C>. The function Leaves(g) returns the set of the leaves of the tree g.

In [START_REF] Amgoud | A formal framework for handling conflicting desires[END_REF], it has been shown that partial plans may be conflicting for several reasons. These different kinds of conflicts are brought together in a unique relation of conflict defined as follows:

Definition 14 (Conflict) Let a 1 and a 2 be two partial plans of ℵ. a 1 conflicts with a 2 iff: {Desire(a 1 ), Desire(a

2 )} ∪ Support(a 1 ) ∪ Support(a 2 ) ∪ C ∪ Σ ⊢ ⊥.
More generally, a set of partial plans may be conflicting.

Definition 15 Let S ⊆ ℵ. S is conflicting iff a∈S ({Desire(a)} ∪ Support(a)) ∪ C ∪ Σ ⊢ ⊥.
Since partial plans may be conflicting, two complete plans may be conflicting too.

Definition 16 (Attack) Let g 1 , g 2 ∈ G. g 1 attacks g 2 iff ∃a 1 ∈ N odes(g 1 ) and ∃a 2 ∈ N odes(g 2 ) such that a 1 conflicts with a 2 .

More generally we are interested in sets of complete plans such that there is no conflict between their nodes. Formally: Definition 17 (Conflict-free) Let S ⊆ G. S is conflict-free13 iff:

[ g∈S [ a∈ N odes(g) (Support(a) ∪ {Desire(a)})] ∪ C ∪ Σ ⊢ ⊥]. If S = {g}, then we say that the complete plan g is conflict-free. Obviously a desire which has no conflict-free complete plan will be called unachievable. This means it is impossible to carry out such a desire. Definition 18 (Unachievable desire) A desire d is unachievable if ∄ g ∈ G s.t Root(g) = d and g is conflict-free.

From the preceding definitions, we can now present the formal system for handling conflicting desires of an agent. Definition 19 (System for handling desires) Let's consider a triple <D, Σ, C>. The pair <G, Attack> will be called a system for handling desires (SHD). A SHD has the same features as an argumentation framework [START_REF] Amgoud | A reasoning model based on the production of acceptable arguments[END_REF]. Inspired by previous work on argumentation theory, we will define acceptable sets of complete plans. Then we will be able to partition the set G into three categories thus meeting again the notion of bipolarity in the selection step:

1. The acceptable set(s) of complete plans. They contain the good plans to achieve their corresponding desires. These desires will become the intentions of the agent.

2. The class of rejected complete plans. These are the selfattacked ones. 3. The class of complete plans in abeyance which gathers the complete plans which are neither good nor rejected.

We give below the semantics of "acceptable sets of complete plans". Definition 20 Let <G, Attack> be a SHD and S ⊆ G. S is an acceptable set of complete plans iff: S is conflict-free and S is maximal (for set inclusion).

Conclusion

This paper presents a comprehensive survey of the use of bipolarity in argumentation frameworks. Indeed, it shows that bipolarity may be used at different levels of an argumentation process. However, this depends broadly on the considered application.

When constructing arguments, for instance, we have shown that in some situations bipolarity does not appear at all. It is the case in argumentation-based inference systems where arguments are constructed in favour of and against a given conclusion. Even if the two kinds of arguments play different roles, their logical definitions are similar. In argumentation-based decision, things seem different since two kinds of arguments are built and handled differently: arguments in favour of a decision and arguments against a decision. In this case, arguments are bipolar.

At a meta level, we can say that we have arguments in favour of other arguments (the support relation) and also arguments against other arguments (the defeat relation).

These bipolar relations between arguments may be used in order to define the strengths of arguments. So, in this case, we propose an extension of Dung's framework: an abstract bipolar argumentation framework. Finally, the result of an argumentation process may be presented in a bipolar way: acceptable arguments, rejected arguments (the arguments in abeyance being derived from the two previous classes). Here, like in the building of arguments, the bipolarity really appears when we choose acceptable arguments and rejected arguments with two distinct processes.

In all the levels, underlying or introducing bipolarity permit an enrichment and an improvement of the power of the argumentation process and reflects the need of bipolar informations in many real applications (see many discussions about this subject [START_REF] Boutilier | Towards a logic for qualitative decision theory[END_REF][START_REF] Tan | Specification and evaluation of preferences under uncertainty[END_REF][START_REF] Lang | Utilitarian desires[END_REF][START_REF] Benferhat | Bipolar representation and fusion of preferences in the possibilistic logic framework[END_REF]).

The future works will be the complete study of:

the abstract bipolar argumentation framework (in particular, the definition of acceptability in this framework), the links between bipolarity in argumentation and other kinds of bipolarity in different domains (in particular in knowledge representation).

  Elements of D and D e are formulas of L. Definition 2 (Argument for a decision) An argument in favour of a decision is a triple A = <S, C, d> such that: d ∈ D e S ⊆ K and C ⊆ D S ∪ {d} is consistent S ∪ {d} ⊢ C S is minimal and C is maximal (for set inclusion) among the sets S and C satisfying the four previous items. S = Support(A) is the support of the argument and C = Consequences(A) its consequences (the desires which are reached by the decision d).

  defines the following graph G b with the root A 3 : representation of a bipolar argumentation framework) Let G b be the bipolar graph associated with the abstract bipolar argumentation framework <A, R def , R sup >, we define: Leaf of the bipolar graph A leaf of G b is an argument

  , B and D are direct defeaters of A, F is a direct supporter of A, C is a direct defender of A and E is an indirect defeater of A.

  arguments, a binary relation R def on A called a defeat relation and another binary relation R sup on A called a support relation: consider

However, some notions proposed by Dung can be used in the valuation of arguments (see(Cayrol & Lagasquie-Schiex

2003b)).

So, the value of an argument may depend on its interactions with the other arguments, or may depend on an intrinsic strength of the argument which can be defined for example by an explicit preference.

If the support relation is removed, we retrieve Dung's framework.

The notions introduced here are inspired by related definitions first introduced in[START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] but are not strictly equiva-

V * denotes the set of the finite sequences of elements of V . H def and Hsup are ordered sets.

So, α is the minimal value for a defeat (resp. a support)ı.e. there is no defeat (resp. no support) -.

So, β is the maximal value for a defeat (resp. a support)i.e. for example, if there is an infinity of direct defeaters (resp. supporters) -.

The definition of acceptability in the case of a bipolar argumentation framework remains to be studied.

Note that this notion is not the same one which is defined by[START_REF] Dung | On the acceptability of arguments and its fundamental role in nonmonotonic reasoning, logic programming and n-person games[END_REF] and recalled in the first section.

Definition 8 (Defeat, defence and support branches for an argument) Let A be an argument.

Defeat (resp. defence) branch for A A branch for

A is a defeat branch (resp. defence branch) iff the longest homogeneous path leading to A of this branch is an homogeneous defeat path whose length is an odd integer (resp. even integer). Support branch for A A branch for A is a support branch iff the longest homogeneous path leading to A of this branch is an homogeneous support path.

9 Note that h def (x1, . . . , xn, xn+1) ≥ h def (x1, . . . , xn) because

, 1] (and the same for hsup). We have also h def () = hsup() = α, α being the minimal value of [0, ∞[, and β being the maximal value of [0, ∞[. We can verify also that g(α, β) = g(0, ∞) = -1 and that g(β, α) = g(∞, 0) = 1 (1 and -1 being respectively V Min and V Max ).

10 It is the first kind of representation of bipolar informations: each information is independent and corresponds to a specific axe. So, we can distinguish the case "there are no information positive and no information negative" and the case "there are as much information positive as information negative".

11 It is the second kind of representation of bipolar informations: both informations are joined and the result corresponds to only one axe. So, it will be difficult to distinguish the case "there are no information positive and no information negative" and the case "there are as much information positive as information negative", because generally the result of the join is the same in the both cases.


Claudette Cayrol

Marie-Christine Lagasquie-Schiex

On the Complexity of Non-Monotonic Entailment in Syntax-Based Approaches

Keywords:

The purpose of this paper is to outline various results regarding the computational complexity of nonmonotonic entailment in di erent syntax-based approaches. Starting from a (non necessarily consistent) belief base E and a pre-ordering on E, we rst remind di erent mechanisms for selecting preferred consistent subsets in syntax-based approaches. Then we present di erent entailment principles in order to manage these multiple subsets.

The crossing point of each generation mechanism m and each entailment principle p de nes an entailment relation (E; ) j p;m which we study from the computational complexity point of view. The obtained results are not very encouraging since the complexity of all these non-monotonic entailment relations is, even in the most restricted languages, larger than the complexity of monotonic entailment.

Introduction

Formalizing \common sense" reasoning is one of the most important research topics in arti cial intelligence. When the available knowledge may be incomplete, uncertain or inconsistent, the classical logic is no more relevant (for example, anything can be classically inferred from inconsistent knowledge bases). Non-monotonic reasoning is needed. Many researchers have proposed new logics (called non-monotonic logics) in order to formalize non-monotonic reasoning, for instance, Reiter's default logic Rei80]. Others proposed to keep the classical logic but with numerical or symbolic structures for ordering the beliefs. These ordering relations, called priority relations, may be de ned:

either in a semantical way, re ecting logical dependence between beliefs, as the epistemic relevance ordering of G ardenfors G ar91];

or in a syntactical way, considering each belief as a distinct piece of information (it will be accepted or rejected as a whole) as in Neb91].

In this paper, we are concerned with non-monotonic entailment (deductive aspect of reasoning) from a syntactical belief base equipped with symbolic ordering structures, a so called strati ed belief base. In the following, we consider only syntax-based entailment (cf. Bre89, Neb91, CRS92, BCD + 93] for works in the same framework). Following Pinkas and Loui's analysis PL92], it is convenient to see non-monotonic syntax-based entailment as a two-steps procedure which rst generates and selects preferred belief states (generation mechanism) and then manages these multiple states in order to conclude using classical logic (con ict resolution principle). For instance, the inference considered in BCD + 93] is de ned by \E infers i is classically inferred in all the preferred consistent subsets of E". A taxonomy of con ict resolution principles, from credulous to skeptical ones, can be found in PL92]. The selection of preferred subsets relies upon the de nition of aggregation modes which enable to extend the priority ordering de ned on the initial belief base into a preference relation between subsets (see BCD + 93, CRS92]).

In the framework described above, our purpose is to propose a comparative study of various syntax-based entailment relations from the point of view of the computational complexity. This topic is essential for practical applications. Indeed, as far as we know, only few papers have been devoted to computational complexity issues for non-monotonic reasoning. Nebel has thoroughly considered the computational complexity of syntax-based revision procedures Neb91]. Eiter and Gottlob Got92, EG92] have also considered the case of default logic and abductive procedures. The paper is organized as follows. Starting from a belief base E and a pre-ordering on E, we rst present three mechanisms for selecting preferred consistent subsets of E, each one being a more selective re nement of the previous one. Then we present three entailment principles in order to manage these multiple subsets: the skeptical principle, the argumentative principle and the credulous principle. The crossing point of each generation mechanism m and each entailment principle p de nes an entailment relation (E; ) j p;m for which we study the computational complexity. Results are also provided in the two restricted cases of a strictly ordered belief base and of a Horn base.

Selecting preferred belief states

Throughout the paper, E denotes a non-empty nite set of propositional formulae referred to as the \belief base". E is not assumed to be consistent. The most usual idea for handling inconsistency is to work with maximal (w.r.t. set-inclusion) consistent subsets of E, called theses of E.

De nition 1 A subset X of E is a thesis of E i X is consistent and there is no consistent subset of E which strictly contains X. Unfortunately, in the worst case, this approach is not selective enough: too many theses must be taken into account. Now, we assume that E is equipped with a complete pre-ordering (a priority relation). It is equivalent to consider that E is strati ed in a collection (E 1 ; : : :; E n ) of belief bases, where E 1 contains the formulae of highest priority (or relevance) and E n those of lowest priority. The pair (E; ) is called a prioritized (or equivalently strati ed) belief base. Each E i is called a stratum of E. Di erent approaches have been proposed to use the priority relation in order to select \preferred" subsets (see CLS93] for a survey). For the purpose of this paper, we concentrate on the approaches which re ne the set-inclusion and lead to select preferred subsets among the theses of E. Indeed, the priority relation on E induces a preference relation on the set of subsets of E. Let us rst brie y remind the \inclusion-based" preference, which is the most frequently encountered, despite di erent presentations.

De nition 2 Let E = (E 1 ; : : :; E n ) a strati ed belief base. Z being a subset of E, Z i denotes Z \ E i . The \inclusion-based" preference is the strict ordering dened on the power set of E by: X Incl Y i there exists i such that Y i strictly contains X i and for any j < i, X j = Y j .

Note that Incl -preferred theses are also called preferred sub-theories in Bre89], democratic preferred 1 in CRS92], and exactly correspond to strongly maximal-consistent sub-bases in DLP91].

Another way of selecting preferred subsets is to use consistent subsets of maximum cardinality (see BCD + 93, Leh92]).

De nition 3 A subset X of E is a cardinalitymaximal-consistent subset of E i X is consistent and for each consistent subset Y of E, jY j jXj (with jY j denotes the cardinality of Y ). Taking into account the strati cation of E leads the de nition of the so-called \lexicographic" preference BCD + 93]:

De nition 4 Let E = (E 1 ; : : :; E n ) a strati ed belief base. The \lexicographic" preference is the strict ordering de ned on the power set of E by: X Lex Y i there exists i such that jX i j < jY i j and for any j < i, jX j j = jY j j.

It can be shown that the lexicographic preference re nes the inclusion-based preference: any Lexpreferred consistent subset of E is an Incl -preferred thesis, but the converse is false as illustrated at the end of this section. Moreover, the associated lexicographic pre-ordering is complete.

Syntax-based entailment principles

As mentioned in the introduction of this paper, nonmonotonic entailment from a given belief base can be viewed as a two steps procedure which rst generates \preferred" belief states, and then manages these different belief states according to cautiousness principles.

In the previous section, we have presented three mechanisms for producing a set of consistent belief states from the initial prioritized belief base (E; ). In the following, we call T the mechanism which produces the set of theses of E (maximal-consistent subsets), Incl the mechanism which produces the inclusionbased preferred theses of E and Lex the re nement which produces the set of preferred theses for the lexicographic ordering.

A taxonomy of numerous entailment principles has been established by Pinkas and Loui PL92] according to their boldness or cautiousness. Here, we are interested in three of them which we now brie y present: We start from a set of consistent subsets of E denoted by m(E) in the following (for instance, m is one of the generation mechanisms T, Incl, Lex). Let be a propositional formula.

De nition 5 is inferred from m(E) according to the skeptical entailment principle i can be classically inferred from each element of m(E). This entailment principle, often called strong consequence or universal consequence in the literature, will be denoted by j 8 and referred to as the Uni principle in the following.

De nition 6 is inferred from m(E) according to the credulous entailment principle i can be classically inferred from at least one element of m(E). This entailment principle, often called weak consequence or existential consequence in the literature, will be denoted by j 9 and referred to as the Exi principle in the following.

These two entailment principles are the most commonly activated in presence of multiple con icting belief states. Obviously, the Uni principle is more cautious than the Exi principle, since each conclusion obtained from m(E) by Uni inference is also obtained by Exi inference. An intermediary principle consists in keeping only the weak consequences whose negation cannot be inferred (see BDP93] for a discussion on the so-called argumentative inference).

De nition 7 is inferred from m(E) according to the argumentative entailment principle i is classically inferred from at least one element of m(E) and no element of m(E) can classically entail : . This entailment principle will be denoted by j A and referred to as the Arg principle in the following.

We are now ready to give a precise de nition of the entailment relations and the associated problems which we will consider from the computational complexity point of view. Each one appears at the crossing point of a belief state generation mechanism m and an entailment principle p. Let (E; ) be the initial belief base and a propositional formula.

De nition 8

The problem Uni-T (resp. Exi-T, Arg-T) is de ned by \verify that is a strong (resp.

weak, argumentative) consequence of E using the theses of E". The T generation mechanism is used. Notation: E j 8(resp. 9;A);T for Uni-T (resp. Exi-T, Arg-T).

In the above notation, it is su cient to mention E instead of (E; ) since producing the theses makes no use of the pre-ordering on E.

De nition 9

The problem Uni-Incl (resp. Exi-Incl, Arg-Incl) is de ned by \verify that is a strong (resp. weak, argumentative) consequence of E using the inclusion-based preferred theses of E".

The Incl generation mechanism is used. Notation:

(E; ) j 8(resp. 9;A);Incl for Uni-Incl (resp. Exi-

Incl, Arg-Incl).
The inclusion-based preference is induced by the preordering (def. 2).

De nition 10

The problem Uni-Lex (resp. Exi-Lex, Arg-Lex) is de ned by \verify that is a strong (resp. weak, argumentative) consequence of E using the lexico-preferred theses of E". The Lex generation mechanism is used. Notation: (E;

) j 8(resp. 9;A);Lex for Uni-Lex (resp. Exi-Lex, Arg-Lex).

The lexicographic preference is induced by the preordering (def. 4).

Example Applying the above principles on the example of the previous section produces:

(E; ) j 8;Incl b (E; ) j 9;Incl nl (E; ) j A;Incl ci (E; ) j 8;Lex np which is equivalent to (E; ) j 9;Lex np and (E; ) j A;Lex np since there is only one lexico-preferred subset.

About complexity

This section is an informal and simpli ed presentation of complexity theory. For more precisions, see for instance GJ79]. The purpose of complexity theory is to classify problems from the point of view of computational complexity, in the worst case. The complexity may be temporal or spatial.

In this paper, we are interested only by the temporal aspect and only for decision problems (each of its instances has either a \yes" or a \no" answer).

The P class contains the problems which are solved eciently (in polynomial time in the size of its instances). These problems are called polynomial or deterministic polynomial.

However, there are many problems for which we can neither prove that there is a polynomial algorithm which solves them nor that there is none. Because of this limitation, the NP class has been introduced. A problem belongs to the NP class (non-deterministic polynomial) if, to each instance I of the problem whose answer is \Yes" (and only for these instances !), it is possible to associate a polynomial certi cate C(I) which enables an algorithm A to verify that the answer is really \Yes" in polynomial time. Intuitively, NP is the class of problems for which it is easy to verify that a potential solution is a real solution. Therefore, Sat (satis ability of a set of clauses C) is in NP because it is su cient to \guess a truth assignment M", this can be done with a polynomial succession of choices (one for each variable of C), then to \verify that M is a model of C", which is done in polynomial time. Note that NP contains P, determinism being a particular case of non-determinism. Then, among the NP problems, the hardest problems called NP-complete problems have been de ned. These problems Q are de ned by the fact that they belong to NP and all the NP problems Q 0 may be e ciently transformed into Q. This polynomial transformation is denoted by Q 0 / Q and informally means that Q is at least as hard as Q 0 . Sat is NP-complete as well as many problems in logic and in operation research. No e cient algorithm is known (at present) for the NP-complete problems. So, we have the essential conjecture of the complexity theory: NP 6 = P. Finding one single polynomial time algorithm for any NP-complete problem would make this conjecture false. Beside this NP class, we nd the co-NP class corresponding to the complementary problems of the NP problems (the \yes" and \no" answers have been exchanged). The complementary problem of an NPcomplete problem is co-NP-complete. Therefore, Un-sat (unsatis ability of a set of clauses) is a co-NPcomplete problem. We will also use the classes of the polynomial hierarchy (called PH), each of them containing supposedly harder and harder problems. This PH is de ned inductively using the notion of oracle. An oracle of complexity X may be viewed as a subroutine which solves any problem of complexity X. Each call to an oracle is counted as one time unit. So, there are polynomial problems using an oracle of complexity X and non-deterministic polynomial problems using an oracle of complexity X. They de ne respectively the P X and NP X classes.

Complexity of general entailment relations

We consider entailment relations of the form (E;

) j p;m where E, , p and m have been de ned in the previous sections, and where is a single propositional formula. The complexity results for the general case are given in table 1. For lack of space, we just give sketches of proof. Most of the detailed proofs are given in CLS93].

For each problem Q, the complexity proof is done in two steps: rst, we exhibit an algorithm which solves Q and whose complexity class is X (

Class membership for strong relations: For

Uni-T and Uni-Incl, we use the results of Nebel in Neb91], because these entailment relations correspond to the Sbr and Pbr revision procedures for which Nebel has proved the p 2 -completeness. Therefore, Uni-T and Uni-Incl belong to the class p 2 . For Uni-Lex, a very interesting phenomena appears. Let (E; ) a strati ed base and a propositional formula, we consider the function f: f((E; )) = (f ! `g E f:`g; ) where `is a new propositional variable (`does not appear in E). The pre-ordering is extended so that the rst stratum of f((E; )) is composed of the single formula ( ! `) and the last stratum of f((E; )) is composed of the single formula (:`). Using f, both Uni-Lex and co-Uni-Lex can be polynomially transformed to Exi-Lex and co-Uni-Lex can be polynomially transformed to Uni-Lex. Therefore, we have the following algorithm:

1. E 0 f ! `g E f:`g 2. k < 0; 0; : : : ; 0 > (*k: array of dimension n=number of strata in E 0 *) 3. For ns from 1 to n do 4. nf number of formulae in the stratum E 0 ns 5. End? false 6. while (nf 0) and (not End?) do 7.

k ns] nf 8.

if Max-Gsat-Array(E 0 ; k) then End? true else nf nf 1 9. Verify that k n] 6 = 1

In this algorithm, we use an oracle Max-Gsat-Array de ned by: Instance: a pre-ordered set (Y; ) of propositional formulae, an array k of dimension n with n=number of strata in Y .

Question: Is there a truth assignment which satis es for each stratum i of Y at least k i] formulae ? This problem is NP-complete (NP class membership is obvious, completeness is proven by restriction to Sat). Therefore the previous algorithm (and its dichotomic version too) is deterministic polynomial and uses a non-deterministic polynomial oracle. So, Uni-Lex belongs to the class p 2 .

Completeness for strong relations: For Uni-T and Uni-Incl, the completeness is still proven using the Sbr and Pbr revision procedures (see Neb91]).

For Uni-Lex, we prove p 2 -completeness using a p 2complete problem de ned in EG93] and referred to as Alm in the following (instance: C = fC 1 ; : : :; C m g a satis able set of clauses, X = fx 1 ; : : :; x n g the set of propositional variables of C, O(X) =< x 1 ; : : :; x n > a prioritization of X, question: does V M , the truth assignment lexicographically maximal with respect to O(X) satisfying C, ful ll V M (x n ) = true ?). Consider the following polynomial transformation from Alm to Uni-Lex: let \C = fC 1 ; : : :; C m g satis able, X = fx 1 ; : : :; x n g, O(X) =< x 1 ; : : :; x n >" an instance of Alm, the instance of Uni-Lex is de ned by = x n and (E; ) = fC 1 ^: : : ^Cm ; x 1 ; : : :; x n g with the following ordering: the formula C 1 ^: : : ^Cm has greater priority than the formula x 1 which has greater priority than the formula x 2 which has greater priority than . .. the formula x n . Therefore Alm / Uni-Lex and Uni-Lex is p 2 -complete.

Class membership for weak relations: For the Exi-m problems (8m 2 fT; Incl; Lexg), we may consider the following algorithm:

1. Guess a subset Y of (E; ) 2. Verify that Y is:

-a thesis (for Exi-T) -an inclusion based preferred thesis (for Exi-Incl) -a lexicographic preferred thesis (for Exi-Lex)

Verify that Y classically entails

First of all, note that \verify that Y classically entails " is co-NP-complete. Then, \verify that Y is a thesis" consists only in checking Y consistency and checking Y fgg inconsistency for each formula g 2 E n Y . For inclusion based preferred thesis, the same principle applies except that the veri cation must be done stratum per stratum. Therefore, the previous algorithm is nondeterministic polynomial and uses non-deterministic polynomial time oracles. Therefore, Exi-T and Exi-Incl belong to the class NP NP = p 2 . For \verify that Y is a lexicographic preferred thesis", we have to rely on an oracle which solves the following problem (called Max-Gsat-Strict):

Instance: a set Y of propositional formulae, an integer k jY j. Question: Is there a consistent subset Y 0 of Y such that jY 0 j > k ?

This problem is NP-complete (NP class membership is obvious, completeness is proven by restriction to Sat). Therefore, this algorithm is non-deterministic polynomial and relies on non-deterministic polynomial time oracles. Therefore, Exi-m belongs to the class NP NP = p 2 .

Completeness for weak relations: For Exi-T, we consider the following polynomial transformation from 2-Qbf to Exi-T: let \9a8bH(a; b)" be an instance of 2-Qbf, we consider the instance of Exi-T de ned by E = fa 1 ; : : :; a n ; :a 1 ; : : :; :a n g and = H(a; b) 1 .

For Exi-Incl, the completeness is obvious, since Exi-T is a restriction of Exi-Incl.

For Exi-Lex, we may use the previous proof for Exi-T since any thesis of E, when E is of the form E = fa 1 ; : : :; a n ; :a 1 ; : : :; :a n g is also a lexicographic preferred thesis of E.

Class membership for argumentative relations: 8m 2 fT; Incl; Lexg, the Arg-m problems can be solved by the following algorithm:

1. Verify that (E; ) j 6 9;m : 2. Verify that (E; ) j 9;m This algorithm is deterministic polynomial and uses a p 2 oracle solving Exi-m. Therefore, we conclude that 8m, Arg-m belongs to the class P p2 = p 3 .

Completeness for argumentative relations: We haven't proven p 3 -completeness for any of these problems, but we re ne the class membership, as in Neb91]. Indeed, we prove that the most of Arg-m problems are in p 3 ( p Gottlob de ne an abductive problem A: instance: P = (V; H; M; T) a propositional abduction problem with V a set of propositional variables, H a set of hypotheses (propositional atoms), M a set of manifestations (propositional formulae), T a consistent theory (propositional formulae), question: is there an explanation to P ? This problem may be transformed to Exi-T by the following transformation:

E = T H and = M.
instance of co-Exi-T, simply consider the function g de ned by g(E) = E f: g and g( ) = : . Therefore, both Exi-T and co-Exi-T can be polynomially transformed to Arg-T. Since Exi-T is p 2complete and co-Exi-T is p 2 -complete, assuming that Arg-T2 ( p 2 p 2 ) would lead to p 2 = p 2 . For Arg-Incl, we still rely on the fact that Arg-T is a restriction of Arg-Incl: Arg-T / Arg-Incl. Since Exi-T / Arg-T and co-Exi-T / Arg-T, we obtain the same conclusion as for Arg-T. For Arg-Lex, similarly as for Arg-T, it is possible to prove that Exi-Lex / Arg-Lex. However, we haven't found a polynomial transformation from co-Exi-Lex (or any other p 2 -complete problem) to Arg-Lex. We simply conclude by saying that Arg-Lex is p 2 -hard.

Complexity of restricted entailment relations

In this section, we consider two possible restrictions of the problems previously considered 2 . First we assume that the belief base is completely and strictly ordered.

In that case E is strati ed with exactly one formula per stratum. In the second case, we suppose that E and are restricted to Horn clauses.

The complexity of the problems p-T (for p in fUni, Exi, Argg) is not a ected by the rst restriction since the pre-ordering on the belief base is not taken into account by the generation mechanism T. We will show that all the other problems become equivalent to a single problem called 1/Stratum. As for the second restriction, both Sat and the entailment problem in classical propositional logic become polynomial.

Strati ed bases with one formula per stratum

Proposition 1 Let < be a complete and strict ordering on E. There is only one inclusion based preferred thesis, which is also the only lexicographic preferred thesis (proof in CLS93]).

Corollary This algorithm (and its dichotomic version too) is deterministic polynomial and relies on an NP-complete oracle. Therefore, 1/Stratum is in p 2 .

Completeness for 1/Stratum: Using the same transformation as in the proof of Uni-Lex, we prove that 1/Stratum is p 2 -complete, since the belief base E considered in that transformation is a strictly ordered base.

Horn clauses language

The belief base is a nite set of conjunctions of propositional Horn clauses and the formula is also a conjunction of Horn clauses. The complexity results are given in the table 3. Once again, the lexicographic based problems are quite speci c: their complexity seems unchanged in case of Horn clauses while all the other problems shift down by one level in the polynomial hierarchy. Completeness for m = T: For Uni-T-Horn, we use an idea previously proposed in EG92]:

Sat / co-Uni-T-Horn (Sat is the satis ability problem for any set of clauses, not only Horn clauses). Let C = fC j g for j 2 f1; : : :; qg a given set of clauses, let V (C) = fx 1 ; : : :; x n g the set of propositional variables used in C, take: E = fP; x 1 ; : : :; x n ; y 1 ; : : :; y n ; :z 1 ; : : :; :z n ; :sg and = :s where y 1 ; : : :; y n ; z 1 ; : : :; z n ; s are new propositional variables and where P is the formula:

(z 1 : : :z n ! s) q ĵ=1 C j y] n î =1

((:x i _ :y i ) ^(y i ! z i ) ^(x i ! z i ))

where C j y] denotes the result of replacing every positive literal x i by the negative literal :y i in C j . This transformation allows to transform any instance of Sat (using any type of clause) into an instance of co-Uni-T-Horn (using only Horn clauses). Therefore, co-Uni-T-Horn is NP-complete and Uni-T-Horn is co-NP-complete.

For Exi-T-Horn, we use the previous transformation, except that is taken equal to s. For Arg-T-Horn, we can not keep the Arg-T proof, because our polynomial transformations from Exi-T to Arg-T and from co-Exi-T to Arg-T do not preserve Horn clauses. We have to consider a new problem (called Exi-T-Horn-Pos):

Instance: E a Horn base, `a positive literal. Question: Is it true that E j 9;T `? It is clear that this problem is NP-complete (see the Exi-T-Horn proof). Therefore, we may use the polynomial transformations de ned for Arg-T on Exi-T-Horn-Pos and co-Exi-T-Horn-Pos. We conclude that Arg-T-Horn is in p 2 (NP co-NP) if NP 6 = co-NP.

Class membership and completeness for m = Incl: We may use the algorithms previously considered in the unrestricted case. All the polynomial transformations we used preserve Horn clauses and we conclude that Uni-Incl-Horn is co-NP-complete, Exi-Incl-Horn is NP-complete and Arg-Incl-Horn is in p 2 (NP co-NP) if NP 6 = co-NP. Class membership for m = Lex: For these problems, we used two oracles: one for Sat and one for Max-Gsat-Strict or Max-Gsat-Array. The rst problem becomes polynomial when restricted to Horn clauses, but the other problems (called Max-Horn-Sat-Strict and Max-Horn-Sat-Array) remain NP-complete. NP-membership is obvious, NPcompleteness is proven for Max-Horn-Sat-Strict using the following polynomial transformation: let \C a collection of n clauses with at most 2 literals per clause and an integer k n" be an instance of Max-2Sat which is NP-complete GJ79]. Simply consider the instance of Max-Horn-Sat-Strict de ned by the collection C 0 of Horn clauses composed of (and only of):

the Horn clauses of C unchanged;

for each of the p non-Horn clauses c = (`_ `0) 2 C, the three Horn clauses f`, `0, (:`_ :`0)g.

and the integer k 0 = k + p 1. For Max-Horn-Sat-Array, we use Max-Horn-Sat-Strict which can be polynomially transformed to Max-Horn-Sat-Array.

Completeness for m = Lex: For Uni-Lex-Horn, we prove p 2 -completeness using a p 2 -complete problem de ned in EG93] and referred to as Acm in the following (instance: C = fC 1 ; : : :; C m g a set of clauses, X = fx 1 ; : : :; x n g the variables of C, k 2 f1; : : :; mg an integer, question: does every truth assignment V cardinal maximal of X, ful ll V (C k ) = true ?). Consider the following polynomial transformation from Acm to Uni-Lex-Horn: let \C = fC 1 ; : : :; C m g, X = fx 1 ; : : :; x n g, k" an instance of Acm, the instance of Uni-Lex-Horn is de ned by = C k y] ^s and (E; ) = fP 1 ; : : :; P m ; x 1 ; : : :; x n ; y 1 ; : : :; y n ; :z 1 ; : : :; :z n ; :sg where y 1 ; : : :; y n ; z 1 ; : : :; z n ; s are new propositional variables and where each P j is the formula:

(z 1 : : :z n ! s) ^Cj y] n î =1 ((:x

i _ :y i ) ^(y i ! z i ) ^(x i ! z i ))
where C j y] denotes the result of replacing every positive literal x i by the negative literal :y i in C j , and where the ordering between formulae of E is the following: P 1 ; : : :; P m have greater priority than x 1 ; : : :; x n ; y 1 ; : : :; y n which have greater priority than :z 1 ; : : :; :z n ; :s. Therefore, we have Acm / Uni-Lex-Horn.

For Exi-Lex-Horn and for Arg-Lex-Horn, we have neither proved completeness nor re ned the class membership result.

Conclusion

We have studied the computational complexity of various syntax-based entailment relations which can be de ned as: (E; ) j p;m . E denotes a set of beliefs, a priority relation on E, a propositional formula, and p, m enable to combine the classical entailment and the selection of preferred consistent subsets. A similar study has been done for other entailment relations in CLS93] (when is the Best-out ordering DLP91], when the preferred subsets are Extensions of default logic Rei80, Got92]). The results reported in this paper show that most of the non-monotonic entailment problems have very likely exponential time complexity with respect to the problem size. Although the complexities observed are limited by the third level of the PH, they are prohibitive and applications may likely wait for an answer for hours, days or centuries ! We have considered two restrictions (strictly ordered belief base, Horn base), but none of them has lead us to a polynomialproblem, eventhough these restrictions are rather strong. Note that the computational complexity is not related of cautiousness: though Arg-m is more cautious than Exi-m and less cautious than Uni-m, Arg-m is more complex than Exi-m and Uni-m. A more complete analysis permits to distinguish the Uni-Lex entailment, whose complexity never leaves the second level of the polynomial hierarchy ( p 2 , NP, co-NP). Paradoxically, Uni-Lex complexity is not a ected by the strongest restriction considered (Horn clauses) when most of the other entailment relations complexities shift down by one level. These results should not prevent us from using the considered formalisms: complexity is already a problem for classical logic (entailment is co-NP-complete), however recent algorithms have obtained interesting results (see results of Gsat in LMS92]) ; we may hope that faster and faster massively parallel machines will lead to further enhancements, although it is not obvious; nally, these results concern worst case, and there are, hopefully, many problems that should be much easier to solve. However, in order to use these formalisms on practical applications, we think it is necessary to identify speci c useful restrictions, or even approximations (numerical or not) of these problems that can be e ciently solved. The next step of our comparative study will concern logical properties of non-monotonic syntax-based entailment relations such as rational monotony for instance (see KLM90, G ar91, GM94] for a catalog of entailment relations properties). A similar study has been reported in BCD + 93], but only for the Uni entailment principle.

  these classes, we also have the notion of completeness (a p k+1 -complete problem is harder than a p k or a p k+1 problem, 8k 0). The conjecture NP 6 = P is generalized to the PH with the following stronger conjectures: NP 6 = co-NP and 8k; p k 6 = p k . Note that NP = P implies that the PH collapses into P. The problem stated below, called 2-Qbf et denoted by 9a8bH(a; b), is an example of a p 2 -complete problem (see Joh90, Neb91]).Instance: a propositional formula H(a; b) where a and b denote sets of propositional variables: a = fa 1 ; : : :; a n g and b = fb 1 ; : : :; b m g Question: Is there a truth assignment of the variables in a such that H(a; b) is true for any truth assignment of the variables in b ?

  Complexities in case of Horn clausesClass membership for m = T: We may still use the previously stated algorithms. Using the fact that the complexity of the entailment problem is reduced, we conclude that Uni-T-Horn is in co-NP, Exi-T-Horn is in NP and Arg-T-Horn is in p 2 .

Table 1 :

 1 Complexities in the general case then, we prove that Q is X-complete by giving a polynomial transformation from an X-complete problem to Q (or else give any other lower bound for the complexity).

	class membership proof which gives an upper bound for the complexity);

  1 The problems Uni-Incl (resp. Lex),

	Class membership for 1/Stratum: Consider the following algorithm for solving 1/Stratum:
	1. X ? 2. ns 1 (current stratum) 3. if X En s is consistent then X X En s 4. ns ns + 1 5. if ns = (total number of strata in E) then verify that X classically entails else go to step 3
	Exi-Incl (resp. Lex), Arg-Incl (resp. Lex) are equivalent to a single problem called 1/Stratum.
	The complexity of the problem 1/Stratum is given in table 2.
	Problem 1/Stratum Table 2: Complexities in the restricted case \one for-Complexity class p 2 -complete mula per stratum"
	2 When E and are CNF formulae (conjunctive normal form), the complexity results remain unchanged.

p 2 ). For Arg-T, we proved that there is a polynomial transformation from Exi-T to Arg-T: let (E; ) be an instance of Exi-T. Simply consider the function f de ned by f(E) = E f ! `g where `is a new propositional variable (`does not appear in E) and f( ) = `. Furthermore, there is a polynomial transformation from co-Exi-T to Arg-T: let (E; ) be an 1 This result is not surprising. In EG93],Eiter and

Acknowledgements

We would like to express our thanks to Daniel Lehmann and Bernhard Nebel for their helpful suggestions, and Michel Cayrol and Thomas Schiex for their constructive readings of our work.


Félix-A Lebel

João Pedro Trovão

Loïc Boulon

Ali Sari

Serge Pelissier

Pascal Venet

Generating Lithium-Ion Cell Thermodynamic Efficiency Maps

In lithium-ion cells, heat is generated via joules losses and exothermic electro-chemical reactions, causing cells to self-heat and risk premature aging or catastrophic failure. However, heat generation is not constant throughout the cells discharge, due to the complex chemical reactions and changes in the micro structure of the active materials of the electrodes. Nonlinear or complex systems thermodynamic behavior is commonly represented by efficiency maps, generated from empirical data. These empirical models are used to estimate a system heat generation at a given operating state. Although very common in many fields of engineering, efficiency maps are yet to be used for lithium-ion batteries. This paper presents a simple method to achieve accurate estimation of thermodynamic efficiency over the full range of use. In this method, the thermodynamic losses are assumed to be proportional to the measured ohmic resistance of the cell. This empirical method is intended to be a fast and reliable characterization tool that can replace other modeling methods, while capturing the non-linear nature of lithium-ion cells. It can be used for energy management and assessment purposes, for battery design or for thermal management system sizing and control.

INTRODUCTION

Nowadays, electric vehicles (EVs) represent an increasing market share of vehicles sold world wide. Battery powered EVs are seen as the most suited technology to reduce green house gas emissions in transportation, alongside fuelcells [START_REF] Van De Kaa | The battle between battery and fuel cell powered electric vehicles: A bwm approach[END_REF]. The overall energy efficiency of the powertrain of an EV is about 80%, meanwhile combustion engines have an efficiency ranging from 10% to 34% at best [START_REF] Laitinen | Improving electric vehicle energy efficiency with two-speed gearbox[END_REF], [START_REF] Prabhakar | Efficiency investigation for electric vehicle powertrain with variable dc-link bus voltage[END_REF]. This goes without considering the wasted energy and resources necessary to transformation and distribution of gasoline [START_REF] Pereirinha | Multiple energy sources hybridization: The future of electric vehicles?[END_REF]. Despite being mostly produced from fossil fuels today, electricity production from renewable sources is for-casted to increase, to nearly satisfy the global energy demand by 2050 [START_REF] Teske | Energy [r] evolution-a sustainable world energy outlook[END_REF].

Thermodynamic efficiency , η, is the ratio of the useful energy of a system to the total energy [START_REF] Heldson | Chapter one -energy[END_REF]. Knowing the thermodynamic efficiency of a system is useful to estimate its losses. It can be used for energy management or performance estimation purposes [START_REF] Pereirinha | Multiple energy sources hybridization: The future of electric vehicles?[END_REF], [START_REF] Trovao | Energy-and power-split management of dual energy storage system for a three-wheel electric vehicle[END_REF] . In the case of lithiumion batteries (LiBs), the stored energy gets mostly converted into heat and electricity. Some of the chemical reactions will release or absorb heat because of variations of the entropy of the materials [START_REF] Takano | Entropy change in lithium ion cells on charge and discharge[END_REF]. However these are not considered as losses, as they are reversible mechanisms.

The efficiency of certain simple systems can sometimes be assumed constant. Although it may be true for an operation point, thermodynamic efficiency of lithium-ion cells is not constant throughout its entire usage domain. Electrical properties of the cell are dependent of the reactions kinetics, temperature and state of charge (SOC). Indeed, the heat generation of LiBs is highly dependent on its SOC and current [START_REF]Sae j1312: Procedure for mapping engine performance-spark ignition and compression ignition engines[END_REF]. Efficiency over the entire operation domain of a complex or non-linear system can be represented in the form of two dimensional contour maps, known as efficiency maps. Electric motors [START_REF] Bojoi | Efficiency and loss mapping of ac motors using advanced testing tools[END_REF] or combustion engines [START_REF] Celik | Performance maps of a diesel engine[END_REF] performances are often mapped this way. Efficiency maps are good system level empirical models that can be used by engineers to solve various problems, such as optimization problems [START_REF] Gökce | An instantaneous optimization strategy based on efficiency maps for internal combustion engine/battery hybrid vehicles[END_REF], [START_REF] Demircal | Influence of the temperature on energy management in battery-ultracapacitor electric vehicles[END_REF] or component sizing [START_REF] Grunditz | BEV Powertrain Component Sizing with Respect to Performance, Energy Consumption and Driving Patterns[END_REF]. Few paper present an efficiency map for LiBs discharge [START_REF] Demircal | Influence of the temperature on energy management in battery-ultracapacitor electric vehicles[END_REF]. This paper provides a methodology to experimentally obtain them, as it seems to be missing from the literature.

The paper is structured as follows: Firstly, the experimental setup is presented at section I. Then, the proposed characterization method is exposed at section II. Section III presents a validation of the results, comparing computed values to measurements. Finally, conclusions are drawn at section ??.

I. EXPERIMENTAL SETUP

The lithium-ion cells tested used for this work have a Nickel manganese cobalt (NMC) positive electrode and graphite negative electrode. They are commercially available cylindrical 18650 cells of a measured capacity Q cell,nom of 2.90Ah. Their operational voltage ranges from 2.5V at a Depth of Discharge (DOD) of 100% to 4.2V at DOD = 0%. Commercially available cell holders with an intrinsic resistance of 20mΩ are used to hold the cells in place on the custom made circuit board, shown in Fig. 1. The positive and negative poles of the cell were connected to the output and sense terminals of programmable source/load, using the 4 wire method. The experiment was performed with an Arbin BT-2000.

The cell was placed in a climatic chamber at a temperature setpoint of 20 • C, for the entire duration of the experiment. Lower voltage limit was set at 2.5V during constant current discharge, as can be seen in Fig. 3. Each discharge was followed by a rest period of 30 minutes, to allow for cell temperature to cool down to ambient temperature T amb of 20 • C. A constant current (CC) recharge of 1.5A with an upper voltage limit of 4.2V (Fig. 3) then followed each discharge, with a constant voltage (CV) top off at a minimum current of 50mA, as recommended by the cell manufacturer. Again, recharge was followed by a 30 minutes rest time to allow for the cell to stabilize to T amb and voltage to relax.

A. Discharge potential

Fig. 4 shows the discharge voltage of the cell. From these, one can extract specifications such as capacity and internal resistance R cell . The dotted line on Fig. 4 is the pseudo open circuit voltage (pseudo-OCV) V 0 and is defined by 1, as the average between a low current charge (+250mA) and symmetric discharge (-250mA), assuming that the average of both voltages approximates to the open-circuit voltage of the cell at a given SOC or DOD. Hysteresis effects are also being neglected.

B. Internal resistance

The internal resistance R cell is the result of electrical conduction and ionic migration phenomenas. These include: resistivity of the current collector, resistivity of the active materials, ion transport in the electrolyte, among others. Ionic conductivity in the electrolyte depends of cell's temperature and reaction kinetics, i.e. the current flowing in the cell, leading to different ionic concentration gradient in the electrolyte [START_REF] Lievre | Practical online estimation of lithium-ion battery apparent series resistance for mild hybrid vehicles[END_REF], [START_REF] Tron | Enhanced ionic conductivity of the solid electrolyte for lithium-ion batteries[END_REF]. However, R cell (DOD, I) can be computed by a discretized Ohm's law, where dV is the drop of circuit voltage V (DOD, I) caused by current at a given DOD, from pseudo-OCV V 0 (DOD, I) (2). Fig. 5 shows R cell (DOD, I) in the form of a 3D mesh plot as a function of current and DOD, computed from the discharges presented at Fig. 4. The measured average internal resistance over the whole domain is 74mΩ. Internal resistance decreases as current increases, possibly because of the higher internal temperature, causing improvements in ionic migration in the electrolyte and improving the electrochemical reaction in general. Achieving iso-thermal conditions at high discharge rates can be quite challenging. Hence, this implies that this map is dependent on cooling conditions of the cell.

C. Electrical power

Two informations are necessary to compute the cells thermodynamic efficiency: electrical power and losses. One can estimate the useful power P max (DOD, I) with the maximum power transfer theorem (3), which is the maximum of ( 6) quadratic equation. Fig. 6 show the iso-power map of the cell as a function of DOD and current. One can see that in order for a cell to provide a steady power, the current has to increase an amount proportional to its drop in potential and corresponding internal resistance.

P max (DOD, I) = V 2 0 (DOD) 4R cell (DOD, I) (3)

D. Losses

Although entropy changes cause both heating or cooling of the cell, it is assumed in this work that heat losses are purely exothermic and caused by the internal resistance (or impedance) of the cell. While this may affect cell temperature, this hypothesis remains valid from a thermodynamic standpoint. Heat generation from the flow of electrons and ions in the cell can be computed by [START_REF] Pereirinha | Multiple energy sources hybridization: The future of electric vehicles?[END_REF].

Q(DOD, I) = R cell (DOD, I)I 2 (4)

E. Efficiency map computation

Thermodynamic efficiency η cell (DOD, I) during discharge of a cell (Fig. 8) is the ratio of P max (DOD, I) to the total power, given as the sum of P max (DOD, I) and Q(DOD, I), from a thermodynamical standpoint [START_REF] Teske | Energy [r] evolution-a sustainable world energy outlook[END_REF]. III. VALIDATION The useful power of the battery was measured during the characterization cycling schedule. This measured power was compared to the estimated power given by (6), by using the current measurements I meas and the calculated pseudo-OCV V 0 and R cell .

η cell (DOD, I) = P max (DOD, I) P max (DOD, I) + Q(DOD, I) (5)
P cell (DOD, I) = V 0 (DOD)I -R cell (DOD, I)I 2 (6)
Fig. 9 shows a very good match between the measured (plain) and calculated (dashed) discharge powers P cell for all tested currents. Fig. 9. Measured electric power (plain), estimated power (dashed) of the cell during discharge at various currents One can observe an error of less than 1% between the measure power and estimated power from the internal resistance, thus validating the method. The error is mainly caused by numerical interpolation and measurement noise. In order to validate the heat losses calculated from the internal resistance map, a temperature model could be implemented. The temperature from the model could then be compared to the measured temperature. However, this is intended for future works.

IV. CONCLUSION

The methodology provided in this paper can help develop research and engineering of lithium-ion batteries, by building empirical maps. Although the efficiency map obtained show a good match in terms of predicting output power, further work would be required to validate the heat losses. This would require to develop a thermal model of the cell for instance, which is planed for future works. However, transitory behavior due to the electrochemical kinetics are not considered in these maps. They should be considered for near steady-state purposes, as it may overestimate the internal impedance of a cell. For short current impulses, cell efficiency is likely to be better than what has been determined with the presented method, because the relaxation periods between pulses allow for lithium-ion concentration in the electrolyte to increase, thus making species more available during discharges. The empirical maps are good for cells of similar chemistry and same level of degradation. Efficiency maps are intended for system level engineering. For instance, they can be used to size a battery pack of an EV for a given operation point. Another application of these would be for power sharing strategies in hybrid vehicles, maximizing the overall fuel efficiency. A third possible usage of these maps could be to determine the operating temperature of a cell and use it to estimate the aging rate of a pack. Internal resistance and efficiency maps could also help in material research, studying the effect of discharge rate on chemical reaction kinetics. Similar methodology could apply to any electric energy storage devices, such as supercapacitors, lithium-ion capacitors, lead-acid batteries.

Fig. 1 .

 1 Fig. 1. Experimental setup

Fig. 2 .

 2 Fig. 2. Current profile

Fig. 3 . 1 )Fig. 4 .

 314 Fig. 3. Voltage response

R 2 )Fig. 5 .

 25 Fig. 5. Internal resistance map,

Fig. 6 .

 6 Fig. 6. Iso power [W] as a function of current and DOD

Fig. 7 .

 7 Fig. 7. Heat losses [W] function of current and DOD

Fig. 8 .

 8 Fig. 8. Efficiency [%] function of current and DOD

ACKNOWLEDGMENT This work was supported in part by Allcell Technologies, Canada Research Chairs Program, Natural Sciences and Engineering Research Council of Canada, and also developed with the support from "Service de Coopération et d'Action Culturelle du Consulat Général de France à Québec" under the Samuel De Champlain program.