Moral Planning Agents with LTL Values

1 Introduction

Evaluation is a core concept in cognitive theories of action [Gollwitzer, 1996], emotion [Moors et al., 2013], knowledge and beliefs [Abelson, 1979], and in the connection between epistemic and motivational attitudes [Miceli and Castelfranchi, 2000]. It is the operation of comparing the goodness or desirability of options from a given set of alternatives in relation to a set of goals. It also important for ethics where the philosophical doctrine of pluralistic consequentialism [Sen, 1985; Sen, 1987] and recent theories of reason-based choice [Dietrich and List, 2013; Dietrich and List, 2017] have emphasized its crucial role in decision-making. According to pluralistic consequentialism, a moral agent has to weigh different and sometimes conflicting values to assess the relative ideality of different alternatives. Evaluation also plays a pivotal role is some existing computational models of ethical deliberation and planning in robotics [Arkin et al., 2012; Vanderelst and Winfield, 2018] and in AI [Rodriguez-Soto et al., 2020; Serramia et al., 2018; Ajmeri et al., 2020; Cranefield et al., 2017]. More recently, it was also formalized in a multi-modal logic of values, knowledge and preferences [Lorini, 2021].

In this paper we study the role of evaluation in a novel multi-agent planning setting where agents share a set of ethical values expressed by formulas of linear temporal logic (LTL), ranked according to their priority. In particular, we focus on evaluation in the context of moral planning agents (MPAs). MPAs compare plans, which are either joint plans or individual plans, lexicographically with respect to their prioritized value base. A joint plan is a finite sequence of joint actions performed by a coalition of agents, while an individual plan is a finite sequence of individual actions performed by a single agent. The notion of joint plan is applicable whenever planning is delegated to a central planner which has to compute the optimal solution for all agents who will each execute their part of the joint plan on their own. Alternatively, the notion of individual plan is relevant for decentralized applications where agents do not know each other's plans.

In order for an agent to compare individual plans, it must consider all possible outcomes given the possible actions of the other agents. We study several evaluation criteria for individual plans: an optimistic (risk-seeking) criterion, a pessimistic (risk-averse) one, and criteria based on intrinsically ethical notions of responsibility. An optimistic agent compares individual plans by considering for each plan the bestpossible history that could result. A pessimistic agent considers only the worst-possible histories. Finally, an agent sensitive to anticipated blameworthiness will be concerned by the possible violation of some ethical values that it brought about (anticipated active blameworthiness) or that it could have prevented (anticipated passive blameworthiness). These two notions of blameworthiness rely on more primitive concepts of active and passive responsibility. Similar notions of optimism and pessimism have been been studied in the domain of qualitative decision theory [Brafman and Tennenholtz, 2018], while concepts of responsibility have been formalized in logical settings [Lorini et al., 2014], in causal models [Chockler and Halpern, 2004] and game-theoretic settings [Braham and van Hees, 2012; Lorini and M¨uhlenbernd, 2015; Lorini and M¨uhlenbernd, 2018]. However, to the best of our knowledge, the use of responsibility and blameworthiness in plan evaluation is novel.

The paper is organised as follows: Section 2 defines our model of multi-agent planning and introduces an illustrative example of our model in action. Section 3 describes how we evaluate joint plans and demonstrates this in our example. Section 4 focuses on individual plans, introducing and discussing optimistic and pessimistic comparison, as well as our notion of blameworthiness. Section 5 analyses the computational complexity of the comparison notions introduced in Section 4. Section 6 situates our paper in the wider fields of ethics in AI and planning, and compares our work to a number of similar papers. Finally Section 7 summarises the paper and suggests directions for future work.

2 The Model

In this section we introduce and define our planning framework for Moral Planning Agents. Our model is grounded on the logical theory of ethical choice presented by Lorini [2015], which is in turn based on situation calculus [Reiter, 2001]. We use a compact representation of values as formulas of linear temporal logic, in line with the work of Bienvenu et al. [2006] on preference-based temporal planning.

2.1 Agents, Actions, and Histories

Let Agt be a set of agents, and let Prop be a countable set of atomic propositions, defining a set of states S = 2Prop , with elements s, s′ , . . .. Let Act be a finite non-empty set of action names. Elements of Prop are noted p, q, . . ., while elements of Act are noted a, b, . . .. We also assume the existence of a special action skip.

