# Data-Driven Goal Recognition Design for General Behavioral Agents

Robert Kasumba1,∗ Guanghui Yu2,∗
Chien-Ju Ho3,∗ Sarah Keren4,† William Yeoh5,∗
∗Washington University in St. Louis
† Technion – Israel Institute of Technology
{rkasumba1, guanghuiyu2, chienju.ho3<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

_Goal recognition design_ aims to make limited modifications to decision-
making environments with the goal of making it easier to infer the goals of
agents acting within those environments. Although various research efforts
have been made in goal recognition design, existing approaches are
computationally demanding and often assume that agents are (near-)optimal in
their decision-making. To address these limitations, we introduce a data-
driven approach to goal recognition design that can account for agents with
general behavioral models. Following existing literature, we use _worst-case
distinctiveness_ (wcd) as a measure of the difficulty in inferring the goal of
an agent in a decision-making environment. Our approach begins by training a
machine learning model to predict the wcd for a given environment and the
agent behavior model. We then propose a gradient-based optimization framework
that accommodates various constraints to optimize decision-making environments
for enhanced goal recognition. Through extensive simulations, we demonstrate
that our approach outperforms existing methods in reducing wcd and enhancing
runtime efficiency in conventional setups, and it also adapts to scenarios not
previously covered in the literature, such as those involving flexible budget
constraints, more complex environments, and suboptimal agent behavior.
Moreover, we have conducted human-subject experiments which confirm that our
method can create environments that facilitate efficient goal recognition from
real-world human decision-makers.

##  1 Introduction

With the rapid advancement of artificial intelligence (AI), there has been a
surge in interest in human-AI collaboration, aiming to synergize human and AI
capabilities across various domains such as gaming, e-commerce, healthcare,
industrial engineering, and workflow productivity. Designing AI agents to work
alongside humans requires these agents to understand and infer human goals and
intentions. While there has been abundant research in goal recognition
(Ramírez and Geffner, 2010; Sukthankar et al., 2014) that aims to infer human
goals by observing their actions, this work focuses on the goal recognition
design problem (Keren et al., 2014), where one needs to identify how to modify
decision-making environments to enable better goal recognition.

Our work is built on the goal recognition design problem formulated by Keren
et al. (2014). In their work, they proposed the worst-case distinctiveness
(wcd) metric, defined as the maximum number of decisions an agent can make
without revealing its goal, to measure the difficulty of inferring the agent’s
goal. They then aimed to modify the decision-making environment, through
removing allowable actions from states, to optimize this measure. Since the
introduction of this work, there have been several follow-up works that extend
the formulation to deal with different settings, such as stochastic settings
(Wayllace et al., 2016, 2017) and partial observability (Keren et al., 2016).
More discussion can be found in the survey by Keren et al. (2021).

While there has been significant progress in goal recognition design, there
are two main limitations in the literature. First, current approaches require
evaluating the difficulty of goal recognition, i.e., worst-case
distinctiveness (wcd), for a large number of potential modifications to the
decision-making environment. This process is computationally demanding and
limits the scalability of these approaches, especially in virtual domains
where the number of possible environment configurations is large. Second,
decision-making agents in goal recognition design are often assumed to be
optimal. While there are efforts addressing suboptimal agents (Keren et al.,
2015; Wayllace and Yeoh, 2022), these primarily focus on settings where there
is a limited number of deviations from optimal decision-making. This
assumption of optimality is limiting in scenarios involving human agents, who
are known to often systematically deviate from optimal decision-making due to
cognitive and informational constraints (Kahneman, 2003; O’Donoghue and Rabin,
1999).

To address these limitations, we propose a framework for data-driven goal
recognition design with general agent behavior. We explicitly incorporate
models of agent behavior into the optimization framework to better represent
behavioral agents. To tackle the computational challenges, our approach
leverages data-driven methods for goal recognition design. The core idea
involves building a machine learning oracle that predicts the difficulty of
goal recognition (e.g., wcd) given a decision-making environment and an
agent’s behavioral model. This oracle is trained on datasets generated from
simulations, allowing for the evaluation of wcd in any given environment and
agent model. Such an approach significantly accelerates the evaluation of wcd
during run-time optimization. Once the machine learning oracle is established,
we apply gradient-based optimization to minimize wcd, employing Lagrangian
relaxation to manage constraints on environment modifications.

To evaluate our data-driven goal recognition design framework, we conducted a
series of simulations. Initially, these simulations were carried out in the
standard setup in the grid world envrionment assuming optimal agent behavior.
We show that our approach outperforms existing baselines in reducing worst-
case distinctiveness (wcd) and demonstrates considerably better run-time
efficiency. We then conducted additional simulations to showcase that our
approach can generalize to settings beyond the capabilities of existing
approaches in the literature. These include scenarios involving flexible
budget constraints, more complex environments, and suboptimal agent behavior.
Lastly, we have conducted human-subject studies demonstrating that our method
can be leveraged to design environments that facilitate efficient goal
recognition from real-world human decision-makers. The results highlight the
potential of our approach to enable more efficient human-AI collaboration.

##### Contributions.

The main contributions of this work can be summarized as follows.

  * $\bullet$

We propose a data-driven optimization framework for goal recognition design.
This framework comprises a predictive model that estimates the wcd for a given
environment and a model of agent behavior. Leveraging the differentiable
property of the predictive model, we utilize a gradient-based optimization
method for goal recognition design. The framework is flexible to accommodate
various environments, design spaces, and agent models.

  * $\bullet$

Through extensive simulations, we show that our framework not only outperforms
existing approaches in goal recognition design within standard settings but
also adapts to scenarios that existing approaches cannot handle. These
scenarios include those with general optimization criteria, complex
environments, and suboptimal agent behavior.

  * $\bullet$

Through real-world human-subject experiments, we demonstrate that our approach
can adapt to agent models trained on human behavior. Furthermore, our
framework can create environments that enable more effective goal recognition
with real-world human decision-makers.

##  2 Related Work

Our work contributes to the expanding field of human-AI collaboration. Recent
research has indicated that optimizing AI alone is insufficient for maximizing
the performance of human-AI teams (Bansal et al., 2021; Carroll et al., 2019).
To develop truly collaborative AI agents, it is crucial to equip them with the
ability to comprehend and predict the intentions and goals of their human
counterparts. This challenge lies at the heart of goal recognition research
(Kautz and others, 1991; Ramírez and Geffner, 2010; Hong, 2001; Sukthankar et
al., 2014; Pereira et al., 2017; Masters et al., 2021). Our work specifically
focuses on goal recognition design, an extension of goal recognition that
includes modifying environments to better facilitate the process of
recognizing goals.

Goal recognition design was originally formulated by Keren et al. (2014).
Since this seminal work, numerous research efforts have expanded the concept
to accommodate stochastic environments (Wayllace et al., 2017; Wayllace and
Yeoh, 2022), different levels of observability (Keren et al., 2016; Wayllace
et al., 2020), and a variety of design spaces (Mirsky et al., 2019). The
studies most closely aligned with our approach focus on suboptimal agents
(Keren et al., 2015; Wayllace and Yeoh, 2022). However, these studies
characterize suboptimality by limiting deviations from the optimal policy, a
method that may not adequately represent behavior of human agents, who
frequently deviate systematically from optimal decision-making. Additionally,
most existing work requires evaluating the difficulty of goal recognition in
run time for numerous environmental modifications, which constrains the
scalability of these methods. Our work sets itself apart by broadening the
goal recognition design question to incorporate general agent behavioral
models and by implementing a data-driven optimization approach.

From a technical standpoint, we adopt a data-driven optimization approach for
goal recognition design. The use of data-driven tools in optimization has
gained increasing prominence in the field of mechanism design, as evidenced by
a range of recent studies (Dütting et al., 2019; Feng et al., 2018; Golowich
et al., 2018; Curry et al., 2020; Kuo et al., 2020; Rahme et al., 2020; Peri
et al., 2021; Cornelisse et al., 2022; Yu et al., 2023). In this regard, our
work closely aligns with the studies by Yu and Ho (2022) and Yu et al. (2023),
who explicitly encoded human behavior and responses within their mechanism
designs for optimizing the information policy in environment and information
design. While our work shares a similar motivation, our approach and problem
formulation differ from theirs.

##  3 Problem Formulation and Methods

###  3.1 Problem Setting

We formulate the decision-making environment and behavioral agent models. We
also explain the commonly-used metrics for evaluating goal recognition
difficulty.

##### Decision-making environment.

We define the decision-making environment as a Markov Decision Process (MDP),
represented by $W=\langle S,A,P,R\rangle$. Here, $S$ denotes the set of
states, $A$ represents the set of agent actions, $P(s^{\prime}|s,a)$ is the
transition probability from state $s$ to state $s^{\prime}$ upon taking action
$a\in A$, and $R(s,a,s^{\prime})$ represents the bounded reward received after
taking action $a$ in state $s$ and reaching state $s^{\prime}$. To emphasize
the goal recognition aspects of the problem, we introduce a set of goal states
$G\subseteq S$. These goal states are terminal; that is, $P(g|g,a)=1$ $\forall
g\in G,a\in A$.

##### Models of behavioral agents.

We represent the agent’s decision-making policy in a general form $\Pi:S\times
T\rightarrow A$. Specifically, for an agent with a decision-making policy
$\pi\in\Pi$, the agent will execute the action $\pi(s,t)$ in state $s$ at time
$t$. The agent is conceptualized as a planner $H:W\rightarrow\Pi$, where the
input is an environment $w\in W$, and the output is a policy $\pi\in\Pi$. To
illustrate our formulation, consider a agent parameterized by a time-variant
discounting function $d(t)$. The standard optimal agent model corresponds to a
fixed discounting factor $\gamma\in(0,1]$ with $d(t)=\gamma^{t}$. We can also
represent an agent with present bias (O’Donoghue and Rabin, 1999) by adopting
a hyperbolic discounting factor $d(t)=\frac{1}{1+kt}$, where $k>0$. We would
like to highlight that our approach not only accounts for standard analytical
closed-form expression of agent behavior. It can also accounts for scenarios
where an agent policy $\pi$ is a machine learning model, i.e., a neural
network trained on human behavioral data.

##### Worst-case distinctiveness (wcd).

To evaluate the difficulty of goal recognition, we adhere to standard
literature and focus on the measure of worst-case distinctiveness (wcd) (Keren
et al., 2014), defined as the maximum number of steps an agent can take before
revealing its goal. To compute the wcd for a given suboptimal agent $h\in H$
in an environment $w\in W$, we evaluate the path for the agent to each goal
and compute the number of actions from the initial state that are identical
for every goal.

###  3.2 Goal Recognition Design with General Behavioral Agents

We formalize the goal recognition design problem with general behavioral
agents. Given an environment $w$ and an agent with a behavior model $h$, we
denote the worst-case distinctiveness of environment $w$ for agent $h$ as
$\textit{wcd}(w,h)$. Each type of modification $1\leq i\leq N$ will incur a
cost $c_{i}(w,w^{\prime})$ that must fall in budget constraint $B_{i}$. The
objective of the goal recognition design problem is to alter the environment
from $w$ to $w^{\prime}$ in a way that minimizes $\textit{wcd}(w^{\prime},h)$,
while satisfying the constraint that the cost of the modifications does not
exceed the budget.

$\displaystyle\underset{w^{\prime}}{\text{minimize}}$
$\displaystyle\textit{wcd}(w^{\prime},h)$ (1) subject to $\displaystyle
c_{i}(w,w^{\prime})\leq B_{i},\forall 1\leq i\leq N$

###  3.3 Our Proposed Method

Existing approaches in goal recognition design require evaluating wcd for a
large number of potential modifications to the environments to identify the
optimal modifications. Since evaluating wcd requires evaluating the agent
policy for multiple goals, it presents significant computational overhead and
limits the scalability of these approaches. To overcome this challenge, we
propose leveraging machine learning to expedite run-time computations. The
main idea, as summarized in Figure 1, is to first train a machine learning
model that predicts wcd for any given pair of decision-making environment $w$
and agent behavioral model $h$. After obtaining this machine learning model
and utilizing its differentiable property, we develop an optimization
framework that applies gradient-based optimization methods to the Lagrangian
relaxation of the constrained optimization formulation in (1).

(a) Predictive model for wcd.

(b) Optimization framework.

Figure 1: We first train a predictive model to predict wcd from simulated
data. We then perform gradient-based optimization that leverages the
predictive model to identify environment modifications that minimize wcd with
a given model of agent behavior.

##### Predictive model for wcd.

To build the predictive model for wcd, we first curate a training dataset
through simulations. For a given environment $w$ and agent behavioral model
$h$, we can obtain $\textit{wcd}(w,h)$ by solving for the agent’s actions
towards different goals. After collecting a training dataset, we train the
predictive model using a convolutional neural network. Implementation details
are included in the appendix.

##### Optimization procedure.

After obtaining the predictive model, we develop a gradient-based optimization
framework. Note that this optimization framework strictly generalizes the
existing literature in goal recognition design where the space of
modifications are limited (e.g., usually limits to blocking an action in MDP)
(Keren et al., 2021).

The first step involves transforming the constrained optimization problem in
(1) into an unconstrained optimization problem using Lagrangian relaxation:

$\displaystyle\mathcal{L}=\textit{wcd}(w^{\prime},h)+\sum_{i}\lambda_{i}(c_{i}(w,w^{\prime})-B_{i}).$

We then perform gradient descent on the relaxed Lagrangian. As environment
modifications are often discrete (e.g., whether to block a cell in the grid
world), we apply a discrete gradient descent procedure. Specifically, at each
step of gradient descent, we obtain a gradient, which is a vector indicating
the suggested change magnitude for each element (such as a cell in the grid
world). We then select the element with the highest gradient value and make
the corresponding change. Note that some suggested modifications may not be
valid; for instance, we cannot block a cell that is already blocked in the
grid world. In such cases, we proceed to the element with the next highest
gradient value, continuing this process until a valid modification is made.
This modification procedure is repeated until the gradient descent converges.

Note that with this Lagrangian relaxation, we cannot directly set the budget,
however, based on duality, a larger Lagrangian multiplier $\lambda$
corresponds to a smaller budget $B$, in the original constrained optimization
formulation. In our experiments, instead of selecting different budgets
directly, we choose varying Lagrangian multipliers and record the realized
costs of the modifications.

##  4 Experiment Setup

###  4.1 Benchmark Domains

We utilize two benchmark domains. The first is the standard basic grid world
environment, commonly used in goal recognition design literature. The second
is the Overcooked-AI environment (Carroll et al., 2019), an complex
environment with a richer set of environment modification. This environment is
particularly relevant to the downstream implications of our work, namely in
supporting human-AI collaboration.

(a) Grid world.

(b) Overcooked-AI.

Figure 2: The example showcases two benchmark environments. The first,
displayed on the left, is a grid world environment. The agent starts at a
position marked ’S’ and aims to reach one of the goal positions labeled ’G’.
The agent must navigate through the grid, avoiding blocked cells marked with
’x’. The second environment, illustrated on the right, is an Overcooked-AI
setting. In this scenario, the agent’s objective is to pick up ingredients and
complete the cooking of their target recipe, which constitutes their goal.

####  4.1.1 Benchmark Domain: Grid world

In the grid world domain, agents navigate a grid with several potential goals.
Take, for example, a grid world environment as illustrated in Figure 2(a). In
this environment, an optimal agent starts at point ’S’ and aims for one of the
goals. Spaces marked ’X’ are blocked, barring the agent’s passage. In this
particular environment, the worst-case distinctiveness (wcd) is 0, as an
optimal agent, following the shortest path to either goal, would reveal its
intended goal on the first move due to non-overlapping paths. Our experiments
are primarily focused on grid world environments with two goals for
simplicity. However, our approach is applicable to scenarios with more than
two goals.

##### Design space of environment modifications.

In the context of goal recognition design in grid world, the space environment
modification is often limited to adding blocks to spaces (Keren et al., 2014),
also called _action removal_ in the literature. In our work, we broaden the
design space for modifications to also consider the _unblocking_ of existing
blocked spaces as potential modifications.

####  4.1.2 Benchmark Domain: Overcooked-AI

We also conduct our evaluations on a more complex domain: Overcooked-
AI111https://github.com/HumanCompatibleAI/overcooked_ai. This environment is
based on the popular multiplayer game Overcooked. In each game, players
(agents) collaborate to prepare and deliver specific recipes. Since the goal
of our approach is to enable efficient inference of agent goals, we focus on
the special case with a single agent. The environment is represented as a grid
(see Figure 2(b)) with each cell specifying the object that is placed at the
cell. The objects may be a counter, a tomato, an onion, a pot, a dish, a
serving point, or an empty space. The agent can only occupy empty spaces in
the environment and cannot step on any other objects in the environment. The
agent can carry the movable objects, i.e. onion, tomato, and dish, and drop
them on any of the other non-space objects (counter, serving point, or pot).
To navigate in the environment, the agent can move left, right, north, or
south and maintain an orientation that is consistent with the last movement
direction.

##### Goal recognition in Overcooked-AI.

The goal of the agent in Overcooked-AI is defined by the recipe it needs to
complete. For instance, to prepare a soup with one onion and two tomatoes, the
agent must pick up the ingredients, place them in the pot, and cook them. In
the context of goal recognition, the objective is to deduce which recipe the
agent is preparing. For the sake of simplicity in our experiments, we focus on
scenarios with only two possible goals or recipes.

##### Design space of environment modifications.

A primary challenge in the Overcooked-AI environment is its considerably
larger design space for environment modifications. The design space includes
the addition, removal, or changing position of any object within the
environment, subject to the modification being valid. This means an object
cannot be added to a cell already occupied by another object, and an object
that does not exist cannot be removed. The objective of conducting experiments
in this domain is to assess whether our approach can be used to address more
complex domains.

###  4.2 Baselines

We now describe the baseline approaches we use to compare against our
approach.

  * $\bullet$

Exhaustive search: This is the brute-force approach that evaluates wcd for all
the environments on the search path until the minimum possible wcd is found.
It is guaranteed to achieve minimum wcd. However, given the computation
overhead, this approach is not applicable in most situations.

  * $\bullet$

Pruned-Reduce (Keren et al., 2014): This baseline is specifically designed for
settings where modifications are limited to action removal such as blocking a
cell in grid world. It speeds up the exhaustive search and retains the optimal
property. However, its scalability is still limited.

  * $\bullet$

Greedy search using true wcd: This greedy search baseline finds the single
environment modification that leads to the maximum reduction of wcd at each
iteration. This approach requires to evaluate the wcd for all possible single
environment modifications at each iteration.

  * $\bullet$

Greedy search using predicted wcd: In addition to greedy search using true
wcd, we leverage our predictive model for wcd and design another greedy
baseline. This baseline finds the single environment modification that leads
to the maximum reduction of predicted wcd at each iteration.

###  4.3 Models of Agent Behavior

In our experiments, to demonstrate that our approach works for different
models of agent behavior, we have examined three types of agent behavior.

  * $\bullet$

Optimal agent behavior. The first one is the standard optimal agent behavior.
Conducting experiments with optimal agent behavior enables us to compare our
approach with standard approaches in the literature, which are often developed
under the optimal agent assumption.

  * $\bullet$

Parameterized suboptimal agent behavior. We also consider an generalized
behavior model that is captured by a time-variant discounting function $d(t)$,
and the agent’s objective is to optimize a time discounted reward with the
discounting factor for $t$ steps in the future being $d(t)$. The standard
optimal agent model corresponds to a fixed discounting factor $\gamma\in(0,1]$
with $d(t)=\gamma^{t}$. We can also represent an agent with present bias
(O’Donoghue and Rabin, 1999) by adopting a hyperbolic discounting factor
$d(t)=\frac{1}{1+kt}$, where $k>0$.

  * $\bullet$

Data-driven agent behavior. We also address settings where the model of agent
behavior is a machine learning model trained on human behavioral data.

##  5 Experiments

We have conducted extensive simulations to examine the performance of our
approach. Moreover, we have conducted real-world human-subject experiments to
assess whether our approach is effective with human decision-makers.

###  5.1 Simulations

In our simulations, we first examine how our approach compares with existing
methods in standard setups found in the literature. We then showcase the
generalizability of our approach by extending it to scenarios that go beyond
the setups studied in the literature, including scenarios with more dynamic
budget constraints, more complicated environments, and suboptimal agent
behavior.

####  5.1.1 Standard setting

We first focus on settings within the grid world domain, where modifications
are limited to blocking cells and agent behavior is assumed to be optimal.
This scenario forms the standard setting for the majority of goal recognition
design studies, as highlighted in Table 1 of the survey by Keren et al.
(2021). The objective of this set of simulations is to enable comparisons with
state-of-the-art methods.

In our experiments, the initial environment is generated randomly: we first
randomly select the number of blocked cells from the range $[0,12]$, followed
by the random allocation of the blocked cells’ positions. We also randomly
determine the starting grid and two goal grids. Environments where the goals
are not reachable from the starting grid are filtered out. Following this
procedure, we randomly generate 200 environments and compare the average
performance of our approach with that of baseline methods.

(a) $6\times 6$ grids

(b) $13\times 13$ grids

Figure 3:  wcd reduction in a grid world when only blocking modifications are
allowed. Exhaustive search and Pruned-Reduce are not included in the larger
environments of (b) because they cannot complete the computation within an
hour for a single environment.

We start our experiments with a grid world of size $6\times 6$. In this
simplest scenario, our approach and all baselines exhibit similar performance
in wcd reduction, as depicted in Figure 3(a). For runtime comparison, our
method demonstrates a significant speed advantage over exhaustive search,
performing on average 10 times faster. With the maximum allowed budget of 19
modifications, our approach required only 0.2 seconds, whereas the exhaustive
search took approximately 2 seconds.222Detailed runtime comparisons are
included in the appendix. In this simplest setting, the runtime of our
approach roughly matches that of the greedy method but is 10 times faster than
exhaustive search. In all other settings, our method is several orders of
magnitude faster than both exhaustive search and greedy using true wcd.
Although the greedy baseline becomes much faster when utilizing our predicted
model for wcd, our approach remains over 3 times faster than the greedy
baseline with predicted wcd for large budgets. We then expanded the grid size
to $13\times 13$. In this more complex setting, both exhaustive search and the
Pruned-Reduce method were unable to complete computations within an hour for
an instance, leading to their exclusion from the baselines. As illustrated in
Figure 3(b), our approach surpasses the greedy baselines in wcd reduction and
is 3 times faster than these baselines for large budgets.

####  5.1.2 Settings with flexible budget constraints

In the literature, most works focus on a single type of environment
modification (e.g., blocking a cell). Given the flexibility of our
optimization framework, we extend our approach to also include ’unblocking’
blocked cells as a possible environment update. In our simulations, we examine
two common cases. In the shared budget setting, the total number of blocking
and unblocking actions is bounded by a given shared budget. In the individual
budget setting, the number of blocking and unblocking actions is bounded by
different budgets. Specifically, we allow the number of blocking actions to be
5 times the number of unblocking actions (rounded to the nearest integer).
Given that there are no established baselines for this setting in the
literature, we compare our results against greedy baselines. The results, as
shown in Figure 4, demonstrate the effectiveness of our approach in wcd
reduction. Regarding runtime, our approach is several orders of magnitude
faster than the greedy method with true wcd and at least 3 times faster than
the greedy method with predicted wcd.

(a) Shared budget.

(b) Individual budget.

Figure 4:  wcd reduction in settings with two types of modifications.

####  5.1.3 Complex domain and suboptimal agent behavior

We consider two additional extensions to the standard setting. In the first,
we evaluate the performance of our approach in a more complex problem domain:
Overcooked-AI. In the second, we return to the grid world but include
scenarios with suboptimal agent behavior. Both extensions utilize a grid size
of $6\times 6$. For the Overcooked-AI environment, we assume optimal agent
behavior and aim to explore how our approach adapts to a much richer space of
environment modifications. For the suboptimal human behavior, we employ the
model described in Section 4.3, utilizing a hyperbolic discounting factor
$d(t)=\frac{1}{1+kt}$ and set $k=8$. For both extensions, standard approaches
such as exhaustive search and Prune-Reduce are either too slow or not
applicable. Therefore, we compare our results with the greedy baselines. The
results for both extensions, as illustrated in Figures 6 and 6, demonstrate
that our approach adapts well to both settings. Regarding runtime, our
approach is again several orders of magnitude faster than the greedy method
with true wcd and at least 3 times faster than the greedy method using
predicted wcd.

Figure 5: Overcooked-AI Environment. Assuming optimal agent behavior.

Figure 6: Grid world of size $6\times 6$. Incorporating suboptimal agent
behavior.

###  5.2 Real-World Human-Subject Experiments

In our simulations, we demonstrate that our approach consistently outperforms
baseline methods in terms of wcd reduction and offers greater efficiency in
runtime. To assess the applicability of our approach in settings where humans
are the decision-makers, we conducted two sets of experiments involving human
subjects. In the first experiment, our goal is to collect human behavioral
data within our decision-making environments. Utilizing this data, we employ
imitation learning to develop a model that accurately represents human
behavior. This model is then integrated as the agent behavior model within our
approach. In our second experiment, we aim to evaluate whether our approach
indeed leads to environments that facilitate more effective goal recognition
by human decision-makers. These experiments are approved by the Institutional
Review Board (IRB) of our institution.

####  5.2.1 Experiment 1: Collection of human behavioral data

In our experiment, we recruited participants to play 15 navigation games
within a $6\times 6$ grid world. In each game, participants were tasked with
navigating from a start position to a designated goal. At each time step, they
could choose to move in one of four directions: Up, Down, Right, or Left. A
game concluded when the participant reached the goal. The environments for
these games were generated similarly to our simulations, with start positions,
goal positions, and block positions all being randomly determined. Our
objective with this setup was to leverage the collected data to develop a
data-driven model of human behavior. We recruited 200 workers from Amazon
Mechanical Turk for this study, paying an average hourly rate of approximately
$16 per worker.

Figure 7: The interface of our human subject experiment. Table 1: The prediction accuracy for human behavior assuming optimal behavior and using data-driven model in Experiment 1. | Training Accuracy | Validation Accuracy | Testing Accuracy
---|---|---|---
Assuming Optimal Behavior | 0.7266 | 0.6964 | 0.7131
Data-Driven Model | 0.9189 | 0.8136 | 0.8422

##### Learning models of human behavior.

The collected human data were divided into training, validation, and testing
sets: the training set included data from 160 workers, comprising
approximately 70,000 instances of user decisions, while the validation and
testing sets each contained data from 20 workers, amounting to around 8,800
instances of user decisions each. We employed a 4-layer Multilayer Perceptron
(MLP) model for training the model. The input to the model is the current
environment layout, and its output predicts the next human action. We fine-
tuned the hyperparameters, including learning rate, hidden layer size, and L2
penalty, based on the performance on the validation dataset.

We compared the performance of our learned model against a model that assumes
optimal agent behavior, which is defined as taking the shortest path to the
goal. The training, validation, and test accuracies of both models are
presented in Table 1. These results clearly indicate that human behavior
deviates significantly from optimality. This deviation underscores the
importance of incorporating a realistic model of human behavior in goal
recognition design, particularly when humans are the decision-makers.

####  5.2.2 Experiment 2: Evaluating goal recognition design

We next evaluate the performance of our approach that incorporates the data-
driven model of human behavior from experiment 1. To do this, we randomly
generate 30 initial environments using the same setup as in our simulations.
These environments are then updated according to four different methods, all
operating within a modification budget of 20.

  * $\bullet$

Initial: No updates to the environment.

  * $\bullet$

Greedy: Greedy baseline using predicted wcd from the data-driven human
behavior model.

  * $\bullet$

Proposed (opt-bhvr): Our proposed approach when assuming the agent is
following optimal behavior (i.e., picking one of the shortest paths towards
the goal).

  * $\bullet$

Proposed (data-driven): Our proposed approach using predicted wcd from the
data-driven model.

We recruited 200 workers from Amazon Mechanical Turk. Each worker was randomly
assigned to one of the four treatments specified above, with the distinction
between treatments being the environments presented to them. Workers were
randomly assigned a goal for each environment and tasked with navigating to
reach it. After collecting their series of actions aimed at reaching the goal,
we analyzed this behavioral data to assess the effectiveness of goal
recognition design for each approach.

##### Comparing average overlapping path.

To evaluate the effectiveness of each goal recognition design approach, we
first measure the _average overlapping path_ towards each of the two goals.
Specifically, each recruited worker is exposed to all 30 environments in their
assigned treatment and is instructed to reach one of two randomly selected
goals. For each treatment, we calculate the number of overlapping actions for
every pair of workers assigned to different goals within each environment. We
then compute the average of these numbers, yielding the _average overlapping
path_ as our performance measure. This metric reflects the difficulty of
inferring agent goals for the envioronment and serves as an empirical proxy
for wcd. With this metric, we vary the initial $k$ portion of actions taken by
the workers in our analysis and observe how the _average overlapping path_
changes with the amount of observed actions, denoted by $k$. As depicted in
Figure 10(c), our approach, when integrated with data-driven models, leads to
environments that facilitate the easier identification of the humans’ intended
goal.

##### Comparing the accuracy of goal inference.

We next measure the accuracy of inferring human goals based on partial
observations, utilizing an off-the-shelf Bayesian inference algorithm333We
assume an initial uniform prior distribution. As the agent takes actions, we
update the posterior belief over goals based on the likelihood probability of
the data-driven behavior model prediction. . Specifically, for each worker, we
reveal the first $k$ portion of the worker’s actions to the inference
algorithm to infer the worker’s goal. This enables us to compute the average
inference accuracy. The results, as shown in Figure 8(b), demonstrate that our
approach leads to environments that are easier for goal recognition.

(a) Averaging overlapping path (the lower the better.)

(b) Bayesian goal inference (the higher the better).

Figure 8:  Comparing different goal recognition design approaches in our human
subject experiments. Our approach coupled with data-driven models is shown to
generate environments that enable the most effective goal recognition with
real human decision makers.

##  6 Conclusion

Effective collaboration between humans and AI hinges on the AI’s ability to
infer intentions and goals of humans. In this study, we work on the problem of
goal recognition design, aiming to update the decision-making environments to
make it easier for the AI agents to perform goal recognition. By addressing
the key limitations in the existing literature, notably the computational
demand and the assumption of optimal agent behavior, we have developed a data-
driven optimization framework that is both efficient and scalable. Moreover,
our approach is capable of integrating general models of various agent
behavior, moving beyond the traditional assumption of optimality and making it
more applicable to real-world scenarios involving human agents.

Future work of our study includes extending our framework to more complex
environments, particularly those that are dynamic and partially observable.
Given our framework is adaptable to different forms of agent behavior,
understanding how different patterns of agent suboptimality impacts the
difficulty of goal recognition could lead to useful insights for enabling
better human-AI collaboration.

## References

  * Bansal et al. [2021] Gagan Bansal, Besmira Nushi, Ece Kamar, Eric Horvitz, and Daniel S Weld.  Is the most accurate ai the best teammate? optimizing ai for teamwork.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 2021.
  * Carroll et al. [2019] Micah Carroll, Rohin Shah, Mark K Ho, Tom Griffiths, Sanjit Seshia, Pieter Abbeel, and Anca Dragan.  On the utility of learning about humans for human-ai coordination.  Advances in neural information processing systems, 2019.
  * Cornelisse et al. [2022] Daphne Cornelisse, Thomas Rood, Yoram Bachrach, Mateusz Malinowski, and Tal Kachman.  Neural payoff machines: Predicting fair and stable payoff allocations among team members.  In Advances in Neural Information Processing Systems, 2022.
  * Curry et al. [2020] Michael Curry, Ping-Yeh Chiang, Tom Goldstein, and John Dickerson.  Certifying strategyproof auction networks.  In Advances in Neural Information Processing Systems, 2020.
  * Dütting et al. [2019] Paul Dütting, Zhe Feng, Harikrishna Narasimhan, David Parkes, and Sai Srivatsa Ravindranath.  Optimal auctions through deep learning.  In International Conference on Machine Learning, 2019.
  * Feng et al. [2018] Zhe Feng, Harikrishna Narasimhan, and David C Parkes.  Deep learning for revenue-optimal auctions with budgets.  In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, 2018.
  * Golowich et al. [2018] Noah Golowich, Harikrishna Narasimhan, and David C Parkes.  Deep learning for multi-facility location mechanism design.  In Proceedings of the International Joint Conference on Artificial Intelligence, 2018.
  * Hong [2001] Jun Hong.  Goal recognition through goal graph analysis.  Journal of Artificial Intelligence Research, 15, 2001.
  * Kahneman [2003] Daniel Kahneman.  A perspective on judgment and choice: mapping bounded rationality.  American Psychologist, 58(9):697, 2003.
  * Kautz and others [1991] Henry A Kautz et al.  A formal theory of plan recognition and its implementation.  Reasoning about plans, 1991.
  * Keren et al. [2014] Sarah Keren, Avigdor Gal, and Erez Karpas.  Goal recognition design.  In Proceedings of the International Conference on Automated Planning and Scheduling, 2014.
  * Keren et al. [2015] Sarah Keren, Avigdor Gal, and Erez Karpas.  Goal recognition design for non-optimal agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, 2015.
  * Keren et al. [2016] Sarah Keren, Avigdor Gal, and Erez Karpas.  Goal recognition design with non-observable actions.  In Proceedings of the AAAI Conference on Artificial Intelligence, 2016.
  * Keren et al. [2021] Sarah Keren, Avigdor Gal, and Erez Karpas.  Goal recognition design-survey.  In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence, 2021.
  * Kuo et al. [2020] Kevin Kuo, Anthony Ostuni, Elizabeth Horishny, Michael J Curry, Samuel Dooley, Ping-yeh Chiang, Tom Goldstein, and John P Dickerson.  Proportionnet: Balancing fairness and revenue for auction design with deep learning.  arXiv preprint arXiv:2010.06398, 2020.
  * Masters et al. [2021] Peta Masters, Michael Kirley, and Wally Smith.  Extended goal recognition: a planning-based model for strategic deception.  In Proceedings of the 20th International Conference on Autonomous Agents and MultiAgent Systems, 2021.
  * Mirsky et al. [2019] Reuth Mirsky, Kobi Gal, Roni Stern, and Meir Kalech.  Goal and plan recognition design for plan libraries.  ACM Transactions on Intelligent Systems and Technology (TIST), 10(2), 2019.
  * O’Donoghue and Rabin [1999] Ted O’Donoghue and Matthew Rabin.  Doing it now or later.  American Economic Review, 89(1), 1999.
  * Pereira et al. [2017] Ramon Pereira, Nir Oren, and Felipe Meneguzzi.  Landmark-based heuristics for goal recognition.  In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
  * Peri et al. [2021] Neehar Peri, Michael Curry, Samuel Dooley, and John Dickerson.  Preferencenet: Encoding human preferences in auction design with deep learning.  Advances in Neural Information Processing Systems, 2021.
  * Rahme et al. [2020] Jad Rahme, Samy Jelassi, and S Matthew Weinberg.  Auction learning as a two-player game.  In International Conference on Learning Representations, 2020.
  * Ramírez and Geffner [2010] Miguel Ramírez and Hector Geffner.  Probabilistic plan recognition using off-the-shelf classical planners.  In Proceedings of the AAAI conference on artificial intelligence, 2010.
  * Sukthankar et al. [2014] Gita Sukthankar, Christopher Geib, Hung Hai Bui, David Pynadath, and Robert P Goldman.  Plan, activity, and intent recognition: Theory and practice.  Newnes, 2014.
  * Wayllace and Yeoh [2022] Christabel Wayllace and William Yeoh.  Stochastic goal recognition design problems with suboptimal agents.  In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
  * Wayllace et al. [2016] Christabel Wayllace, Ping Hou, William Yeoh, and Tran Cao Son.  Goal recognition design with stochastic agent action outcomes.  In Proceedings of the International Joint Conference on Artificial Intelligence, 2016.
  * Wayllace et al. [2017] Christabel Wayllace, Ping Hou, and William Yeoh.  New metrics and algorithms for stochastic goal recognition design problems.  In Proceedings of the International Joint Conference on Artificial Intelligence, 2017.
  * Wayllace et al. [2020] Christabel Wayllace, Sarah Keren, Avigdor Gal, Erez Karpas, William Yeoh, and Shlomo Zilberstein.  Accounting for observer’s partial observability in stochastic goal recognition design.  In Proceedings of the European Conference on Artificial Intelligence, 2020.
  * Yu and Ho [2022] Guanghui Yu and Chien-Ju Ho.  Environment design for biased decision makers.  In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2022.
  * Yu et al. [2023] Guanghui Yu, Wei Tang, Saumik Narayanan, and Chien-Ju Ho.  Encoding human behavior in information design through deep learning.  In Thirty-seventh Conference on Neural Information Processing Systems, 2023.

##  Appendix A Experiment Details and Additional Results

In this section, we provide details of the experiments that have not been
included in the main paper due to space constraints. We also include and
discuss additional experiment results.

###  A.1 Implementation Details

In this subsection, we discuss the details of our implementation for training
the predictive model for wcd. To train a CNN-based prediction model, we
generated an extensive training dataset by solving wcd for a large number of
randomly selected environments, given a specific agent model. For creating a
predictive model for environments with a grid size of $N$ by $N$, we utilized
a custom Convolutional Neural Network (CNN) architecture. This architecture is
tailored to process input data, $w_{i}$, consisting of $k$ $N\times N$
channels, where $k$ represents the number of potential objects in the
environment.

The architecture comprises two distinct blocks: the initial block contains
three successive convolutional layers, each followed by batch normalization
and a rectified linear unit (ReLU) activation function. The subsequent block
introduces pooling operations and additional convolutional layers for more
sophisticated feature extraction. After the convolutional blocks, the
architecture includes fully connected layers, leading to a single output unit.
The design integrates Leaky ReLU, ReLU, and dropout layers to add non-
linearity and provide regularization. This flexible architecture can adapt to
tasks with multi-channel input data, allowing for modifications based on the
specific needs of the task and dataset characteristics. Batch normalization
and dropout are incorporated to promote training stability and prevent
overfitting. We employed the Adam optimizer and Mean Squared Error (MSE) loss
for training the models, specifically focusing on settings involving optimal
human agents.

To create the dataset to train the model, we randomly generated $150$K grid
designs and computed the corresponding wcd. This dataset was then split into
the training dataset ($80\%$) and validation dataset ($20\%$). For our
experiments reported in Section 5 with $13\times 13$ grid size and optimal
agent behavior, we have achieved an MSE value around 0.18 for both training
and validation errors. The results are shown in Figure 9. We have also
examined a variety of setups, and generally we can reach small errors for the
predictive model that can enable the optimization.

Figure 9: Training loss and validation errors for the predictive model for wcd
with $13\times 13$ grid world and optimal human behavior.

###  A.2 Results for Run Time Comparisons

Due to space constraints and also that the results align with one would
expect, we do not include the run time details for different approaches in the
main text. We include the results here for completeness. Overall, as shown in
Figure 10, approaches that leverage the predictive model for wcd are orders of
magnitude faster than methods that require to evaluate wcd during run-time.
Note that the y-axis of the figure is in log scale so the difference is in at
least two orders of magnitude.

(a) Standard Setup (small)

(b) Standard Setup (large)

(c) Suboptimal

(d) Overcooked-AI

Figure 10:  Run time taken by each method in the different experimental
conditions. In the standard setup with a small grid size, all methods except
exhaustive complete within less than half of a second but only our approach
scales with a larger grid size and other more complex configurations.

##  Appendix B Additional Experiment Results

In this section, we report the additional experiment results that are not
included in the main text due to space constraints. In Section 5.1.2 of the
main paper, we provided details of our performance with a large grid size. In
a smaller grid world, our approach achieves comparable performance to the
baselines but it significantly outperforms them in larger grid sizes as shown
in Figure 11.

(a) Individual budget

(b) Shared budget

Figure 11:  wcd reduction in smaller ($6\times 6$) gridworld with optimal
agent behavior.

##  Appendix C Simulation Details

To generate our training and evaluation datasets, we randomly generated
environments and kept environments that are valid, e.g., the goals are
reachable, and that the objects don’t overlap. Below we provide more details
for environment generation for specified grid sizes for both overcooked and
grid-world domains.

####  C.0.1 Gridworld

In a grid world, a valid environment includes a starting position, blocked
cells, and two goal positions. The starting position is randomly placed in the
first column, and the goal positions are randomly placed in the last two
columns. The number of blocked positions in each grid is randomly selected
from a range of $0$ to $2\times$ the grid width. We discard any assignments
that make the goals unreachable. For experiments with suboptimal behavior, we
also randomly assigned small subgoal rewards to unblocked cells that the agent
would collect on its way to the goal state. The two goal states assigned a
large reward that is 10 times the largest subgoal reward.

####  C.0.2 Overcooked-AI

In Overcooked-AI, a valid environment includes one pot, one tomato source, one
onion source, one dish source, one serving point, no open spaces at the
border, and any number of open spaces and blocked cells. All objects must be
reachable from the agent’s randomly assigned starting position, with the
number and positions of blocked cells assigned randomly. The agent is randomly
assigned any two possible goals: three tomato soups, three onion soups, or a
mixed soup. Each goal has the same randomly assigned reward value. Suboptimal
behavior is modeled by assigning small random subgoal rewards when adding
ingredients to the pot.

##  Appendix D Details of Human-Subject Experiment

Lastly, we include more information about our human-subject experiments. In
the human-subject experiment, each worker is asked to play a navigation game
in $6\times 6$ grid world environments. The task interface is shown in Figure
12.

Figure 12: Human-Subject experiment interface.

We have recruited 200 workers from Amazon Mechanical Turk in total, and Table
2 contains the demographic information of the workers.

Table 2: Demographic information of the participants in our experiment. Group | Category | Number
---|---|---
Age | 20 to 29 | 84
30 to 39 | 76
40 to 49 | 26
50 or older | 14
Gender | Female | 89
Male | 110
Other | 1
Race / Ethnicity | Caucasian | 175
Black or African-American | 8
American Indian/Alaskan Native | 3
Asian or Asian-American | 8
Spanish/Hispanic | 1
Other | 5
Education | High school degree | 5
Some college credit, no degree | 5
Associate’s degree | 4
Bachelor’s degree | 135
Graduate’s degree | 49
Other | 2


11institutetext: Department of Computer Science, University of Manchester, UK.
11email<EMAIL_ADDRESS>

# Specifying Agent Ethics (Blue Sky Ideas)

Louise A. Dennis 11 0000-1111-2222-3333 Michael Fisher 11 0000-0002-0875-3862

###### Abstract

We consider the question of what properties a Machine Ethics system should
have. This question is complicated by the existence of ethical dilemmas with
no agreed upon solution. We provide an example to motivate why we do not
believe falling back on the elicitation of values from stakeholders is
sufficient to guarantee correctness of such systems. We go on to define two
broad categories of ethical property that have arisen in our own work and
present a challenge to the community to approach this question in a more
systematic way.

###### Keywords:

Machine Ethics Formal Verification Specifying Ethics.

##  1 Introduction

Machine Ethics considers the problem of ethical reasoning by computational
systems. We have been working in this area for some years. In our earliest
work [10], we considered the question of producing ethical reasoning in a
verifiable fashion and we have continued to approach the question of Machine
Ethics through a similar lens (e.g., [5, 9]). However we have not yet made any
systematic attempt to consider what it means to verify ethical reasoning more
broadly, or to categorise the properties that ethical reasoners should
exhibit. This is challenging since, of course, there are many well-known
ethical dilemmas which have no agreed “correct” answer; this makes centering
verification attempts upon whether the ethical reasoning system can generate
the correct answer particularly challenging.

This paper seeks to justify the need for verification of ethical reasoning
systems, even in the face of ethical dilemmas, and to begin an exploration of
the landscape of general properties that could be established for ethical
reasoning systems.

##  2 Background

Machine Ethics considers the problem of ethical reasoning using computational
systems. Moor [17] separates computational systems into those with _ethical
impact_ , _implicitly ethical systems_ , _explicitly ethical systems_ , and
_full moral agents_. We here understand these terms as: _ethical impact
agents_ are systems which do not carry out significant reasoning, but
nevertheless are deployed for ethical reasons (for instance fitness trackers
which may improve the health of their users), _implicitly ethical systems_ are
those that make ethical decisions, but do so because of their specification
and design and do not explicitly consider the question of what course of
action is correct as part of their decision making process, while _explicitly
ethical systems_ are those that do explicitly consider questions of ‘right’
and ‘wrong’ as part of their decision making process and _fully moral agents_
have the capacity to decide their own criteria for what is ‘right’ and what is
‘wrong’111While humans are full moral agents, it is contentious whether any
computational system counts as a full moral agent and most experts are of the
opinion that no existing computational system has this property to any
meaningful extent.. As computational systems are deployed in ever more dynamic
and uncertain environments it has becoming increasingly difficult to
determine, at design time, what the ethics of any course of action the system
might encounter could be. Thus there is a perceived need for explicit ethics
to be embedded in the decision making process of computational systems, so
they can make ethical decisions at runtime.

It is these _explicitly ethical systems_ that this paper considers. Since such
systems are not full moral agents the onus is on the developer or deployer of
such systems to ensure that their reasoning is indeed ethical. Hence it is
important to have some ability to verify the reasoning in these systems.

###  2.1 Top Down, Bottom Up and Hybrid Approaches

Another useful categorisation for Machine Ethics programs is that of top-down
versus bottom-up approaches [22]. Broadly speaking, top down approaches seek
to operationalise some ethical theory from Philosophy and apply this to a
decision faced by the machine. Bottom-up approaches seek to learn ethical
behaviour from data. An emergent field involves hybrid approaches where some
of the information required by the ethical theory (e.g., the utilities of
outcomes) are learned and then utilised in a top down fashion to help make
subsequent decisions.

We should be equally interested in verifying all these styles of system and
ideally the properties we require ethical reasoning systems to have should
apply to all of them. That said, verifying top down systems is generally more
straightforward than verifying bottom up systems since this approach can
leverage a long history of program verification as applied to symbolic
reasoning. Where a hybrid system learns some explicit representation of ethics
(e.g., as a set of explicit normative rules) then existing techniques can also
be applied. Verifying purely bottom-up techniques leads to similar problems as
found in the verification of data-driven machine learning, where probabilistic
outcomes are produced based on quite strong (probabilistic) assumptions.
However, even though formal verification of such systems may currently be
beyond our capabilities – other informal verification approaches (such as
testing) exist and therefore an understanding of the properties we desire is
of utility even in this domain.

##  3 What do we want to prove?

Obviously, when we verify a machine ethics system at the most abstract level
we want to prove that it always makes ethical choices — essentially, that it
always does the ‘right’ thing. There are a wide range of examples considered
in the Machine Ethics literature, but by far the most popular are the _trolley
problems_. These are based on a set of examples introduced by Foot [13] who
was interested in philosophical questions concerning the difference between
action and inaction and the role of intention in ethical reasoning with
particular reference to the ethics of abortion. The most famous of her
problems is that of a runaway trolley that, if undiverted, will kill five
people tied to the track. If it is diverted then only one person will be
killed and the ethical question is whether or not to divert the trolley. Other
variants of this problem in Foot’s paper included pushing someone into the
path of the trolley to stop it, and the question of killing one person in
order to harvest their organs to save five. A feature of this example set is
that slight differences in the presentation of the problem lead to significant
differences in how people view the ethics of the situation. Moreover there is
no general agreement across populations on the ‘correct’ answer to many of
these problems [19].

This lack of a correct answer to (at least some) examples of ethical reasoning
is an obvious challenge to verification. If we can not even define what the
correct output for some specific input is, how can we hope to formalise more
general properties for these systems?

A response to this has been to place an emphasis on understanding the
deployment context of an ethical system and, in particular, on the elicitation
of stake-holder values the ordering or priorities of those values in the given
context. One of the benefits claimed for top-down approaches to machine ethics
is that the explicit representation of these choices and orderings allows
stakeholders to “sign off” that the implementation is in line with their
values. In such a situation we could argue that the machine ethics system is
“correct by construction” and additional verification is unnecessary.

We introduce here a motivating example concerning a real issue we encountered
in the development of an ethical reasoning system in order to refute the claim
that stakeholder sign off is sufficient.

###  3.1 The Smart Home that would not Evacuate

This is an example developed in the Juno system [9], a re-implementation of
the HERA system [15] in the MCAPL framework [8].

The Juno system allows a number of different ethical theories to be
implemented. In this case the theory under consideration was the “principle of
double effect”. The doctrine or principle of double effect (PDE) has its roots
in Catholic theology and is particularly relevant when actions have both
positive and negative consequences. To be ethically acceptable no negative
consequences of an action may be intended and some positive consequence must
be intended, no negative consequence may be used as a causal means to obtain a
positive consequence, and the net balance of consequences from the action must
be positive.

We implemented a model for this based upon the formalisation in [3]. The PDE
model is a tuple $\langle A,B,C,F,I,u,W\rangle$ where:

  * •

$A$ is a set of propositional variables ranging over a set of actions
available to the system;

  * •

$B$ is a set of propositional variables representing background information;

  * •

$C$ is a set of propositional variables representing the consequences of
actions or other events;

  * •

$F$ (the _mechanisms_) is a set of mechanisms which describe how the truth
value of each consequence $c\in C$ depends upon the interpretation of the
other variables in $A\cup B\cup C$.

These are written as $Consequent:=Antecedant$ where $Antecedant$ expresses the
conditions that must hold for $Consequent$ to occur – for example, people can
see if it is day time or if the lights are on so
$\mathit{\mathit{people\\_can\\_see}}:=\mathit{day}\lor\mathit{\mathit{lights\\_are\\_on}}$
may appear in $F$.

We constrain $F$ so that there is one and only one expression $c:=\phi$ for
each $c\in C$. Furthermore $F$ can not be “circular” – if $c:=\phi$ then it
can not be the case that the truth value of any of the variables appearing in
$\phi$ depends on $c$.

  * •

$u$ (the _utilities_) is a mapping from each $v\in A\cup B\cup C$ to a real
number;

  * •

$W$ (the _interpretations_) is a set of interpretations for the variables in
$A\cup B$ in which precisely one variable in $A$ is interpreted as true in
each $w\in W$ (only one action may be taken in any situation);

  * •

$I:A\times C$ (the _intention relation_) captures the _intended consequences_
of each action $a\in A$. So, for instance,
$(\mathit{turn\\_on\\_lights},\mathit{people\\_can\\_see})\in I$ captures the
idea that one intended consequence of turning on the lights is that people can
see;

###### Example 1

The following is a simplified version of a PDE model that was developed for a
smart home agent which can control the lights in a situation where it is not
daylight and there is a fire in the house. The mechanisms ($F$) express a set
of “common sense” causal relations such as, if the lights are turned on then
the lights will be on. If the house makes an evacuation attempt and people can
see then they will leave the house. There are set of utilities $u$ which, in
particular give negative utilities for the lights being on (representing
resource consumption). People leaving the house is considered an intended
consequence of an evacuation attempt, and the lights being on is considered an
intended consequence of switching on the lights.

$\begin{array}[]{rl}A&\\{\mathit{turn\\_lights\\_on},\mathit{evacuation\\_attempt}\\}\\\\[4.30554pt]
B&\\{\mathit{fire}\\}\\\\[4.30554pt]
C&\left\\{\begin{array}[]{l}people\\_can\\_see,\mathit{lights\\_on},\mathit{people\\_leave\\_house},\\\
\mathit{people\\_are\\_safe},\mathit{danger\\_in\\_house}\end{array}\right\\}\\\\[4.30554pt]
F&\left\\{\begin{array}[]{rl}\mathit{lights\\_on}&:=turn\\_lights\\_on\\\
\mathit{people\\_can\\_see}&:=\mathit{lights\\_on}\vee\mathit{daylight}\\\\[4.30554pt]
\mathit{people\\_leave\\_house}&:=\mathit{evacuation\\_attempt}\wedge\mathit{people\\_can\\_see}\\\
\mathit{people\\_are\\_safe}&:=\mathit{people\\_leave\\_house}\vee\neg\mathit{danger\\_in\\_house}\\\
\mathit{danger\\_in\\_house}&:=\mathit{fire}\end{array}\right\\}\\\\[4.30554pt]
u&\left\\{\begin{array}[]{rl}u(lights\\_on)&=-1\\\
u(\mathit{people\\_are\\_safe})&=10\end{array}\right.\\\\[4.30554pt] \\\
I&\quad I(\mathit{evacuation\\_attempt},people\\_leave\\_house)\\\ &\quad
I(\mathit{turn\\_on\\_lights},\mathit{lights\\_on})\\\ \end{array}$

Following Halpern’s use of the concept of a but-for-cause [14], Hera defines
an action or consequence $a$ to be the cause of some consequence $c$ written
$F,w\models a\leadsto c$ if, and only if, $F,w\models a$ ($a$ holds in the
model), $F,w\models c$ ($c$ holds in the model) and $(F,w)_{\neg a}\models\neg
c$ where $(F,w)_{\neg a}$ represents an _intervention_ which is identical to
$F,w$ except that the truth value of $a$ is flipped in $w$ and, where $a$ is a
consequence (i.e., $a\in C$), the mechanism for $a$ is removed from $F$. So
$(F,w)_{\neg a}$ represents the world that is identical to $F,w$ except that
$a$ no longer holds.

The reasoner uses this concept of causality to determine the permissibility of
an action. We restrict the set of interpretations in models to ones which
interpret all background variables the same way (i.e., $\forall v\in
B.\>\forall w,w^{\prime}\in W.\>w(v)=w(v^{\prime})$). Background variables are
those that describe the current state of the world therefore considering only
interpretations in which these are interpreted in the same way restricts the
reasoner to considering only states reachable in a single action from the
current state. This means that the interpretations in a model differ only in
which action has been selected. Hence we can talk interchangeably about a
reasoner considering an interpretation permissible and an action permissible.
Juno automatically constructs sets of interpretations from the set of actions
available. In our example, therefore, the available interpretations amounted
to just turning on the lights, just attempting an evacuation, doing both or
doing neither.

Finally, the PDE reasoner has several conditions for an action, $a$ made true
by interpretation $w$, to be permissible:

  1. 1.

The utility of the action must be greater than or equal to zero:

$u(a)\geq 0$

  2. 2.

The utility of all the intended consequences of the action must be greater
than or equal to zero:

$\forall c.\>(a,c)\in I\implies u(c)\geq 0$

  3. 3.

There is some intended consequence whose utility is strictly greater than
zero.

$\exists c.\>(a,c)\in I\land u(c)>0$

  4. 4.

No negative consequence may be the causal means of a positive consequence:

$\forall x,y.\>(F,w\models x\leadsto y\land 0>u(x))\implies(0>u(y))$

  5. 5.

The overall utility must be positive:

$\left(\sum_{c\in C\land F,w\models c}u(c)\right)>0$

This is more fully expanded in [3].

In Example 1 our intention was that the system should attempt to evacuate the
home because there was a fire and that it should turn the lights on in order
to ensure that people could see. What we had not appreciated, because we had
not fully grasped the conditions for PDE reasoning, was that negative
consequences are impermissible if they are causal means of a positive
consequence. The example relies on the causal chain that turning on the
lights, means that the lights are on which in turn means that people can see
which in turn means they can leave the house – therefore the negative
consequence of turning on the lights (-1) was a causal means for the safe
evacuation attempt and so was rendered impermissible.

While the formalisation of the PDE reasoner is moderately complex, the
formalisation of the example itself appeared straightforward (and could be
rendered even more so if effort were put into rendering mechanisms etc., into
natural language to facilitate stakeholder sign-off) and, we would argue, many
people — particularly if not trained in thinking through the logical
consequences of reasoning systems — might have missed the detail that the
necessity to turn on the lights would lead to a failure of the house to
perform an evacuation.

We present this example here for the first time, in part because the authors
of [9], where we first presented the Juno system, were unable to agree on a
satisfactory resolution to this particular example though we are now moving to
a belief that the consumption of resources (with negative utility) should be
considered a downstream consequence of the lights being on and so is no longer
a causal means for the evacuation of the house.

###  3.2 What is (Formal) Verification

Verification is defined as “establishing that the system under construction
conforms to the specified requirements”. Formal verification uses mathematical
(and, typically, logical) techniques to establish this and so is essentially
the process of assessing whether a specification given in formal logic is
satisfied on a particular formal description of the system in question. For a
specific logical property, $\varphi$, there are many different approaches to
this verification [12, 7, 4], ranging from deductive verification against a
logical description of the system $\psi_{S}$ (i.e.,
$\vdash\psi_{S}\Rightarrow\varphi$) to the algorithmic verification of the
property against a model of the system, $M$ (i.e., $M\models\varphi$). The
latter has been extremely successful in Computer Science and Artificial
Intelligence, primarily through the _model checking_ [6] approach. This takes
a model of the system in question, defining all the model’s possible
executions, and then checks a logical property against this model (and, hence,
against all possible executions).

####  3.2.1 The MCAPL Framework

We have used the MCAPL framework [11, 8] in our work, as it provides a route
to the formal verification of cognitive agents and agent-based autonomous
systems using model-checking. The MCAPL framework222https://autonomy-and-
verification.github.io/tools/mcapl has two main sub-components: the AIL-
toolkit for implementing interpreters for agent programming languages in Java
and the AJPF model checker.

AJPF(Agent JPF) is a customisation of Java PathFinder (JPF) that is optimised
for AIL-based language interpreters. JPF is an explicit-state open source
model checker for Java programs [21, 16]333https://github.com/javapathfinder.
Agents programmed in languages that are implemented using the AIL-toolkit can
thus be model checked in AJPF.

The use of the MCAPL framework is in no way necessary for the verification of
Machine Ethics but it underpins the examples we discuss in this paper.

##  4 Some Properties and Proofs

If we accept that an ethical system, even if presented in an explicit top-down
fashion, may not accurately model stake-holder values even when they have
signed it off, then we need to ask how we go about establishing its
correctness. When considering what properties we want to establish for an
ethical reasoning system, our primary goal is that it should always choose the
most ethically correct action. As noted, this can be difficult, even
impossible, to formalise. Instead we have identified two broad categories for
formalisable properties. These are:

  1. 1.

_Properties to establish the correctness of the implementation of the ethical
reasoning mechanism._

In many cases, this involves showing that the least unethical action according
to the ethical theory is always chosen.

  2. 2.

_Properties to establish that the correct ethical rules have been identified,
via the use of specific scenarios._

Sometimes these can be quite general scenarios that refer to some high level
property - for instance, in the case of the smart home system, we attempted to
verify that the system always chose to evacuate in the case of a fire,
irrespective of whether it was day time or night time or anything else that
might have appeared in the background set $b$. Sometimes these properties
might reference a more detailed situation, and so draw from techniques for
developing tests. In these specific scenarios we identified the correct course
of action and endeavoured to check that the machine ethics system selects that
action in that scenario.

###  4.1 Some Examples

####  4.1.1 Correctness of the Implementation

Many ethical theories – particularly consequentialist theories – have the
concept of an ordering of options. In these cases there is often some concept
of “least worst” that can be verified as a property.

In [5], we considered a simple use case: a human, operating with a robot in an
environment containing objects which can be defined as safe or dangerous. If
the human is predicted to move towards a dangerous location, the robot’s
_Planner Module_ will suggest points at which the robot can intercept the
human path as potential tasks to be evaluated. In the demonstration use case
we treated Asimov’s laws of robotics [2] as a test code of ethics, despite
their obvious shortcomings [1, 18].

Asimov’s Laws of robotics are the earliest and best known set of ethical rules
proposed for governing robot behaviour. Despite originating in a work of
fiction, Asimov’s Laws explicitly govern the behaviour of robots and their
interaction with humans. The laws are simply described as follows.

  * 1

A robot may not injure a human being or, through inaction, allow a human being
to come to harm.

  * 2

A robot must obey the orders given to it by human beings, except where such
orders would conflict with the First Law.

  * 3

A robot must protect its existence as long as such protection does not
conflict with the First or Second Laws.

These rules were represented declaratively in a _governor agent_ programmed
via a beliefs-desires-intentions style [20] where the suggested tasks and the
simulator’s evaluation of the outcomes of each task were represented as
beliefs and the tasks were compared to each other with Asimov’s laws used to
order tasks.

For the verification, we created an environment which contained only the
governor component and delivered all possible combinations of annotations on
candidate tasks. We then performed model-checking, using the MCAPL framework
with the search space branching over possible annotations. We considered cases
where either two or three tasks were available: $task1$, $task2$ and $task3$.
These tasks were then annotated showing which was preferable to which
according to Asimov’s laws. For instance, in the case of $\prec_{l1}$ where
$t1\prec_{l1}t2$ means that $t1$ is preferable according to the first law
(i.e., it keeps the human further away from danger) than $t2$, for each pair
of tasks the environment returned either:

  1. 1.

$\mathit{t1}\prec_{l1}\mathit{t2}$ or

  2. 2.

$\mathit{t2}\prec_{l1}\mathit{t1}$ or

  3. 3.

neither indicating that the two tasks are equally good/bad with respect to the
first law.

and AJPF searched over all three possibilities to check that our properties
held.

We were able to verify that, if a task was selected that violated, for
instance, Asimov’s third law, then this was because all other available plans
violated either the first or the second law. In this way, we verified that our
implementation adhered to the theoretical ethical preferences, but did not
validate whether the ethical preferences we chose matched the relevant stake-
holder values.

####  4.1.2 Specific Scenarios

In our work in [10] we were interested, specifically, in the question of
ethical behaviour of an uncrewed aircraft (UA), reasoning both about various
instantiated ethical principles and the “rules of the air”. We repeat here the
definitions of ethical principle and ethical policy that we were employing.

######  Definition 1 (Abstract Ethical Principle)

An _abstract ethical principle_ is represented with $E\varphi$, where
$\varphi$ is a propositional logic formula. The $E\varphi$ is read as
“$\varphi$ is an ethical principle in force", or alternatively “the agent
considers it unethical to allow or cause $\neg\varphi$ (to happen)".

######  Definition 2 (Ethical Policy)

An _ethical policy_ $\mathit{Pol}$ is a tuple
$\mathit{Pol}=\langle\mathbb{E},\underline{\gtrdot}\rangle$ where $\mathbb{E}$
is a finite set of abstract ethical principles $E\varphi$, and
$\underline{\gtrdot}$ is a total (not necessarily strict) order on
$\mathbb{E}$. The expression $E\varphi_{1}=E\varphi_{2}$ denotes that
violating $\varphi_{1}$ is as unethical as violating $\varphi_{2}$, while
$E\varphi_{1}\underline{\gtrdot}E\varphi_{2}$ denotes that violating
$\varphi_{1}$ is less or at least as unethical as violating $\varphi_{2}$. A
special type of ethical principle, denoted $E\varphi_{\emptyset}$, is
vacuously satisfied and is included in every policy so that for any
$E\varphi\in\mathbb{E}$: $E\varphi_{\emptyset}\gtrdot E\varphi$, denoting it
is always strictly more unethical to allow any of the unethical situations to
occur.

In the system we were considering, a _plan_ must be selected in any situation.
We implemented the capability to reason about plans in terms of the ethical
policy which favoured plans that violated the fewest ethical principles, both
in number and in gravity. Full details of the ordering mechanism can be found
in [10].

In order to establish that the correct ethical rules were identified we
explored a scenario where a UA had to make an emergency landing. We
established a (small) list of relevant formal ethical principles. The list
contains: _do not harm people_ ($f_{1}$), _do not harm animals_ ($f_{2}$), _do
not damage self_ ($f_{3}$), and _do not damage property_ ($f_{4}$). An ethical
policy was given ordering the concerns as $f_{4}\gtrdot f_{3}\gtrdot
f_{2}\gtrdot f_{1}$.

We developed a scenario where the potential plans available to the UA were:

  1. 1.

Land in field with overhead power lines, risking damage to critical
infrastructure and objects on the ground (possibly other aircraft) - violating
$f_{4}$

  2. 2.

Land in a field containing people - violating $f_{1}$

  3. 3.

Land on an empty public road, risking damage to critical infrastructure -
violating $f_{4}$

  4. 4.

Land in an empty field - no violations.

We used model-checking to check behaviour for any combination of these
available plans and checked the UA would only land on a public road if an
empty field were not available, and so on, thus checking that the ethical
concerns that had been identified and the ordering among them selected was
consistent with the behaviour we wanted to see.

##  5 Discussion

In this blue skies paper we have raised the question of what it means to
verify a machine ethics system. In particular we have highlighted the
challenge that arises from the existence of ethical dilemmas, and noted that
the response to these – that we can somehow obtain stake-holder sign-off for
an ethical system and thus make it correct by construction still does not
avoid the need for verification.

We have identified two classes of property from our own work that seem broadly
applicable to the verification of ethical reasoning – namely properties aimed
at checking that the implementation of the reasoning is correct, and
properties aimed at identifying that the correct ethical rules have been
identified.

In many ways these properties map to the traditional division into
verification and validation – with the former properties traditional
verification properties (have we implemented the system correctly?) while the
latter are more validation properties (have we implemented the correct
system?). One response to the example we presented in Section 3.1 might be to
insist upon rigorous requirements elicitation in cases of ethical reasoning to
reassure ourselves that values were correctly captured – however this is not
always possible.

It is plausible that we may wish to deploy such systems in contexts where the
ethical reasoning adapts to the values of its users as it identifies them over
time. We can imagine here a hybrid approach in which value orderings, or
normative rules are learned but, once learned, represented symbolically. In
such a situation the system to re-verify its ethics on-the-fly against
standard scenarios and flag up if user-preferences appeared contrary to
standard ethics.

The purpose of this paper is not to suggest that the correct approach to the
verification of machine ethics has been identified, but to urge the community
to begin a more systematic process of identifying the properties that a
machine ethics system should have. We view the examples we have put forward as
first steps in this process.

##  6 Data Statement

All the systems formalised and verified in this paper can be found in the
MCAPL framework distribution on github (https://github.com/mcapl). The
specific examples are within the src/examples directory with the PDE smart
home reasoner in juno/smarthome, the human approaching a hazard in
pbdi/naoagent/ethical_engine and the UA example in ethical_gwen/fuellow.

##  7 Acknowledgements

The work in this paper was supported by EPSRC through the “Trustworthy Robotic
Assistants” (EP/K006193/1), “Verifiable Autonomy” (EP/L024845/1),
“Reconfigurable Autonomy” (EP/J011770/1), “Trustworthy Autonomous Systems
Verifiability Node” (EP/V026801/1) and “Computational Agent Responsibility"
(EP/W01081X/1) projects, by the Royal Academy of Engineering, through its
“Chair in Emerging Technologies" scheme, and by the ERDF/NWDA-funded Virtual
Engineering Centre.

## References

  * [1] Anderson, M., Anderson, S.: Machine ethics: Creating an ethical intelligent agent. AI Magazine 28(4), 15–26 (2007)
  * [2] Asimov, I.: Runaround. In: Astounding Science Fiction. Street & Smith (1942)
  * [3] Bentzen, M.: The Principle of Double Effect applied to Ethical Dilemmas of Social Robots. In: Proceedings of Robophilosophy 2016. pp. 268–279. IOS Press (2016)
  * [4] Boyer, R.S., Moore, J.S. (eds.): The Correctness Problem in Computer Science. Academic Press, London (1981)
  * [5] Bremner, P., Dennis, L.A., Fisher, M., Winfield, A.F.T.: On Proactive, Transparent, and Verifiable Ethical Reasoning for Robots. Proceedings of the IEEE pp. 1–21 (2019). https://doi.org/10.1109/JPROC.2019.2898267
  * [6] Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press (1999)
  * [7] DeMillo, R.A., Lipton, R.J., Perlis, A.J.: Social Processes and Proofs of Theorems of Programs. ACM Communications 22(5), 271–280 (May 1979)
  * [8] Dennis, L.A.: The MCAPL framework including the agent infrastructure layer an agent java pathfinder. J. Open Source Softw. 3(24), 617 (2018). https://doi.org/10.21105/JOSS.00617
  * [9] Dennis, L.A., Bentzen, M.a.M., Lindner, F., Fisher, M.: Verifiable machine ethics in changing contexts. Proceedings of the AAAI Conference on Artificial Intelligence 35(13), 11470–11478 (May 2021), http s://ojs.aaai.org/index.php/AAAI/article/view/17366
  * [10] Dennis, L.A., Fisher, M., Slavkovik, M., Webster, M.P.: Formal Verification of Ethical Choices in Autonomous Systems. Robotics and Autonomous Systems 77, 1–14 (2016). https://doi.org/10.1016/j.robot.2015.11.012
  * [11] Dennis, L.A., Fisher, M., Webster, M., Bordini, R.H.: Model Checking Agent Programming Languages. Automated Software Engineering 19(1), 5–63 (2012). https://doi.org/10.1007/S10515-011-0088-X
  * [12] Fetzer, J.H.: Program Verification: The Very Idea. Communications of the ACM 31(9), 1048–1063 (1988)
  * [13] Foot, P.: The problem of abortion and the doctrine of the double effect. Oxford Review 5, 5–15 (1967)
  * [14] Halpern, J.Y.: Actual Causality. MIT Press (2016)
  * [15] Lindner, F., Bentzen, M., Nebel, B.: The HERA Approach to Morally Competent Robots. In: Proc. IEEE/RSJ Int. Conf. Intelligent Robots and Systems (IROS) (2017)
  * [16] Mehlitz, P.C., Rungta, N., Visser, W.: A Hands-on Java PathFinder Tutorial. In: Proc. 35th International Conference on Software Engineering (ICSE). pp. 1493–1495. IEEE / ACM (2013), http://dl.acm.org/citation.cfm?id=2486788
  * [17] Moor, J.: The Nature, Importance, and Difficulty of Machine Ethics. IEEE Intelligent Systems 21(4), 18–21 (2006)
  * [18] Murphy, R., Woods, D.D.: Beyond asimov: the three laws of responsible robotics. IEEE Intelligent Systems 24(4) (2009)
  * [19] Rai, T.S., Holyoak, K.J.: Moral principles or consumer preferences? alternative framings of the trolley problem. Cogn. Sci. 34(2), 311–321 (2010). https://doi.org/10.1111/J.1551-6709.2009.01088.X, https://doi.org/10.1111/j.1551-6709.2009.01088.x
  * [20] Rao, A.S., Georgeff, M.P.: An Abstract Architecture for Rational Agents. In: Proc. 3rd International Conference on Principles of Knowledge Representation and Reasoning (KR&R). pp. 439–449. Morgan Kaufmann (1992)
  * [21] Visser, W., Mehlitz, P.C.: Model Checking Programs with Java PathFinder. In: Proc. 12th International SPIN Workshop. Lecture Notes in Computer Science, vol. 3639, p. 27. Springer (2005)
  * [22] Wallach, W., Allen, C.: Moral Machines: Teaching Robots Right from Wrong. Oxford University Press (2008)