We define a k-history to be a pair H = (Hst ,Hact ) with Hst : {0, . . . , k} -→ S andHact : Agt×{0, . . . , k-1} -→ Act. A history specifies the actual configuration of the environment (i.e., the state) at a certain time point and the actions executed by each of the agents that inform the next state. The set of k-histories is noted Histk. The set of all histories is Hist = ⋃k∈N Histk.

2.2 Multi-Agent Action Theory

To represent actions' effects and preconditions compactly, we use a multi-agent action theory inspired by situation calculus [Reiter, 2001] and developed by Lorini [2015].

Let LPL be the standard propositional language built from atomic formulas p for p ∈ Prop and do(i, a) where i ∈ Agt and a ∈ Act. We suppose actions in Act are described by an action theory γ = (γ+, γ-), where γ+ and γ- are, respectively, the positive and negative effect precondition function γ+ : Agt × Act × Prop -→ LPL and γ- : Agt ×Act ×Prop -→LPL.

The fact γ+(i, a, p) guarantees that proposition p will be true in the next state when action a is executed by agent i (provided no other action interferes), while γ-(i, a, p) guarantees that proposition p will be false in the next state when action a is executed by i (without interference). In case of conflicts between actions, we use an intertial principle: if γ+(i, a, p) and γ-(j, b, p) are both true at a given state and actions a and b (which may be the same action) are executed by agents i and j (which may also be the same), then the truth value of p will not change in the next state.

Furthermore, in cases where not all actions are available to all agents we can simply set γ+(i, a, p) = γ-(i, a, p) = ⊥ for all p ∈ Prop to signal that action a is not available to agent i. We also the assume the existence of the special action skip, such that γ+(i, skip, p) = γ-(i, skip, p) = ⊥ for all i and p. Equivalently, we could define skip as follows: γ+(i, skip, p) = p and γ-(i, skip, p) = ¬p for all i and p.

Definition 1 (Action-compatible histories). Let γ = (γ+, γ-) be an action theory and let H = (Hst ,Hact) be a k-history. We say H is compatible with γ if the following condition holds for every t ∈ {0, . . . , k - 1}, Hst (t + 1) = (Hst (t) \ X) ∪ Y where:

In words, a history H is compatible with the action theory γ = (γ+, γ-) if its state transition respects the theory. This means that, all propositional facts for which the negative effect precondition of an executed action hold, while the positive effect preconditions of all executed actions do not hold, become false. In addition, all propositional facts for which the positive effect precondition of an executed action holds, while the negative effect preconditions of all executed actions do not hold, become true. All other propositional facts do not change their truth values.

2.3 Action Sequences and Joint Plans

Let us now move from the notion of action to the notion of plan. Given k ∈ N, a k-action-sequence is a function

The set of k-action-sequences is noted Seqk. For a (nonempty) coalition of agents J ∈ 2Agt \ ∅ we can define a joint k-plan as a function Π : J -→ Seqk. If J is a singleton set then we call Π an individual plan. The set of joint k-plans for a coalition J is written PlanJk . The set of all joint plans for a non-empty coalition J is PlanJ = ⋃k∈N PlanJk . Given a joint plan Π for coalition J and another sub-coalition J ′ ⊆ J, we can write the joint plan of coalition J ′ in Π as ΠJ ′ , we can also write Π-J ′ for the joint plan of sub-coalition J \ J ′ .

Definition 2 (Plan Compatibility). Given Π1 ∈ PlanJk1 and Π2 ∈ PlanJ ′ k2 for sub-coalition J ′ ⊆ J and k2 ≤ k1, we say that Π1 is compatible with Π2 if

Given two k-plans Π1 and Π2 for disjoint coalitions J1, J2, we write Π1 ∪ Π2 (the combination of Π1 and Π2) for the shortest joint plan for J1 ∪ J2 such that (Π1 ∪Π2)J1 is compatible with Π1 and (Π1 ∪ Π2)J2 is compatible with Π2.

The following definition introduces the notion of history generated by a joint k-plan Π at an initial state s0. It is the action-compatible k-history along which the agents jointly execute the plan Π starting at state s0.

Definition 3 (History generated by a joint k-plan). Let γ = (γ+, γ-) be an action theory, s0 ∈ S and Π ∈ PlanAgt k . Then, the history generated by Π from state s0 in conformity with γ is the k-history HΠ,s0,γ = (HΠ,s0,γ st , HΠ,s0,γ act ) such that:

Example 1 (Toy-sharing). Consider a childcare robot that shares a set of four toys between two children. We model this by supposing that there three are agents, called Adam, Beth and Rob (the robot). The available actions are the skip action and 24 actions 1 written in the form Move(i, j, A), where the agent attempts to move toy A from agent i to agent j (where i ̸= j). There are 12 atomic propositions, each written Has(i,A) representing that agent i has toy A. The set of toys is written toys.

The action theory γtoys states that the action Move(i, j,A) succeeds exactly when toy A is with agent i and no other agent attempts to take toy A from agent i. In case of such a conflict, the toy remains where it is. The full formalisation of γtoys is in the supplementary material.

Consider an initial state with only two toys, both of which are held by Rob, that is s0 = {Has(Rob,1),Has(Rob,2)}. Consider the following joint 2-plan Π1:

In this plan Rob gives one toy to each child in turn, meaning that the final state will be s2 = {Has (Adam,1), Has (Beth,2)}.

2.4 Linear Temporal Logic

In order to represent agents' values in a temporal planning situation, we introduce the language of LTLf (Linear Temporal Logic over Finite Traces) [Pnueli, 1977; De Giacomo and Vardi, 2013; De Giacomo and Vardi, 2015], which we denote LLTLf , defined by the following grammar:

with p ∈ Prop, i ∈ Agt and a ∈ Act. Atomic formulas in this language are those that consist of a single proposition p or a single instance of do(i, a). X and U are the operators "next" and "until" of LTLf . Operators "henceforth" (G) and "eventually" (F) are defined in the usual way: Gφ def = ¬(⊤U φ) and Fφ def = ¬G¬φ.

Semantic interpretation of formulas in LLTLf relative to a k-history H ∈ Hist and a time point t ∈ {0, . . . , k} goes as follows (we omit boolean cases which are defined as usual):

Given a set of LLTLf -formulas Σ, we define Sat(Σ,H) = {φ ∈ Σ : H, 0 |= φ} to be the set of formulas from

Σ that are true in history H. Similarly, Sat(Σ,Π,s0,γ) = Sat(Σ,HΠ,s0,γ ) for joint plan Π starting from state s0 under the action theory γ.

2.5 Planning withMoral Agents

Moral values are not always consistent and occasionally conflict with each other [McConnell, 2022]. Furthermore, it is more serious to violate some values than others (murder is worse than lying). Therefore define the concept of a value base as an ordered sequence of sets of values (written as LLTLf -formulas) Ω1, ..., Ωn, with Ω1 containing the most important values and Ωn the least.

Definition 4 (Moral Planning Agent Problem). A moral planning agent problem (MPAP) is a tuple ∆ = (γ, s0, Ω) where γ = (γ+, γ-) is an action theory, s0 is an initial state, and Ω = (Ω1, . . . ,Ωm) is a value base with Ωk ⊆ LLTLf for every 1 ≤ k ≤ m.

We assume that all agents have a single, shared value base. This value base is used to compute the relative ideality of histories, namely, whether a history H1 is at least as ideal as another history H2. Following Lorini [2021], we call evaluation the operation of computing an ideality ordering over plans from a value base.

Inspired by work in preference representation languages [Lang, 2004] and preference-based temporal planning [Bienvenu et al., 2006; Grandi et al., 2022], we define the following qualitative criterion of evaluation, noted ⪯qual ∆ , which compares two histories lexicographically on the basis of inclusion between sets of satisfied values.

Definition 5 (Qualitative ordering of histories). Let ∆ = (γ, s0, Ω) be an MPAP with value base Ω = (Ω1, . . . , Ωm) and H1,H2 ∈ Histk two γ-compatible histories. Then, H1 ⪯qual ∆ H2 if and only if:

This method of evaluation compares histories by checking if either history satisfies a strict subset of the values satisfied by the other history at priority level 1. If they satisfy exactly the same set of values then we compare instead according to values of priority level 2, and so on. If at some point both histories satisfy different sets of values and neither is a subset of the other, then the two histories are incomparable according to qualitative ordering.

Since incomparability is not always desirable we can also define a notion of quantitative comparison ⪯quant ∆ . This is equivalent to qualitative comparison except that we compare the number of values satisfied by each history at each priority level. This ensures that any two histories will always be comparable.

2.6 FromValues to LTL Formulas

So far we have said very little about either the source of these values forming a value base (whether they should be imposed from above or learned by the agent) or their nature (whether they should be consequentialist, deontological, or something else). This is a deliberate choice, as we want our model to be able to accommodate a wide variety of different moral agents and their values (some of which may be practical or social rather than moral).

While defining a general method for formalising moral values in LTLf would be outside the scope of this paper, we will give an example of how this could be done in practice, by formalising the value of equality.

More specifically, when confronted with situations where a finite set of objects It are distributed amongst a finite group of agents J, equality requires an equal distribution (at the end of the plan). Assuming the existence of some general ownership atom Has(i,A), we can formalise such a value as EQUALITY(It ,J) = FG EqShare(It ,J), where:

Example 2 (Toy sharing - continued). We suppose that the shared value base Ωtoys contains three values. Firstly, both children must be given at least one toy (subsistence). Secondly, nobody should take a toy away from someone else, though they may give away their own toys (property). Finally, both children should have the same number of toys (equality). The formalisation of these values is as follows (where Ω1 is subsistence, Ω2 is property and Ω3 is equality):

Note the different temporal characteristics of these values. Substistence and equality both describe a state that must be satisfied at the end of the plan, whereas property must be satisfied at all points in the plan. Note also how our model is able to handle both consequentialist values (subsistence and equality both describe states of affairs that must hold at some point) and deontological values (property forbids agents from taking certain kinds of actions).

3 Evaluating Joint Plans

Once we fix a moral agent planning problem ∆, every joint plan Π induces a single generated history HΠ,s0,γ (recall Definition 3). Thus, we can lift Definition 5 of comparison among histories to comparison among joint plans.

Definition 6. Let ∆ = (γ, s0,Ω) be an MPAP and let Π1,Π2 ∈ PlanAgt be two joint plans for Agt. Then, Π1 ⪯qual ∆ Π2 if and only if HΠ1,s0,γ ⪯qual ∆ HΠ2,s0,γ . Similarly, Π1 ⪯quant ∆ Π2 if and only ifHΠ1,s0,γ ⪯quant ∆ HΠ2,s0,γ .

Given an MPAP ∆ = (γ, s0,Ω) and a joint plan Π ∈ PlanAgt we say that Π is k-non-dominated for ∆ if there is no plan Π′ of length at most k such that Π ⪯qual ∆ Π′

and Π′ ̸⪯qual ∆ Π (an equivalent definition can be given using ⪯quant ∆ ).

In conclusion, comparing joint plans with reference to a value base is conceptually equivalent to the problem of comparing two histories. Thus, we can import the analysis and the computational complexity results of Grandi et al. [2022], who showed that the problem of comparing singleagent plans (and hence histories) can be solved in polynomial time, while the problem of testing whether a given plan or history is non-dominated is PSPACE-complete.

Example 3 (Toy sharing - continued). Consider again the initial state with only two toys, both of which are held by Rob, s0 = {Has(Rob,1),Has(Rob,2)}. In this instance there are several joint plans that satisfy all values (and therefore are, by necessity, non-dominated). The first is the plan that we introduced before:

It is straightforward to see that this plan satisfies the values of subsistence, property and equality.

Consider now a different initial state with only one toy, held by Rob (s0 = {Has(Rob,1)}). In this case there is no plan satisfying all values, as our subsistence values conflict with our equality value. A non-dominated plan will therefore be one that prioritises values according to the lexicographic ordering. In this case, the best Rob can do is to satisfy the property value and one of the subsistence values:

However, if we change the value base by swapping the contents of Ω1 and Ω3, then Π2 is dominated by the following plan, which would itself be non-dominated (as now the best option for Rob is to keep the toy and satisfy equality):

4 Evaluating Individual Plans

Evaluating joint plans is helpful whenever agents are able to coordinate, for example in presence of a central planner. Otherwise, agents may not have any knowledge about the other agents' plans. Meaning that their individual plans may be part of many possible joint plans, meaning many possible histories and many possible sets of satisfied values.

4.1 Optimistic and Pessimistic Comparison

Two intuitive ways of comparing individual plans under complete ignorance of the other agents' plans are by comparing according to the best-case outcome of that individual plan (risk-seeking) or the worst-case outcome of that individual plan (risk-averse). In line with Lorini [2015], we call these methods of comparison "optimistic" and "pessimistic".

Definition 7 (Optimistic k-comparison). Let ∆ = (γ, s0, Ω) be an MPAP, i ∈ Agt, and Π1,Π2 be individual plans. Let k be an integer greater than or equal to the length of both Π1 and Π2. Then, Π1 ≤opt i,k Π2 iff ∃Π′2 ∈ PlanAgt k s.t. Π′2 is compatible with Π2 and ∀ Π′1 ∈ P lanAgt k s.t Π′1 is compatible with Π1 we have Π′1 ⪯quant ∆ Π′2 .

Definition 8 (Pessimistic k-comparison). Let ∆= (γ, s0,Ω) be an MPAP, i ∈ Agt, and Π1,Π2 be individual plans. Let k be an integer greater than or equal to the length of both Π1 and Π2. Then, Π1 ≤pess i,k Π2 iff ∃Π′1 ∈ PlanAgt k s.t Π′1 is compatible with Π1 and ∀Π′2 ∈ P lanAgt k s.t Π′2 is compatible with Π2 we have Π′1 ⪯quant ∆ Π′2 .

The reading of the plan comparison statement Π1 ≤opt i,k Π2/Π1 ≤pess i,k Π2 is "agent i's k-plan Π2 is optimistically/pessimistically at least as ideal as agent i's k-plan Π1". We use the standard notation of writing Π1 <pess i,k Π2 for Π1 ≤pess i,k Π2 and Π2 ̸≤pess i,k Π1, and Π1 ≈pess i,k Π2 if Π1 ≤pess i,k Π2 and Π2 ≤pess i,k Π1. The notion of plan comparison allows us to define the corresponding notion of nondominated plan.

Definition 9 (Optimistic k-non-dominance). Let ∆ = (γ, s0,Ω) be an MPAP, i ∈ Agt, and Π1 ∈ Plank. Then, we say that agent i's plan Π1 is k-non dominated iff ̸ ∃Π2 ∈ Plank such that Π1 <opt i,k Π2.

Given an agent i ∈ Agt , we say that i is optimistic-rational if i only ever selects plans that are optimistic non-dominated. We define the notions of "pessimistic k-non-dominance" and "pessimistic-rationality" in an equivalent way.

Note that we have used quantitative comparison in our definition in order to simplify later proofs, but we could alternatively use qualitative comparison. Qualitative comparison does not guarantee the existence of a single history that is weakly preferred to all other histories, hence the slightly more-complex-than-usual phrasing of optimistic and pessimistic comparison.

Example 4 (Toy Sharing - continued). Consider the plans available to Rob using pessimistic comparison. While there are many joint plans that satisfy all values, guaranteeing the satisfaction of values in the individual planning case is much harder. This is because if we fix the actions of Rob, Adam and Beth can always "coordinate" their actions to cause a worstpossible outcome. This can be done by having Adam "block" all of Rob's moves by always making conflicting moves, while Beth moves toys in a way that violates as many values as possible. This means pessimistic comparison does not discriminate in this planning domain.

On the other hand, optimistic comparison does discriminate between plans, since if Rob chooses a plan that does not violate property, property will not be violated in the best-case outcome, but if Rob chooses a plan that does violate property, then property will be violated even in the best-case outcome. Moreover, it can be seen that if all agents are optimisticrational, property will not be violated.

The example above suggests that optimistic comparison generally discriminates more than pessimistic comparison. However, we now define two classes of MPAP where both notions cannot discriminate among plans.

Definition 10 (k-Resilient Domains). Let ∆ = (γ, s0, Ω) be an MPAP, we say that ∆ is k-resilient iff ∀i ∈ Agt,Π ∈

P lan{i} k , ∃Π′ ∈ PlanAgt k where Π′ is compatible with Π and Π′ is a k-non-dominated joint plan according to ⪯quant ∆ .

Definition 11 (k-Fragile Domains). Given an MPAP ∆ = (γ, s0,Ω), we say that ∆ is k-fragile iff ∀i ∈ Agt,Π ∈ P lan{i} k , ∃Π′ ∈ PlanAgt k where Π′ is compatible with Π and Π′ is k-maximally-dominated according to ⪯quant ∆ (there is no plan Π′′ such that Π′′ ≺quant ∆ Π′ ).

The following two theorems show that optimistic comparison cannot discriminate between plans in a resilient domain, and pessimistic comparison cannot discriminate between plans in a fragile domain. Full proofs can be found in the supplementary material.

Theorem 1. Given a k-resilient MPAP ∆ = (γ, s0,Ω), an agent i ∈ Agt and two individual plans Π1 and Π2, we have that Π1 ≈opt i,k Π2.

Theorem 2. Given a k-fragile MPAP ∆ = (γ, s0,Ω), an agent i ∈ Agt and two individual plans Π1 and Π2, we have that Π1 ≈pess i,k Π2.

The intuition behind these proofs is that in a resilient domain, no individual plan will optimistic-dominate any other because all plans are optimistic non-dominated (since all best-case outcomes are equally good). An equivalent issue occurs for pessimistic-rational agent in a fragile domain. This is also why pessimistic comparison is indifferent in Example 4, as ∆toys is a k-fragile domain for any k ∈ N in any initial state where all toys belong to Rob.

4.2 Anticipating Blameworthiness

The previous section illustrates the need for another method of plan comparison to complement optimistic or pessimistic comparison. A moral agent would care not just about values being satisfied, but also that they are not blameworthy for values being violated. This is something that we aim to introduce to our model, by defining the following notion of blameworthiness. First, given a set of LLTLf -formulas Σ, let us denote with Viol (Σ,Π,s0,γ) the set Σ \ Sat(Σ,Π,s0,γ) of those formulas in Σ that are not satisfied by the history generated by plan Π from state s0 according to action theory γ.

Definition 12 (Anticipated Passive Blameworthiness with k-Horizon). Let k be a positive integer. Let MPAP = (γ, s0, Ω) be an MPP, i ∈ Agt an agent, and Π ∈ P lanl{i} an individual plan where l ≤ k. Let ω ∈ Ω. Then, we say that i is P-k-blameworthy for ω in Π if there exists some joint plan Π1 ∈ Planl1Agt\{i} such that l ≤ l1 ≤ k, HΠ∪Π1,s0,γ ̸|= ω, and there exists some joint plan Π2 ∈ Planl2 {i} such that l1 ≤ l2 ≤ k and HΠ2∪Π1,s0,γ |= ω.

Definition 13 (Anticipated Active Blameworthiness with k-Horizon). Let k be a positive integer. Let MPAP = (γ, s0,Ω) be an MPP, i ∈ Agt an agent, and Π ∈ Planil an individual plan where l ≤ k. Let ω ∈ Ω. Then, we say that i is A-k-blameworthy for ω in Π if there exists some joint plan Π1 ∈ P lanAgt l1 such that l1 ≤ k, HΠ1,s0,γ |= ω, and for all joint plans Π2 ∈ PlanAgt l2 such that l ≤ l2 ≤ k and Π2 is compatible with Π, HΠ2,s0,γ ̸|= ω.

In line with previous work [Lorini and M¨uhlenbernd, 2018; Lorini et al., 2014], we assume blameworthiness has two components: the causal responsibility component and the value violation component. This means that an agent is blameworthy for any value that it is causally responsible for violating. The notions of causal responsibility we consider are both the passive sense (i.e. given the other agents' choices, the agent could have prevented the value from being violated by making a different choice) and the active sense (i.e. given the agent's choices, the other agents could not prevent the value from being violated by making different choices). For more on the distinction between passive and active responsibility we refer to Lorini et al. [2014]. Note that our definition is for anticipated responsibility, meaning that i may be responsible if they perform plan Π. This only really affects passive responsibility, since if an agent is actively responsible the actions of all other agents are irrelevant.

We can also define equivalent notions of active and passive praiseworthiness, meaning that an agent is actively praiseworthy for any value that they guaranteed the satisfaction of, and passively praiseworthy for any value that was satisfied but which they could have violated.

Given an MPAP ∆ = (γ, s0,Ω), an agent i ∈ Agt and an individual plan Π and an integer k greater than or equal to the length of Π, we define ABW(i,Π, k,∆) as the set of all values ω ∈ Ω such that agent i is A-blameworthy for ω in Π (where ∆ is obvious from context, it is omitted). We define PBW(i,Π, k,∆) as composed of all values ω ∈ Ω such that agent i is P-blameworthy for ω in Π. Equivalently, we can define APW(i,Π, k,∆) and PPW(i,Π, k,∆) for praiseworthiness.

Example 5 (Uses of Responsibility). A responsibilityconscious agent could allow us to improve on both optimistic and pessimistic comparison. For optimistic comparison, consider a simple example with multiple agents with the goal of emptying a bin. This is acheived by some agent performing the emptybin action at some point in their plan (let plan Π1 be a sequence of skip actions and Π2 the same but with an emptybin action at the beginning). This is then a k-resilient domain (for all k) since the best-case outcome for all individual plans is the same. Therefore an optimistic-rational agent could not decide between Π1 and Π2.

However, the table above shows that by emptying the bin, the agent will be actively and passively praiseworthy for the bin being emptied, whereas by not emptying it, they will be passively blameworthy for not doing so. Therefore a responsibility-conscious agent would choose to empty the bin. For pessimistic comparison, consider again Rob from the toysharing example. Let Π1 be some plan containing an action that violates property, and Π2 a plan that does not contain such an action. Then consider the following table, illustrating responsibility for the property value:

Therefore by choosing plan Π2 Rob can ensure that they will not be blameworthy for the violation of property (even if the value is violated by another agent).

5 Complexity Results

This section provides an analysis of the computational complexity of optimistic and pessimistic comparison, as well as the notions of blameworthiness introduced in Section 4.2. These tasks are PSPACE-complete, in line with the complexity of classical problems in planning or the model checking of LLTLf -formulas. Full proofs of our results can be found in the supplementary material.

Define OPT-k-COMPARISON (respectively PESS-kCOMPARISON) as the decision problem that takes as input an MPAP ∆ = (γ, s0,Ω), an integer k, and two individual plans Π1 and Π2 for some agent i, and asks whether Π1 ≤opt i,k Π2 (resp. Π1 ≤pess i,k Π2). Membership in PSPACE is straightforward, given that we can generate and compare joint plans two-by-two. With a reduction from the classical PSPACE-complete problem PLANMIN [Bylander, 1994] we can show the following:

Theorem 3. OPT-K-COMPARISON and PESS-KCOMPARISON are both PSPACE-complete.

For responsibility, we consider the problem of recognising whether an agent is blameworthy for a given value. Let A-BLAME (respectively P-BLAME) be the decision problem where given an individual plan Π for some agent i, k greater than or equal to the length of Π and a formula φ ∈ ∪Ω in an MPAP ∆ = (γ, s0,Ω), we must decide if φ ∈ ABW(i, Π, k, ∆) (respectively φ ∈ PBW(i, Π, k, ∆)). Again, membership to PSPACE is straightforward and a reduction from PLANMIN shows the following:

Theorem4. A-BLAME and P-BLAME are both PSPACEcomplete.

While we did not introduce any notion of comparison based on anticipated responsibility, our Theorem 4 shows that any reasonable such definition will be PSPACE-hard to use.

6 RelatedWork

Our work is a contribution to the field of ethical planning in AI [Dennis et al., 2016; Lindner et al., 2019], and also to the larger body of research on planning with preferences [Baier and McIlraith, 2008; Juma et al., 2012] and temporally extended goals [Bienvenu et al., 2006; De Giacomo and Vardi, 2015; Camacho et al., 2017].

Of these, the work of Bienvenu et al. [2006] and Dennis et al. [2016] are the two most closely related to our work. Bienvenu et al. [2006] present a model for planning with temporal preferences, represented using various combinations of LTL formulas. While this model does allow lexicographic combinations of values, it cannot efficiently model our concept of a lexicographic value base. Also, unlike our work, this model does not allow for incomparability between plans, which can be useful when dealing with ethical dilemmas. Dennis et al. [2016] focus instead on the verification of autonomous agents in relation to their capacity to select ethical plans. This paper models ethical values in propositional logic, and uses a total (not necessarily strict) order on values that is functionally equivalent to our notion of quantitative comparison. To evaluate plans, this model uses ethical rules which map specific actions (or their absence) to the violation of specific values in a given context. While our representation of value bases is equivalent, their model allows the tracking of repeated violations of values, however it is limited to propositional values that can be attributed to single actions, whereas we have the full expressivity of LTLf . Finally, both papers are limited to single-agent planning applications.

However, some approaches to multi-value LTL planning do consider multiple agents. For example, Guo and Dimarogonas [2015] present a model for motion planning in a cooperative setting, where each agent has an independent goal represented in LTL as a series of hard and soft constraints. This approach differs from ours in that it is specialised towards motion planning. While it can model potentially conflicting values through its use of soft constraints, it has no way of indicating the relative priority of constraints. On the other hand, it includes partial information and communication between agents, which suggests useful additions to our work.

A popular approach to managing relative levels of importance in multi-value planning is to assign numerical weights to values. Juma et al. [2012] explore solving Preference Based Planning problems (a form of multi-objective planning) via partial weighted MaxSAT techniques. Partial weighted MaxSAT has both hard constraints and soft constraints (which have weighted penalties for not satisfying). This approach can easily handle multiple conflicting goals, but we chose to avoid it in favour of a lexicographic approach as we wanted to guarantee that our most important values (such as safety) could not be overridden by a multitude of lesser values (such as politeness). Furthermore, this paper is only able to express preferences as partial sets of assignments to variables, rather than our model which uses LTLf .

Similar approaches to our work can also be found in the field of agent programming. Agent programming is similar to planning in that agents have a set of available actions and a goal to achieve. The difference is that rather than finding a plan to achieve the goal, agents follow the rules of some program. This is computationally much more tractable than planning, but does not guarantee that the agents actions will be ideal, which is why we did not use this approach. Hindriks and Birna van Riemsdijk [2008] use (limited) look-ahead and soft and hard constraints to further restrict available actions. The soft constraints are strictly ordered in a lexicographic fashion (unlike our model where the ordering can be nonstrict) and hard constraints simply must not be violated.

The complexity analysis we perform is in line with the work of Lindner et al. [2019] which reaches similar conclusions concerning consequentialist plan comparison. In this work, the authors evaluate the permissibility or impermissibility of various single-agent single-goal plans according to various ethical principles. They evaluate various ethical theories including deontology, consequentialism and the principle of double effect under a numerical representation of values on actions and properties of the environment.

Our work on responsibility is part of the larger field of Responsible AI, as outlined by Dignum [2020]. She identifies three main branches of responsible AI: developing legislation for determining responsibility in cases involving AI, ensuring AI compliance with human ethics and values, and ensuring widespread accessibility and participation in the development and use of AI. Our work focuses on the second branch.

The idea of combining notions responsibility and blameworthiness in multi-agent planning has also been explored in a recent work by Alechina et al. [2017], which grounds on previous work by [Chockler and Halpern, 2004] on the formalization of responsibility (see also [Halpern and KleimanWeiner, 2018]). Rather than using LTL, as in our approach, this work uses structural equation modeling (SEM). Also, while our work focuses on responsibility as a method of plan evaluation (forward-looking), this paper considers responsibility retrospectively, and assigns responsibility for the failure of a goal (backward-looking). This model can assign different degrees of responsibility to different agents, which ours cannot, but it is limited to planning problems with a single goal, and there is no connection to ethics.

Our model is grounded on previous work in ethical planning and moral reasoning. First, our representation of values and their interpretation on histories is based on the work of Grandi et al. [2022]. Second, our notions of dominance between multi-agent plans is inspired by Lorini [2015], who however uses a numerical representation of values.

7 Conclusion

In this paper we outlined our model of moral planning agents with temporal values, equipped with novel criteria to evaluate their plans. We showed, with the help of a running example, that optimistic and pessimistic comparison can be indecisive in ethically sensitive situations. We introduced new criteria based on responsibility, and showed that they overcome this limitation. Finally, we showed that comparing plans in our model is PSPACE-complete.

Our intention is to create a model that can be used by autonomous moral agents to produce ethically-acceptable plans. To this end, we would like to expand the expressiveness of our model and drop some of the simplifying assumptions made in this paper. At present, our model assumes that all agents have the same value base, it also assumes perfect information and fully deterministic actions, which will not always be a practical assumption. In line with Dietrich and List [2017], we intend to relax these assumptions in future work.

Furthermore, while we have modelled a causal form of responsibility (where the actions of agents causally contribute to an outcome) it would be interesting to consider indirect notions of responsibility as studied by Lorini and Sartor [2016]. We would also like to extend LTLf to include epistemic operators for applications to AI such as ChatGPT, whose ethical violations (misleading users, revealing sensitive information) are mostly epistemic in nature.

Last but not least, it would also be interesting to refine our methods for plan comparison, including developing methods that make use of dominance such as those proposed by Horty [2001]. This could be used to create real-world implementations of our model to demonstrate its capability.

Ethical Statement

There are no ethical issues.

Acknowledgments

Support from the ANR project CoPains "Cognitive Planning in Persuasive Multimodal Communication" (grant number ANR-18-CE33-0012) and the ANR-3IA Artificial and Natural Intelligence Toulouse Institute (ANITI) is gratefully acknowledged.