# Governing Automated Vehicle Behavior

Nelson De Moura Martins Gomes

► To cite this version:

Nelson De Moura Martins Gomes. Governing Automated Vehicle Behavior. Computers and Society [cs.CY]. Sorbonne Université, 2021. English. NNT: 2021SORUS169. tel-03709568v2

HAL Id: tel-03709568

https://theses.hal.science/tel-03709568v2

Submitted on 25 Nov 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
## SORBONNE UNIVERSITÉ

École doctorale 130: Informatique, Télécommunications et Électronique
Institut des Systèmes Intelligents et de Robotique

### Thèse de Doctorat

Pour obtenir le grade de

### DOCTEUR en informatique

Soutenance présenté par

Nelson DE MOURA MARTINS GOMES

## GOVERNING AUTOMATED VEHICLE BEHAVIOR

Soutenue le 29 juin 2021 devant le jury composé de :

Dr. Fawzi NASHASHIBI

Dr. Catherine TESSIER

Pr. Stéphane CHAUVIER

Pr. Véronique CHERFAOUI

Dr. Ebru BURCU DOGAN

Pr. Jean-Gabriel GANASCIA

Pr. Alan WINFIELD

Pr. Raja CHATILA

Rapporteur

Rapporteur

Examinateur

Examinateur

Examinateur

Examinateur

Examinateur

Directeur de thèse

INRIA

Onera

Sorbonne Université

Université de Technologie
de Compiègne

Institut VEDECOM

Sorbonne Université

UWE Bristol

Sorbonne Université
<figure><img src="image_2.png" /></figure>
# Abstract

From a societal point of view, automated vehicles (AV) can bring many benefits, such as an increase of road safety and a decrease of congestion (Fagnant and Kockelman, 2015; Schwarting et al., 2018). However, due to the highly dynamic environments these vehicles can encounter, technical concerns about their feasibility and ethical concerns about their actions' deliberation, explainability and consequences (Lin, 2016; Gerdes and Thornton, 2016) seems to damper the enthusiasm and optimism that once ruled the automotive sector and the public opinion (Boudette, 2019).

This thesis addresses the core questions surrounding autonomous vehicles today: how they should account the road users sharing the same environment in their decision making and also how they should deliberate to act in dilemma situations. Firstly, a decision making process for the autonomous vehicle under general situations is proposed, and then, as a particular situation, the deliberation under certain collision, with other vehicles, pedestrians or static objects, is implemented.

The discussion focus on an hypothetical AV implementation in urban environments, where velocity is limited and many road users might interact with each other. Therefore, the behavior from other road users is a significant source of uncertainty for the AV (Madigan et al., 2019). In a first attempt to propose a decision making algorithm for the AV that contemplate both generic and dilemma situations, the behavior of road users was considered static during the execution of an AV policy.

A finite horizon MDP, with states representing only the AV's configuration, was implemented, leaving the road users' configuration to be accounted in the reward function as an evaluation of how much risk and performance each action would bring. With this state definition the transition probability was defined as static scalar constant, given that it would represent only the probability of the AV reaching an expected next state given a current one and an action. A dilemma scenario was defined as when all available actions for the AV would result in an accident, which is predicted by the outcome calculated in the reward function estimation. The results of this implementation can be seen in (de Moura et al., 2020).
In the aforementioned article and also in (Evans et al., 2020), a measure of the risk in an
accident, called harm, was proposed. It accounts for the difference of velocity produced by the
collision and for the vulnerability between the involved road users. This last parameter is proposed
to be calculated via a statistical accidentology study from a region or a country, classifying the
severity of a collision according to the difference of velocity between the concern road users.
The harm represents a scaled measure of risk for each road user due to a collision and is used to
deliberate on which action the AV should execute in a dilemma scenario situation.

On the subject of ethical deliberation, (de Moura et al., 2020) and (Evans et al., 2020) take different approaches. The former adapts the general idea of certain ethical theories (ralwsian contractualism, utilitarianism and egalitarianism) into a mathematical formulation to choose the action based on the expected harm it would produce, which is then used as a deliberation method by the MDP for a state that presents a dilemma situation, instead of the usual value iteration criteria for general situations. The method proposed by (Evans et al., 2020) adds to the harm the concept of ethical valence, which represents the degree of social acceptability that is attached to the claims of the road users in the environment. Then both measures are used by defined moral profiles to deliberate on an action.

Coming back to the question about other road users’ behaviors uncertainty, a different approach was considered for such parameter to the AV’s decision making. Using an intersection as use case, a multi-agent simulation was implemented, with each decision making from other road users (pedestrians and vehicles) being executed by a set of deterministic rules, to represent the behavior of a standard driver/pedestrian. To estimate the intentions of other users, the AV compares its predictions by assuming an intention vector and updating an instance of a Kalman filter for each user. The distance between the estimate and the observation defines the probability that a user has the assumed intention. To take into account the interactions between the different users, we adopt a game theoretic approach with incomplete information (Harsanyi, 1967; Harsanyi, 1968b) to then calculate the Nash’s equilibrium, giving the final AV’s strategy.

**Keywords:** automated vehicles, decision-making, ethical decision-making, artificial moral agents, game theory, behavior prediction
# Résumé

D'un point de vue sociétal, le véhicule à conduite automatisée (VA) peut nous offrir plusieurs avantages par rapport au trafic constitué seulement de véhicules avec conducteur, comme une augmentation de la sécurité routière et une diminution de la congestion routière (Fagnant and Kockelman, 2015; Schwarting et al., 2018). Cependant, à cause de l'environnement dynamique et complexe où ces systèmes doivent opérer, des questionnements concernant leur sûreté de fonctionnement et leur comportement vis-à-vis des autres utilisateurs se posent, en particulier sur la capacité du VA de délibérer sous dilemme éthique, d'expliquer ses choix et de mesurer les conséquences de ses actions (Lin, 2016; Gerdes and Thornton, 2016). Ces questions ont finalement ralenti l'enthousiasme naïf et inouï qui avait conquis l'opinion publique et une partie des constructeurs automobiles (Boudette, 2019).

Deux sujets sont abordés dans cette thèse concernant les défis du déploiement du VA dans le monde réel: comment prendre en compte les autres utilisateurs de la route dans le processus de prise de décision du VA dans un environnement urbain, et comment le VA doit délibérer sous une situation de dilemme éthique. D'abord un algorithme de prise de décision conçu pour traiter des situations génériques est proposé; ensuite, à partir de cet algorithme et dans le cadre d'une situation spécifique, quand une collision avec des autres véhicules ou des piétons devient inévitable, la délibération éthique est traitée.

La discussion concernant la prise de décision du VA est limitée à l'environnement urbain, où la vitesse est limitée et plusieurs utilisateurs, protégés par des coques de métal (véhicules) ou pas (piétons, cyclistes, etc.) interagissent les uns avec les autres. Le comportement des autres usagers est une source majeure d'incertitude pour le VA. Dans une première proposition d'un algorithme de prise de décision pour le VA, le comportement des autres utilisateurs a été considéré comme statique.

Un processus de décision Markovien (Markov Decision Process, MDP) fini avec des états qui représentent seulement la configuration du VA a été implémenté, avec la prise en compte de la position des autres utilisateurs dans l'évaluation de chaque action action. Cette évaluation permet aussi de détecter les situations de dilemme éthique, qui sont traités de deux façons différentes: avec une optimisation (minimisation) du dommage (*harm* en anglais) prévu pour une collision
dans le cadre d'un processus délibération défini à partir d'une théorie éthique (de Moura et al., 2020) ou en considérant des profils moraux qui prennent en compte la valence éthique de chaque utilisateur et le dommage prévu (Evans et al., 2020).

La probabilité de transition entre états a été considérée comme statique pour le processus de prise de décision proposé. Cependant elle est en réalité dépendante du comportement de chaque utilisateur individuellement et de ses interactions avec les autres. Dans une généralisation de la démarche précédente, nous avons introduit une modélisation pour prédire ces comportements.

Une simulation multi-agents est nécessaire pour que l'interaction avec les autres usagers soit bien représentée. Pour estimer les intentions des autres usagers, le VA compare ses prédictions en utilisant un vecteur d'intentions et en mettant à jour un filtre de Kalman pour chaque usager. L'écart entre l'estimation et l'observation définit la probabilité qu'un utilisateur ait l'intention prédite. Pour tenir compte des interactions entre les usagers, nous adoptons une formulation the théorie des jeux avec informations incomplètes qui permet de fournir le comportement de l'ensemble des agents (Harsanyi, 1967; Harsanyi, 1968b). Le point d'équilibre de Nash permet d'obtenir la stratégie finale du VA.

**Mots-clés:** véhicule automatisé, prise de decision, prise de décision éthique, agents moraux artificiel, théorie des jeux, prédiction de comportement
Remerciements

Primeiro eu gostaria de agrader meus pais, Nelson e Daisy, pela confiança que eles sempre
me deram e pelo apoio incondicional, em todos os momentos, desde os tempos da natação com
treinos às 4:00, passando pela poli e pelas duas mudanças para o exterior. Tenho que agradecer
também minha família aqui na Europa, tia Marilda e tio Henk, Tanja, Carol, Dennis, Janwillen,
Mats e Louis pelas páscoas, natais, aniversários e por me ajudar em todos os momentos aqui.
Sem todos vocês eu nunca teria chegado aonde cheguei.

Je veux remercier aussi Amanda, pour m'avoir eu comme co-loc pendant quatre mois et
pour être toujours là quand je besoin. Et Bruno, Jero, Ale et Lucas pour tous les weekends, les
fêtes et les invitations que j'ai refusés car je devrais travailler. Ebru, merci pour m'avoir choisi
pour travailler dans votre projet et pour me donner la possibilité d'être dans MOB02. Mercedes,
Elsa, Franck, JB, Jessy, Jean-Louis et Céline, je suis très content d'avoir appris un peu sur le
domaine de chacun de vous, qui sont très éloignés de tout ce que j'ai étudié auparavant et de nos
discussions autour des cafés dans les matins et des bières dans les après-midis. Merci beaucoup
pour m'avoir reçu de manière si chaleureuse au sein de l'équipe. Le même est aussi vrai pour
le VEH08, DT et Guillaume, Mohamed, Nicolas, Laurène, Florent, Flavie, Floriane et Marie,
merci pour les cafés, les discussions et pour me soutenir pendant les trois années à VEDECOM.
Je remercie aussi le CSE, pour l'expérience quasi-syndicale et le D1 pour la camaraderie et les
afters.

Katherine, merci pour avoir facilité mon introduction à l'éthique, sujet avec lequel je n'ai
jamais eu de contact avant le début de la thèse; sans ton aide toute le développement de cette
thèse aura été beaucoup plus difficile. Merci pour les innombrables révisions de notre article
(vraiment innombrables) et pour ta patience et compréhension quand je faisais des remarques sur
les aspects fonctionnels dans tes raisonnements (c'est-à-dire tout le temps).

Et en dernier, et certainement le plus important, je remercie Raja. Au long des trois ans
de thèse j'ai écouté plusieurs histoires de thésards qu'ont eu des difficultés avec ces directeurs de
thèse. Je n'ai jamais compris ces histoires car pendant tout ma thèse tu m'as donné le support,
le temps et la confiance que j'avais besoin. Merci beaucoup pour avoir eu la patience avec moi
même quand je ne l'avais pas et pour le soutien indéfectible pendant ces derniers mois de thèse.
This research has been conducted as part of the AVEthics Project funded by the French National Agency
for Research, grant agreement number ANR-16-C22-008 and Horizon 2020 program AI4EU under grant
agreement 825619.
# Contents

<table><tr><td>Abstract</td><td>iii</td></tr><tr><td>Résumé</td><td>v</td></tr><tr><td>Remerciements</td><td>vii</td></tr><tr><td>List of Figures</td><td>xv</td></tr><tr><td>List of Tables</td><td>xviii</td></tr><tr><td>1 Introduction</td><td>1</td></tr><tr><td>1.1 Automated driving vehicles in society</td><td>1</td></tr><tr><td>1.1.1 A note on terminology</td><td>1</td></tr><tr><td>1.1.2 History</td><td>2</td></tr><tr><td>1.1.3 Current research status</td><td>9</td></tr><tr><td>1.2 Motivation of the thesis</td><td>12</td></tr><tr><td>1.3 Contributions of the thesis</td><td>14</td></tr><tr><td>1.4 Structure of the document</td><td>15</td></tr></table>
## 2 State of the Art 17

<table><tr><td>2.1</td><td>Decision Making</td><td>18</td></tr><tr><td>2.1.1</td><td>Related works</td><td>20</td></tr><tr><td>2.2</td><td>Ethical decision-making</td><td>25</td></tr><tr><td>2.2.1</td><td>Normative Ethics</td><td>25</td></tr><tr><td>2.2.2</td><td>Artificial moral agents</td><td>27</td></tr><tr><td>2.3</td><td>Behavior prediction</td><td>32</td></tr><tr><td>2.3.1</td><td>Vehicle prediction</td><td>33</td></tr><tr><td>2.3.2</td><td>Pedestrian prediction</td><td>38</td></tr><tr><td>2.4</td><td>Game theory</td><td>40</td></tr><tr><td>2.4.1</td><td>Related works</td><td>42</td></tr><tr><td>2.5</td><td>Conclusion</td><td>45</td></tr></table>

## 3 MDP for decision making 47

<table><tr><td>3.1</td><td>Theoretical background</td><td>47</td></tr><tr><td>3.1.1</td><td>AV's Architecture</td><td>48</td></tr><tr><td>3.1.2</td><td>Markov Decision Process</td><td>50</td></tr><tr><td>3.2</td><td>AV decision-making model</td><td>55</td></tr><tr><td>3.2.1</td><td>State and action sets</td><td>55</td></tr><tr><td>3.2.2</td><td>Transition function</td><td>57</td></tr><tr><td>3.2.3</td><td>Reward function</td><td>59</td></tr><tr><td>3.3</td><td>Results and discussion</td><td>66</td></tr></table>
<table><tr><td>3.3.1 Value iteration</td><td>66</td></tr><tr><td>3.3.2 Simulation</td><td>68</td></tr><tr><td>3.3.3 MDP policy results</td><td>70</td></tr><tr><td>3.4 Conclusion</td><td>74</td></tr><tr><td><b>4 Dilemma Deliberation</b></td><td><b>77</b></td></tr><tr><td>4.1 Dilemma situations</td><td>78</td></tr><tr><td>4.2 The definition of harm</td><td>79</td></tr><tr><td>4.2.1 Δv for collision</td><td>82</td></tr><tr><td>4.2.2 Vulnerability constant</td><td>83</td></tr><tr><td>4.3 Ethical deliberation process</td><td>86</td></tr><tr><td>4.3.1 Ethical Valence Theory</td><td>86</td></tr><tr><td>4.3.2 Ethical Optimization</td><td>90</td></tr><tr><td>4.3.3 Value iteration for dilemma scenarios</td><td>94</td></tr><tr><td>4.4 Results and discussion</td><td>98</td></tr><tr><td>4.4.1 Using EVT as ethical deliberation</td><td>98</td></tr><tr><td>4.4.2 Using the Ethical Optimization profiles to deliberate</td><td>102</td></tr><tr><td>4.5 Conclusion</td><td>104</td></tr><tr><td><b>5 Road User Intent Prediction</b></td><td><b>107</b></td></tr><tr><td>5.1 Broadening the scope</td><td>108</td></tr><tr><td>5.2 Intent estimation</td><td>109</td></tr><tr><td>5.2.1 Simulated Environment</td><td>109</td></tr></table>
<table><tr><td>5.2.2</td><td>Agent's decision model</td><td>112</td></tr><tr><td>5.2.3</td><td>Estimating other agents' intent</td><td>119</td></tr><tr><td>5.3</td><td>Incomplete game model</td><td>125</td></tr><tr><td>5.3.1</td><td>Nash equilibrium</td><td>125</td></tr><tr><td>5.3.2</td><td>Harsanyi's Bayesian game</td><td>126</td></tr><tr><td>5.3.3</td><td>Decision making procedure</td><td>129</td></tr><tr><td>5.4</td><td>Simulation results</td><td>133</td></tr><tr><td>5.4.1</td><td>Multi-agent simulation</td><td>134</td></tr><tr><td>5.5</td><td>Final remarks</td><td>138</td></tr><tr><td><b>6</b></td><td><b>Conclusion</b></td><td><b>141</b></td></tr><tr><td>6.1</td><td>Final remarks</td><td>141</td></tr><tr><td>6.2</td><td>Future research perspectives</td><td>144</td></tr><tr><td><b>A</b></td><td><b>Simulation set-up</b></td><td><b>147</b></td></tr><tr><td>A.1</td><td>Webots simulation structure</td><td>147</td></tr><tr><td>A.2</td><td>Controlling a car-like vehicle</td><td>149</td></tr><tr><td>A.3</td><td>Controlling the pedestrian</td><td>153</td></tr><tr><td>A.4</td><td>Necessary modifications</td><td>154</td></tr><tr><td></td><td><b>Bibliography</b></td><td><b>157</b></td></tr></table>
List of Figures

<table><tr><td>1.1</td><td>Automated vehicles envisioned in 1950 (source: (Kröger, 2016))</td><td>3</td></tr><tr><td>1.2</td><td>Interior of the vehicle used to test the machine vision component proposed in (Dickmanns and Zapp, 1987) (source: (Daimler, 2016))</td><td>5</td></tr><tr><td>1.3</td><td>Argo vehicle (source: (Parma, 1999))</td><td>6</td></tr><tr><td>1.4</td><td>Sandstorm vehicle in its final accident (source: Urmson, Anhalt, Clark, et al., 2004)</td><td>7</td></tr><tr><td>1.5</td><td>Stanley vehicle in 2005 DARPA Grand Challenge (source: (Thrun et al., 2006))</td><td>8</td></tr><tr><td>1.6</td><td>Boss vehicle in 2007 DARPA Urban Challenge (source: (Urmson, Anhalt, Bagnell, et al., 2008))</td><td>9</td></tr><tr><td>1.7</td><td>Definitions of levels of automation (source: (SAE, 2018))</td><td>10</td></tr><tr><td>2.1</td><td>Possible structures for the AV's decision-making</td><td>19</td></tr><tr><td>2.2</td><td>Hierarchy of possible significations for behavior</td><td>33</td></tr><tr><td>3.1</td><td>Three tiered (3T) architecture</td><td>49</td></tr><tr><td>3.2</td><td>AV architecture adopted</td><td>49</td></tr><tr><td>3.3</td><td>Simplified example of an MDP</td><td>52</td></tr><tr><td>3.4</td><td>AV's kinematic model</td><td>56</td></tr><tr><td>3.5</td><td>Example of state space discovery</td><td>57</td></tr></table>
<table><tr><td>3.6</td><td>State transition uncertainty for a<sub>0</sub> and a<sub>3</sub></td><td>58</td></tr><tr><td>3.7</td><td>Performance reward parameters</td><td>60</td></tr><tr><td>3.8</td><td>AV with all the proximity limits</td><td>61</td></tr><tr><td>3.9</td><td>Calculation of velocity projections</td><td>63</td></tr><tr><td>3.10</td><td>Workflow for s<sub>prox</sub> calculation</td><td>64</td></tr><tr><td>3.11</td><td>Calculating the separation line</td><td>65</td></tr><tr><td>3.12</td><td>Initial simulation setup (other road users' configuration is represented by (x, y, θ, v), not in scale)</td><td>69</td></tr><tr><td>3.13</td><td>Simulation environment</td><td>69</td></tr><tr><td>3.14</td><td>AV's behavior for x<sub>veh</sub> = 100, 80, 40m</td><td>71</td></tr><tr><td>3.15</td><td>AV's behavior for x<sub>veh</sub> = 80, 40m with 5 transitions</td><td>72</td></tr><tr><td>3.16</td><td>AV's velocity, direction and trajectory for x<sub>veh</sub> = 80m</td><td>72</td></tr><tr><td>3.17</td><td>AV's behavior for x<sub>veh</sub> = 100, 40m and θ<sub>ped</sub> = <sup>3π</sup>⁄<sub>4</sub> rad</td><td>74</td></tr><tr><td>3.18</td><td>Trajectory for x<sub>veh</sub>=40m, θ<sub>ped</sub>=<sup>3π</sup>⁄<sub>4</sub> rad for 5 transitions</td><td>74</td></tr><tr><td>4.1</td><td>Projection of future collision into previous states</td><td>97</td></tr><tr><td>4.2</td><td>Possible dilemma situation</td><td>99</td></tr><tr><td>4.3</td><td>Initial simulation setup (other road users' configuration is represented by (x, y, θ, v), not in scale)</td><td>99</td></tr><tr><td>4.4</td><td>Collision simulation for situation 1</td><td>100</td></tr><tr><td>4.5</td><td>Second simulation setup (other road users' configuration is represented by (x, y, θ, v), not in scale)</td><td>101</td></tr><tr><td>4.6</td><td>Collision simulation for situation 2</td><td>102</td></tr><tr><td>4.7</td><td>Trajectories for contractarian, utilitarian and egalitarian methods</td><td>103</td></tr></table>
<table><tr><td>5.1</td><td>New simulation environment</td><td>111</td></tr><tr><td>5.2</td><td>Road environment graph structure</td><td>115</td></tr><tr><td>5.3</td><td>Decision tree for vehicles</td><td>117</td></tr><tr><td>5.4</td><td>Decision tree for pedestrians</td><td>118</td></tr><tr><td>5.5</td><td>Illustration of the intersection interaction</td><td>135</td></tr><tr><td>5.6</td><td>Strategies used during situation 1</td><td>135</td></tr><tr><td>5.7</td><td>Strategies used during situation 2</td><td>136</td></tr><tr><td>5.8</td><td>Strategies used during situation 3</td><td>137</td></tr><tr><td>5.9</td><td>Modified vehicle decision for the no collision sub-tree</td><td>138</td></tr><tr><td>A.1</td><td>Main window of the simulator</td><td>148</td></tr><tr><td>A.2</td><td>Longitudinal control for the vehicle</td><td>150</td></tr><tr><td>A.3</td><td>Vehicle's acceleration sampling distribution</td><td>151</td></tr><tr><td>A.4</td><td>The pedestrian object</td><td>154</td></tr><tr><td>A.5</td><td>Pedestrian supervisor field</td><td>155</td></tr></table>
<figure><img src="image_3.png" /></figure>
# List of Tables

<table><tr><td>3.1</td><td>Parameters used in the state space discovery</td><td>58</td></tr><tr><td>3.2</td><td>MDP parameters used</td><td>66</td></tr><tr><td>3.3</td><td>Road users' physical properties</td><td>70</td></tr><tr><td>4.1</td><td>Δv threshold used for fatality collisions</td><td>80</td></tr><tr><td>4.2</td><td>Possible valence hierarchy</td><td>87</td></tr><tr><td>4.3</td><td>Possible moral profiles for an AV</td><td>87</td></tr><tr><td>4.4</td><td>Optimization procedure based on the moral profile chosen</td><td>88</td></tr><tr><td>4.5</td><td>Valence hierarchy</td><td>100</td></tr><tr><td>4.6</td><td>AV's harm for each possible collision for situation 1</td><td>101</td></tr><tr><td>4.7</td><td>Road users' harm for each possible collision for situation 1</td><td>101</td></tr><tr><td>4.8</td><td>AV's harm for each possible collision for situation 2</td><td>102</td></tr><tr><td>4.9</td><td>Road users' harm for each possible collision for situation 2</td><td>102</td></tr><tr><td>4.10</td><td>Expected harms and σ<sub>h<sub>exp</sub></sub> for contractarian policy</td><td>103</td></tr><tr><td>4.11</td><td>Expected harms and Σh<sub>exp</sub> for utilitarian policy</td><td>104</td></tr><tr><td>4.12</td><td>Expected harms and total cost for egalitarian policy</td><td>104</td></tr></table>
<table><tr><td>5.1</td><td>Example of reward table for a specific intent vector c</td><td>130</td></tr><tr><td>5.2</td><td>Rewards for player x</td><td>132</td></tr><tr><td>5.3</td><td>Intent probabilities</td><td>132</td></tr><tr><td>5.4</td><td>Conditional probabilities for c<sub>x</sub> = i<sub>1</sub></td><td>132</td></tr><tr><td>5.5</td><td>Conditional payoffs for c<sub>x</sub> = i<sub>1</sub></td><td>133</td></tr></table>
# Chapter 1

# Introduction

## Contents

<table><tr><td>1.1</td><td>Automated driving vehicles in society</td><td>1</td></tr><tr><td>1.1.1</td><td>A note on terminology</td><td>1</td></tr><tr><td>1.1.2</td><td>History</td><td>2</td></tr><tr><td>1.1.3</td><td>Current research status</td><td>9</td></tr><tr><td>1.2</td><td>Motivation of the thesis</td><td>12</td></tr><tr><td>1.3</td><td>Contributions of the thesis</td><td>14</td></tr><tr><td>1.4</td><td>Structure of the document</td><td>15</td></tr></table>

## 1.1 Automated driving vehicles in society

### 1.1.1 A note on terminology

The expression "automated driving vehicles" or "automated vehicles", will be preferably used in this manuscript instead of autonomous vehicles. The technical meaning of an "autonomous machine" is a machine that operates on its own, once programmed and started, without human intervention. This is also the meaning of "automated machine"(Dictionary, 1989). Only environment and task complexity lead researchers in robotics to use "autonomous robots" in place of "automated" because the necessary capacities in terms of perception, decision making, learning, etc., are more diverse, and the tasks are more complex. However, "autonomous" and "autonomy" in the general language, in philosophy and in law carry the meaning of deciding one's own goals and making one's own decisions - including moral decisions - independently from other agents' influence, (Christman, 2008): "...to govern itself, to be directed by considerations, desires,
conditions and characteristics that are not simply imposed externally upon one but are part of what can somehow be considered one's authentic self". The decision-making algorithms proposed and discussed in this thesis account for usual vehicle behavior control but also for decisions having ethical stakes. This invalidates the use of autonomy as descriptive of such vehicles, since machines do not have morality on their own. Automated driving vehicles accomplish computations as programmed in their algorithms, designed by humans - including through machine learning methods - and are constrained by what these algorithms compute. It's therefore important to avoid any misleading terminology and to use the proper terms.

1.1.2 History

To explain from where the decision-making algorithms that govern automated vehicles (AV) originated, a short history about the development of artificial intelligence (AI) in general, with focus on mobile robotics, will be given, together with the past and current developments for automated vehicles. A picture about the current deployment of automated driving technologies on roads will also be presented, with the most popular use cases and main actors in the domain. This overview will situate the motivations and contributions of this thesis and help to put the research discussed in the next chapters into context.

The history of automated vehicles (AVs) is one that starts long before this century, and in fact even before the well known DARPA challenges (2005 Grand challenge and 2007 Urban challenge), that brought AVs into the public spotlight as a real and imminent innovation. The first interaction between the wide public and cars that can drive themselves was in the New York's world fair in 1939. At that time, GM imagined a trench-like system build into highways to keep vehicles separated. Then the driver could enable the automatic driving system and relax. All such vehicles based their autonomy in mechanical systems (Kröger, 2016) since any kind of computing machine technology was still in its beginnings.

Only in 1960's, with the development of computational systems, semiconductors and the establishment of artificial intelligence (AI), researchers start working towards reproducing some sort of intelligence embedded in a vehicle. By introspection, what makes an agent<fnref n="1" /> become an intelligent agent (which hypothetically receives some sort of authorization from society to function with less or even without human supervision) is the possession of a model for the world, which can be used to draw conclusion about how a task can be accomplished using computational reasoning, can be enriched with additional information and allow the agent to execute tasks necessary to complete a goal (McCarthy and Hayes, 1969). However the exigence towards the performance level of said intelligent agent changed through the years. The first definition of artificial intelligence for an inanimate agent, the *Turing Test*, verify if some sort of machine is capable of producing an output indistinguishable from one originated from a human being

<footnote n="1">¹Which are considered by the literal provenance of the word, from the latin *agere*, or to do, disregarding its
philosophical meaning.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 1.1 – Automated vehicles envisioned in 1950 (source: (Kröger, 2016))</figcaption></figure>

(Turing, 1950). At this point the idea of an intelligent agent was connected to an equivalence between human and machine, but a more accurate definition is perhaps the one given by (Bellman, 1978): "the automation of activities associated with human thinking".

With each advancement in the field, the equivalence was replaced by optimality, defining an intelligent agent as a rational<fnref n="2" /> machine capable of executing the best outcome (or expected best outcome under uncertainty) at each time given a mission (Russell and Norvig, 2009). The same "rationality" is used in (Winston, 1992) through the definition of AI as "the computations that make it possible to perceive, understand and act". This formulation of intelligence, born from the introspection of the human mind (McCarthy and Hayes, 1969), is the first robotic paradigm used to approach the implementation into a machine (Murphy, 2000).

Such concept of rationality, which is connected with the robot's capacity to reason and to construct a world model is based on a knowledge representation consisting of all the sensorial data and a priori information about the environment (Murphy, 2000). Planning, state spaces and transitions were used to construct this world model in the STRIPS planning system for the robot Shakey (Munson, 1971; Fikes and Nilsson, 1971), even if at the time the theoretical tool used to implement the planning was predicate logic, which does not offer the capacity to deal with the uncertainties that may exist in an open and dynamic world. But when one considers the entire concept of intelligence, only planning is not enough to reproduce, for example, the behaviors that

<footnote n="2">²Rational is used in (Russell and Norvig, 2009) as a property of someone or something that acts "doing the right thing". It is not clear if this model of rationality accounts a moral component into the evaluation of what is right. Therefore for this specific case, "the right thing" means quantitatively the best outcome without any moral consideration.</footnote>
can be observed in animals given its complexity and the need for real-time execution (Brooks, 1986).

Intelligence as only defined by reason, and therefore with an artificial implementation based on a top-down approach like the hierarchical paradigm, practically limits a robot's capabilities to some aspects of what one would expect from an intelligent agent (Brooks, 1991). For example, the necessity for a real-time capacity to respond to stimulus can be in opposition to the execution of a planning routine at every iteration (and it certainly was in the 1960s, when computational capacity was much lower). It is from the search of a more "animal-like" responses that the reactive paradigm came about. The seminal paper of (Brooks, 1986) defines the main characteristics of this bottom-up approach (using a subsumption architecture): many distributed components, each one emulating a kind of behavior, interact with each other and with other components in different layers of increasing complex behavior. No planning is involved in this approach, thus the agents do not have a model of the environment or any type of memory, instead they react to what is perceived from the environment.

However, given the desire to implement an intelligent agent that has at least an equivalent capacity to a human (if not more) to execute some specific task, the reactive paradigm also falls short on finding a viable implementation (even though it produced many successful demonstrators of animal behaviors, as (Brooks, 1989) or even other models of reactive behavior, as (Firby, 1989)). Having no capacity to plan is not realistically possible, since some kind of high-level planning is necessary to execute long-term missions, map the environment and check the robot's performance (Murphy, 2000). So because of this outcome the planning step was added on top of a deliberative process proposed by the reactive approach, in a hybrid configuration. The reactive approach was a functional way to model the low-level real-time behavior for an agent but some knowledge representation of the world is always necessary to plan, as it is shown in (Payton, 1986), (Arkin, 1990), (Giralt et al., 1990) and (Noreils and Chatila, 1995).

From the 1990s forward, two other modules started to appear and compose robotics systems with perception, deliberation and action: communicate and learn (and given the dif-fuse nature of the behavioral approach, these two functions where implemented by specific components). The former is an essential source of information about other agents in the same environment, allowing a more predictable interaction to optimize the main goal of both. Learn-ing, and more specifically reinforcement learning presented itself as an alternative to the fixed behaviors proposed by the reactive paradigm while using planning to find the best actions to be executed (Sutton, 1990). Perception will also adopt learning for machine vision (Brauckmann et al., 1994).

Throughout the development of the techniques, concepts and demonstrators of AI in robotics, AV research (in this context AV refers to the domain of mobile robotics concerned into producing vehicles for transportation) also took part in such progress from the 1980s. Given the highly dynamical environment they should be able to operate, they touch the main problem of hierarchical architectures, the need for a closed world assumptions, but an reactive approach is
also not completely adapted *a priori* to the problem, since planning and representation is still essential. Thus, since the beginning an hybrid approach was taken to build an AV architecture. Some of the main demonstrators of self-driving AVs will be discussed below<fnref n="3" />.

One of the first implementations of camera-based perception for AVs was done by (Tsugawa et al., 1979). Two cameras were used in a stereo mount to detect and avoid objects, with a maximum cruise velocity of 30km/h on private tracks. In 1987 (Dickmanns and Zapp, 1987) successfully tested an AV capable of lateral and longitudinal guidance by computer vision in a public highway for 20km with a maximal velocity of 96km/h. Such implementation extracted the road boundary markings from images produced by a CCD TV-camera to determine an estimation of the road geometry (curvature). Then this measure was updated at each iteration with the vehicle state using a Kalman filter and used to calculate the longitudinal and lateral control.

The progress of self-driving continued from 1987 to 1995 due to the Prometheus project, an European project that assembled car manufactures and research organizations to improve road traffic safety from a vehicle perspective and from an infrastructure perspective. At the same time the machine vision applied to AVs also was focus of research in the US and in Japan (Dickmanns, 2002). In (Dickmanns, Behringer, et al., 1994) a vision system composed of two platforms of two cameras with different focal points was used to interpret the situation ahead and behind the vehicle, with traffic sign detection, moving humans identification, obstacles and road lanes finding. In the same project, (Brauckmann et al., 1994) proposed a vision system of sixteen cameras, capable of detecting road vehicles all around, with a neural network capable of detecting the rear of vehicles, a lateral blind spot surveillance and a short range visual object detection to automate stop and go situations.

<figure><img src="image_5.png" /><figcaption>Figure 1.2 – Interior of the vehicle used to test the machine vision component proposed in (Dickmanns and Zapp, 1987) (source: (Daimler, 2016))</figcaption></figure>

<footnote n="3">³A more exhaustive list of projects can be found in (Claussmann, 2019)</footnote>
All of the developments cited were finally concentrated in the VITA II demonstrator (Ulmer, 1994), which had the following capacities: lane, distance and speed keeping, lane change, overtaking and collision avoidance. For the collision avoidance, two subsystems co-exist in the vehicle: one that calculate controls based in a potential field approach and another that uses a state transition model to represent all possible situations that may arise in traffic, invoking vehicle's maneuvers when necessary. Another European project, ARGO, also demonstrated a AV prototype capable to drive long distances without a driver only with passive sensors (two cameras and a speedometer) (Broggi, Bertozzi, et al., 1999). The road was reconstructed using monocular images while detection and tracking of other vehicles was done with pattern matching. For the vehicle control, a variable gain proportional controller with a non-holonomic bicycle model and a quintic polynomial approximation produced the final trajectory. This demonstrator drove 2000km in Italian highway network (not continuously). Problems related to illumination sensibility in image acquisition and some control instability in high speeds were observed along during tests.

<figure><img src="image_6.png" /><figcaption>Figure 1.3 – Argo vehicle (source: (Parma, 1999))</figcaption></figure>

Then it came the DARPA (Defense Advanced Research Projects Agency) challenges. The race consisted in completing a 143 miles (approx. 230 km) route in the Mojave desert. No team were able to complete the very first challenge in 2004, with the Red team from Carnegie Mellon University traveling the farthest. The course route were given only 3 hours before the start of the race, so the trajectory could not be calculated beforehand and since it is an off-road challenge (thus no traffic infrastructure were available) the number of sensors needed to assure high speed automated driving increased in number and complexity in comparison with the previous attempts in highway environments. An effort from Red team was made to build a detailed map from the entire region were the race could take place, with possible routes, geographic characteristics, elevation and satellite images before the race. All this information was used, with the course waypoints, to calculate a pre-established path, which should be tracked by the vehicle during execution based on sensor readings (GPS for position and LIDAR and stereo vision for terrain perception). Many incidents were reported, some related to the inability to modified the pre-planned trajectory to avoid obstacles, but the one that provoked the final accident was due to an
excessive sharpness in the pre-planned trajectory, tendency to cut corners from the pure pursuit control and measurement errors in the GPS readings (Urmson, Anhalt, Clark, et al., 2004).

<figure><img src="image_7.png" /><figcaption>Figure 1.4 – Sandstorm vehicle in its final accident (source: Urmson, Anhalt, Clark, et al., 2004)</figcaption></figure>

Since no team was able to finish the event, it was repeated in 2005. Five teams successfully finished the course this time, with the Stanford team as first. The winner vehicle also possessed a rich array of sensors as previously, from lasers, radars and cameras for environmental detection to IMU, GPS and wheel encoders for position measurements. The Red team vehicle already implemented an architecture close to the hierarchical paradigm, but the Stanford's vehicle went beyond and based its software in the three-layer architecture (will be detailed in the next chapter). All position estimation measures were calculated using an UKF with a modified estimation for GPS outages situations, where accurate vehicle modeling is necessary to maintain pose errors contained. No environment *a priori* map was used, with the vehicle executing the obstacle detection online and with laser measurements. Such detection is based on a probabilistic grid approach with parameters tuned by a discriminative machine learning algorithm. For road finding, since the laser range was insufficient given the speed necessary to complete the challenge, all readings of safe terrain from laser origin were projected into the perceived pixels of the camera image. Then, using a mixture of Gaussians the image pixels were classified and the drivable surface was determined. The base trajectory was pre-calculated and modified online to avoid obstacles while staying inside the course limits (Thrun et al., 2006).

As one can see, the complexity of the perception systems increased substantially since the days of (Dickmanns and Zapp, 1987; Brooks, 1986) in terms of price and capacity. The other main advancement that allowed such gain of performance is the availability of more capable computers. Most of the machine vision processing done in (Dickmanns and Zapp, 1987) was done in specific hardware; in (Thrun et al., 2006) the embedded processing unit had 6 processors. Advances in machine learning were also capitalized in machine vision for the road and object detection (although neural networks were already present in (Dickmanns, Behringer, et al., 1994)).

In 2007 the Urban Challenge took place, which consisted in a course of 97km through
<figure><img src="image_8.png" /><figcaption>Figure 1.5 – Stanley vehicle in 2005 DARPA Grand Challenge (source: (Thrun et al., 2006))</figcaption></figure>

an urban environment. This time it was the Carnegie Mellon University team that won the first
place. Their vehicle, called Boss, used a similar architecture from Stanley but with a focus on
active sensing. Given the nature of the challenge two different navigation modules existed: one
to generate a trajectory for road environments and another for non-structured zones (parking
zones). In roads multiple trajectories were generated from the middle of the current lane, allowing
the vehicle to choose the best lane to avoid static or dynamic obstacles. Outside roads, where
there was no nominal orientation, the vehicle model was used to generate offline a set of possible
maneuvers available for each state (in this case the state is composed by (x, y, θ, v)<fnref n="4" /> ). Then this
space was searched online to form a trajectory, from the goal pose to the current position. Moving
obstacles were tracked using or a fixed-body hypothesis or a point-based estimation and then
classified as moving or not, while static objects first were identified in a instantaneous map to
then be filtered out or added into the temporally map (Urmson, Anhalt, Bagnell, et al., 2008).

But the real differential with the previous challenge was the mission planning. The
environment now had intersections, that needed to be managed in addition to the structured
and unstructured environment. Thus three behaviors were available: lane driving, intersection
handling and goal selection (for unstructured road). Each one of these behaviors had functional
components that could be used if necessary, in a reactive structure (Urmson, Anhalt, Bagnell,
et al., 2008).

From this point on there have been some initiatives from institutional projects, but the
private initiative took hold from the domain and started to develop real applications with the
technology displayed until this point (Anderson, Kalra, et al., 2016). Research beyond the 2010s
started to focus on the study of V2X communications combined with automated driving, as shown
by The Grand Cooperative Driving Challenge (Englund et al., 2016), an event in the molds of
the DARPA Challenge about wireless communication usage in traffic. Two other examples are
Broggi, Cerri, et al., 2015, a test in open street without driver in Parma, and Ziegler et al., 2014,
an automated driving test in the same route where the first cross-country automobile journey took
place, between Mannheim and Pforzhein in 1888.

<footnote n="4">⁴position in 2D, direction and velocity</footnote>
<figure><img src="image_9.png" /><figcaption>Figure 1.6 – Boss vehicle in 2007 DARPA Urban Challenge (source: (Urmson, Anhalt, Bagnell, et al., 2008))</figcaption></figure>

1.1.3 Current research status

Many applications for limited domain of operation are already present in the real world today. The most popular system deployed are small shuttles operating in closed environments and with limited velocity. For example, university campuses are very interesting environments to test such technology and also to inquire the users about the service's quality and its social acceptability (Berrada et al., 2020; Nordhoff et al., 2021). Even if from a technical standpoint they do not deliver what is expected – fully automated driving; Nordhoff et al., 2021 and Mouratidis and Cobeña Serrano, 2021 had maximal velocity of 18*km/h* with automatic longitudinal control but any obstacle avoidance needed to be executed by the operator and Berrada et al., 2020 had a maximal velocity of 30*km/h* – their deployment in specific domains is useful to start studying the societal effects that the automated driving can have in our society, which can vary from an acceleration of urban sprawl (Soteropoulos et al., 2019) to an improvement of public transport coverage in urban zones with few or infrequent buses (Mouratidis and Cobeña Serrano, 2021).

Usual car manufacturers already adopted level 1 or level 2 autonomy solutions. According to the definition given by (SAE, 2018), level 1 automation is characterized by longitudinal or lateral automatic control and level 2 both directions are controlled by the vehicle, but always under de strict driver supervision. The latter is the frontier between having the driver in the loop<sup>5</sup>, since from level 3 it is the machine that takes over – although in case of accidents or any type of failure the driver must be ready to take over. For example, a very common system nowadays

<footnote n="5">⁵To be more precise, the difference between both levels is that level 2 assumes that no object or event detection, recognition, classification, response preparation and response execution will be done by the vehicle, while level 3 internalize such tasks while maintaining the option to cede control for the driver (SAE, 2018)</footnote>
is the adaptive cruise control (ACC), which controls the velocity of a vehicle when engaged, always checking ahead for obstacles. Another popular feature is the automatic emergency braking (AEB), a system capable of detecting obstacles in front of the vehicle and break under danger of collision. Its efficacy to reduce rear-end vehicle to vehicle (V2V) collision by was shown in Fildes et al., 2015 for low speed (30km/h to 50km/h), but these systems still have difficulty to prevent collisions with pedestrians in straight roads and in left and right turns (AAA, 2019).

<figure><img src="image_10.png" /><figcaption>Figure 1.7 – Definitions of levels of automation (source: (SAE, 2018))</figcaption></figure>

Both aforementioned systems are classified as level 1. A level 2 system could be composed for example by an ACC and a lane keeping system functioning at the same time, which is a combination done by some brands (Toyota, Tesla and Mercedes, for example). No examples of complete level 3 automation for open road usage<fnref n="6" /> exist in commercial cars today due to the lack of regulatory legislation up to 2020, since level 3, often called conditional autonomy, is the first stage of automated driving, thus, a priori, manufacturers could be liable for accidents during execution of the given system, even in misuse cases.

<footnote n="6">⁶The open road usage was added to exclude parking assistants from the comparison, given that they are classified as level 4 but they have a very specific raison d'être.</footnote>
From January 2021 forward, 60 countries (including the EU, Japan and Canada) adopted a UN resolution that sets up the regulation of automated lane keeping systems (ALKS)<fnref n="7" />, limited to 60km/h and roads with separation between opposite directions and without pedestrians or cyclists. The regulation considers the system as primary driver and sets safety requirements for emergency maneuvers, transition demands and minimal risk maneuvers. With level 3 capabilities also comes two mandatory hardware components: a driver availability recognition system, which detects the driver’s presence and readiness to take back control, and a data storage system, sort of a black box for the automated system (UNECE, 2020). Thus, level 3 capable vehicles should be expected in the near future.

Differently from the established car manufacturers, that avoid taking considerable risks, some companies are working in level 4 urban AVs. Two of them already have automated demonstrators working in the streets: Waymo and Cruise. The first, a spin-off from Google, is the company with the most experience and mileage concerning simulation and real kilometers driven in automated mode. It even created its own LIDAR sensor, which is used to give the vehicle a 360° vision of the environment. Cruise, a start-up that has as investors GM, Honda and Microsoft, has a automated taxi service in central San Francisco without backup driver since October 2020, after years of tests in the suburbs. Zoox, bought by Amazon in 2020, does not have vehicles retrofitted with sensors to be autonomous, it has taken the approach to design a vehicle (in this case a shuttle) from the ground up to be autonomous, with 4-wheel steering and bidirectional driving.

The case of Tesla for automated driving is more complex. Tesla's Autopilot has been present in the streets since 2014 and it has generated controversy given its array of accidents and problems, since its first accident in 2016 (Yadron and Tynan, 2016), when a Tesla drove under a perpendicular lorry after failing to distinguish the latter from the bright sky (Tesla, 2016), until another one in 2018 when a Model X hit a previously damaged median barrier at approximately 114km/h (Chokshi, 2020). In this last accident the National Transportation Safety Board, the federal agency that investigated the incident pointed that the accident was caused by the driver who has not paying attention to the road and that in 19 minutes of automated driving the driver kept its hands on the wheel for a total of 34 seconds (Chokshi, 2020).

In 2017, as the result of an investigation of the 2016 accident (BBC, 2017), the same agency had already issued two specific recommendations, for Tesla and all other manufacturers: to limit the use of automated systems to the conditions accounted during design and to make sure driver keep the focus on the road and their hands on the wheel (Chokshi, 2020). More recently it was announced that US federal regulators investigate 23 accidents involving Tesla's vehicles, potentially using AutoPilot (it is not clear yet if the system was enable and functioning at the moment of accident in all accounts). In these accidents there are instances when the Tesla crashed into a stopped police vehicle without decreasing its velocity, another rear-ended a police vehicle and one, which happened in February 2021, very similar to the 2016 lorry accident (Boudette, 2021).

<footnote n="7">⁷Despite the name, longitudinal control is also executed by the system</footnote>
Tesla's new automated lane change system is the main focus of attention now. Since 2019 the Autopilot function can deliberate if a lane change is possible and necessary, and depending on the settings used, it can be executed or ask the driver permission to execute. Up until 2019 the driver itself had to initiate the lane change. According to Barry, 2019, the functionality can cut off cars in a way that drivers do not usually do. Other problems are mentioned, like the difficulty to interact with high-speed vehicles coming from the rear during lane change and problems to merge into traffic. Thus, one of the characteristics that an AV should have (or at least some vehicle with advanced ADAS), the predictability of its actions by other drivers, sometimes is not present. By hindsight, maybe the system executes such maneuvers because it has a greater analytical capacity than a common driver, but there is no way to know since the inner works of the system are secret.

This privacy problem is also present in all other automated systems from other manufacturers, throwing all the responsibility to policymakers, that will need to establish the homologation process for automated driving systems. This secrecy also prevents the inspection or the investigation of these systems by the scientific community (or the public in general) at large. Despite an expected re-calibration on the hopes and dreams about deploying fully functional AVs in the roads at the beginning of this decade (Boudette, 2019), the technological development in the private domain has already solidified and it is advancing towards a real prototype.

## 1.2 Motivation of the thesis

Simply put, the biggest selling point for the deployment of automated vehicles a possible decrease in the number of accidents, given that that approximately 93.1% of them in the US are due to human error (NHTSA, 2008). Such decrease is taken as a condition for the licensing of automated systems according to guidelines from regulators (Luetge, 2017; Bonnefon et al., 2020). Automated driving is estimated to represent a significant decrease in the number of deaths in road accidents per year, which would be a gain for society as a whole, even if the gains of such revolution would be felt in its majority in high-income countries, where the average rate of death per 100.000 is 8.3 in comparison with 27.5 for low-income countries<fnref n="8" /> (WHO, 2018). There are other reasons to study and push for AVs in the streets, for example to reduce traffic and congestion (Narayanan et al., 2020), improve transportation efficiency (and therefore reduce pollution) (Wadud et al., 2016), increase accessibility to the elderly and the disable (Fagnant and Kockelman, 2015), but spare lives is the most urgent issue.

It is undeniable that an automated system can, *a priori*, have a better analytical capacity than a human. This is even more evident if one considers afflictions that only affect humans, for example alcoholic intoxication, lack of attention, disregard towards signalization or the traffic code, drowsiness and many others. So, on the account of accidents involving these situations an AV can make a difference. However, the interaction between AV and other drivers can itself

<footnote n="8">⁸It is also important to mention that road traffic injuries are the eight leading cause of death for all age groups and the leading cause for the range of 5-29 years according to WHO, 2018.</footnote>
introduce new sources of accidents. This interaction between machine and human is even more
critical considering that it is expected from the AV the capacity to solve situations that would
result in an accident, thus possibly producing a non-obvious behavior for the other road users.
The AV's ability to account for these interactions and predict the reaction of all other road users
is important and, by nature, these reactions are uncertain.

The AV itself also has some shortcomings. For example, every perception source has an inherent noise, maximal range and other specificities related to each type of sensor (for example GPS do not work well in dense urban areas and LIDAR measurements are disturbed by rain), there is a limited time for reasoning and hardware failures are always possible. But even if one assume that all the AV system and the infrastructure function at an ideal performance level, the unpredictability about the other road users remain (considering situations were there is an human component in the environment). Thus, even in an ideal world some uncertainty always exists and, because of that, the possibility of an accident happening cannot be disregarded (Goodall, 2014). According to Teoh and Kidd, 2017, in 2016, Google's AV registered 3 reportable incidents in tests at Mountain View, California. The comparison with real drivers shows that the AV is safer than a normal driver, but without statistical certainty (95% confidence interval). Looking the numbers of disengagement initiated by the backup driver, out of 13, 10 would have caused a contact. A more detailed study is done in Blanco et al., 2016, which also does not have enough data to reach a conclusion but observes the same tendency, this time adjusted by US national statistics<fnref n="9" />.

It is clear from this point that a probabilistic approach needs to be adopted at the planning
component of the AV, to account the behavior of other road users and all the related uncertainty.
But if an ethical dilemma situation presents itself in the planning, how the AV should deliberate?
Firstly, an ethical dilemma is defined as a situation where harm will be inflicted by the AV toward
other road users for every possible action executed (Evans et al., 2020). If the planning for some
non-dilemma situation predicts a possible collision (i.e., there is a risk of harm for some of
the users), the simple imperative that the AV must not cause accidents can be used to avoid
completely this situation, and in this normal situation other parameters would be used to drive
the decision, as for example the AV's performance given the chosen action, proximity to other
road users, etc. But this imperative is invalid in a dilemma situation, and the other ones are not
pertinent, since deliberation about the harm distribution must be the priority, which is dependent
on how one thinks it is pertinent, fair, moral to distribute the risk of harm between each one in the
environment. Such deliberation is necessarily an ethical one (Evans et al., 2020).

Considering the predicament mentioned, this is the main motivation of the thesis: **to inves-**
**tigate how an automated vehicle should deliberate under normal situation and in dilemma**
**situations.** From a defined decision process for normal situations an additional component must
be integrated, to enable the AV to reproduce some sort of moral deliberation, given a pre-defined
ethical theory, to determine how the distribution of risk needs to be done if the planned situation

<footnote n="9">⁹Another interesting problem with a direct comparison of accidents is that all accidents are reported by AVs, which is not true for human drivers, creating a bias against the AV. Even so, the final conclusion in Blanco et al., 2016 says that only for the least severe crashes the AV is safer at a statistically significant level.</footnote>
manifest itself in the real world.

The reasoning to argue that ethics is necessary in the decision-making component of an AV presented above might be classified as a top-down justification, since it starts discussing the general capabilities of an AV to them point where the need for ethical reasoning arises. The inverse direction could also be used to justify the same need: assuming that during the life-cycle of an AV and that because of the highly dynamic environment characterized by urban areas, at least once it might face a dilemma situation, maybe only in planning, but if it is predicted it might materialize itself. In this case, how it should deliberate? Should it choose at random, or should it beforehand have some capacity to choose one action over the other (Lin, 2016)? This consideration also assumes that it is improbable that an AV could be treated as a perfect implicit ethical machine, i.e. a system capable to avoid any type of ethical issues at all times (Moor, 2006).

## 1.3 Contributions of the thesis

The following contributions were implemented and tested through a multi-agent simulation of an environment containing vehicles, pedestrians and AV.

* **Definition of a harm measure for collisions:** Defined by the difference in velocity between the two road users involved in the collision and scaled using a constant that represents the inherent fragility of a road user.

* **Ethical deliberation according to different moral theories:** Rawlsian contractualism, utilitarianism and egalitarianism were used to inspire three different optimization criteria for the risk of harm in an accident.

* **Reward function combined with ethical consideration:** An ethical component assumes the role as reward function when necessary, projecting future dilemma situations into the present to actively avoid it.

* **Model of interaction between road users using an probabilistic game theory approach:** Accommodation of other road users probable behavior into the AV's decision-making structure using a game with incomplete information to model expected reward given each possible action for the AV.

Results from the ideas and propositions during this thesis are presented in the following publications:
## Peer-Reviewed Journals

**Title:** Ethical Decision Making In Autonomous Vehicles: The AVEthics Project

**Authors:** Katherine Evans, Nelson de Moura, Stéphane Chauvier, Raja Chatila & Ebru Dogan

**Journal:** Science and Engineering Ethics, Springer

**Volume:** 26, **Pages:** 3285-3312, **Year:** 2020, **Reference:** Evans et al., 2020

## Peer-Reviewed Conferences

**Title:** Ethical decision making for autonomous vehicles

**Authors:** Nelson de Moura, Raja Chatila, Katherine Evans, Stéphane Chauvier & Ebru Dogan

**Conference:** IEEE Intelligent Vehicles Symposium

**Place:** Las Vegas, US (virtual), **Date:** October 2020, **Reference:** de Moura et al., 2020

# 1.4 Structure of the document

**Chapter 2** presents the state of the art in the most relevant domains addressed in this thesis, decision-making, ethical decision-making, behavior prediction and game theory. Comments about the structure and types of methods inside each domain is followed by the mention of a set of representative publications about the methods discussed.

**Chapter 3** proposes the decision-making algorithm to process normal situations. Before diving into the implementation details, a discussion about the architecture used and the theoretical definition of a Markov decision process are done. Next, the details about the implementation of a MDP are given, which is followed by the policy determination procedure and the results obtained in simulation.

**Chapter 4** proposes two possible deliberation procedures to determine an action to be executed in a dilemma situation. The chapter starts with the definition of what is a dilemma situation, to then propose a severity measure of an accident. The two deliberation methods are treated next and to finish the chapter, the simulation results are discussed.

**Chapter 5**'s main goal is to relax the assumption about the invariability of the other road users behaviors during the execution of the AV's policy. Starting from the determination of the errors that might drive the AV into a dilemma situation, the a new use-case and the definition of the deterministic decision process for other agents in the simulation is addressed. The AV's estimation of the other road users intent and the game theoretic model are proposed, in a first moment only considering pure strategies and then modifying the proposed framework to account for mixed strategies.

**Chapter 6** closes this document with the final remarks and future research perspectives concerning this thesis thematic.
**Appendix A** includes a presentation of the simulation environment and set-up, based on Webots, to which we have made some adaptations.
# Chapter 2

# State of the Art

## Contents

<table><tr><td>2.1</td><td>Decision Making</td><td>18</td></tr><tr><td>2.1.1</td><td>Related works</td><td>20</td></tr><tr><td>2.2</td><td>Ethical decision-making</td><td>25</td></tr><tr><td>2.2.1</td><td>Normative Ethics</td><td>25</td></tr><tr><td>2.2.2</td><td>Artificial moral agents</td><td>27</td></tr><tr><td>2.3</td><td>Behavior prediction</td><td>32</td></tr><tr><td>2.3.1</td><td>Vehicle prediction</td><td>33</td></tr><tr><td>2.3.2</td><td>Pedestrian prediction</td><td>38</td></tr><tr><td>2.4</td><td>Game theory</td><td>40</td></tr><tr><td>2.4.1</td><td>Related works</td><td>42</td></tr><tr><td>2.5</td><td>Conclusion</td><td>45</td></tr></table>

To propose a decision-making system capable to deal with the situations mentioned in Chapter 1 it is necessary to consider two main subjects. The first is the algorithms that reason about the world around the AV and allow it to make decisions in place of the driver during the mission. They usually consider criteria about the consequences of actions towards achieving a goal as the only (or the most important) measure to find the best action. Three domains from this first subject are explored in this thesis: how to predict the behavior of other agents, how to model interaction between agents and how to account for uncertainty.

The second subject concerns the fusion between ethical considerations and normal decision making. The resulting methods from this domain are grouped on what is called ethical decision-making methods; their imperative is to determine the best action according to some ethical theory of what is right, good or fair. A discussion about the scope of ethics needed to implement these methods and the one used in the algorithms that are proposed in subsequent
chapters will be followed by a report of the past and current state of the art in the field of artificial moral agents.

Two other domains are of importance, this time for the questions addressed in chapter 5. To relax the assumption that no interaction between road users happens during the AV's mission it is necessary to, first estimate the intention of each road user and then account for possible interactions. Therefore, a discussion about behavior prediction is due, as is one concerning game theory, the most appropriate tool to model interaction between agents that present some form of rationality.

## 2.1 Decision Making

As the title clearly states a decision making system uses its input, that may be sensor information, a priori data or any sort of exploitable data, with its decision structure to deliberate on what the automated<fnref n="1" /> system (AS) should do, given a mission or an objective. Considering the hierarchical paradigm, decision-making is the embodiment of the plan step (for mobile vehicles motion planning<fnref n="2" /> is also a part of the plan step, if it is not handle by the decision-making itself), and for the reactive paradigm the decision is indirectly implemented by the sum of all components in all layers.

There is a wide range of methods for decision making in many tasks and situations. Autonomous systems cover a wide range of applications, from the automated vehicles (aerial, terrestrial or aquatic) to robotic manipulators, but the discussion here will be centered in the decision making methods for automated vehicles. In the AV domain, the organization established by the hierarchical paradigm is often used to define the AV's architecture (more details on this point will be given in chapter 3), with the sense-plan-act layers. These three layers can also be divided in sub-components, which is typically the case of the planning layer: its task can be separated in strategic, tactic and operation procedures. Such classification is used in (González et al., 2016) and (Sharma et al., 2021) and in most of the AV published research, although with different names. Decision-making methods concerns exactly the planning layer, with the tactical component (path planner in the former and behavioral planner in the latter) being of special interest since it is where the global path is adapted to the environment constraints and the behavior of other road users.

The realization of this architecture can be done in different ways. One notable difference

<footnote n="1">¹The same reasoning as for the discussion between automated and autonomous vehicles is valid here; the term more commonly known is autonomous systems, but automated systems will be used.</footnote>

<footnote n="2">²There might be some confusion related to the frontier between motion planning and decision-making. It will be considered that decision-making is more general than motion planning and thus can refer to decisions about other variables than the trajectory to be executed, which the output of each motion planning method necessarily refers to; for example, considering the AV context, the decision-making can reason about the necessity to adopt some general profile of defensive driving in certain situations, which does not have a direct relation with the trajectory to be followed.</footnote>
concerns the flow of information inside an AV. According to (Schwarting et al., 2018), these organizations can be resumed to three representations, shown in figure 2.1 (they are fairly similar to the usual architecture for an AV, as it will be explored in section 3.1). The first and the second approaches have the perception and control components well defined, having as difference the separation or not from the motion planning and the higher decision-making process. Such difference depends upon the characteristics of the model, for example, if some internal motivation or long-term strategy is calculated as a separate process, then this result necessarily becomes the input for the motion planning, that may deal not only with the geometric constraints of the trajectory but also with the interaction with other road users. On the other hand, methods as Markov Decision Process (MDP) can fuse both procedures in one only component, even if some internal variable needs to be calculated as to guide the trajectory determination.

<figure><img src="image_11.png" /><figcaption>Figure 2.1 – Possible structures for the AV’s decision-making</figcaption></figure>

The third option has recently being in the spotlight due to the advancements delivered by deep-learning methods, which enables the learning procedure to be executed directly from the input data mass without any type of separation, rule abstraction or clear hierarchy. However, the first application of end-to-end driving was proposed years before, by (Pomerleau, 1988), which used a neural network to teach a vehicle how to keep driving in the same lane. Given the critical characteristic of automated driving, this implementation philosophy is somewhat contentious, since these systems function as black-boxes and that they are approximate methods without a measure of limits to which the output values can assume.

Considering the frameworks of possible methods and proposed organization for the flow of information, some examples of decision-making application into for AVs will be discussed next. A preference will be given for MDP-inspired decision-making algorithms, since it directly relates to all the methods proposed here, and, together with end-to-end learning based on neural networks, constitutes the two most used approaches for AVs decision-making implementation.
2.1.1 Related works

Given the importance of the uncertainties involved in automated driving, finite state
machines are not commonly used to embody the decision-making of an AV. Markov decision
processes are much more adapted to this task, which is observed by the number of publications
that propose such methods. Aiming to solve a partially observable Markov decision process
(POMDP) in real time, (Ulbrich and Maurer, 2013) organized the entire decision system using
two levels: one that detects if a lane change is possible and/or beneficial, using two different
signal processing networks, and a POMDP that has as input these networks and chooses the
action to take the AV to a state from a defined set of eight possible states. These are defined by
three boolean variables, that represents if the lane change is possible, if it is beneficial and if it
is in progress, while the action set is composed by continue in lane, change lane and abort lane
change. The main idea is to encapsulate into the POMDP all the sensor noise handling while
maintaining a low complexity so as to allow real-time execution.

Still in the lane change use-case, (Wei et al., 2011) uses a point-based Markov decision
process (QMDP) to implement a decision-making capable to account for three types of uncertain-
ties: sensor noise, perception limitations and other vehicles’ behaviors. Such interpretation of the
usual MDP algorithm uses Monte Carlo sampling from the sensor readings to define the states
which will have the reward calculated, instead of using a POMDP. The sensor uncertainty and the
perception range limitation also modifies the transition probability calculation during the policy
evaluation.

In (Brechtel et al., 2011) an MDP with a Dynamic Bayesian Network (DBN) as a transition model is proposed. The state space is discretized in rectangles of equal size so as to allow the definition of a finite set of states, while the use of an DBN gives the possibility to express multiple abstraction levels. The model resolution is obtained by applying a Monte Carlo approximation, that is solved partially offline and then refined online, allowing a real-time execution.

Two types of uncertainty are the focus of (Brechtel et al., 2014) proposed POMDP model: the environment evolution uncertainty and the limitation of sensor. In order to address these parameters, the transition probability function is defined by a DBN, similar to (Brechtel et al., 2011) but without the state space discretization, where the current state is related to the environment context, the planned trajectory and the action, transitioning to a new state with a certain probability. Finally, the model is solved using the Monte Carlo Value Iteration, an algorithm proposed in (Brechtel et al., 2013) which determines a discrete representation of the state space and calculates the α-vectors; such representation is formed offline and then used in real time for a T-intersection use-case.

Addressing the same two uncertainty sources, (Hubmann et al., 2018) defines a POMDP
with a limited number of parameters, searching to determine the longitudinal acceleration neces-
sary for the AV to cross an intersection. The lateral motion is considered to be extracted from
the road geometry. Each vehicle in the environment is represented in the state by its position, longitudinal velocity and its assumed path, which is not observable as the other two variables, but it is determined from the current state of the vehicle in question and it has its prediction uncertainty calculated by a naive Bayes instance. This POMDP is solved using an adaptive belief tree (ABT) proposed in (Kurniawati and Yadav, 2016), a method that uses an unweighted particle filter-like approach to create a belief tree while selecting with actions should be favored in the particle sampling using an upper confidence bound determination (UCB).

Bayesian change-point detection is used in (Galceran et al., 2017) to classify observed states from other vehicles based on predefined action-policies, or intentions, which are formed by low-level commands. These distributions are then sampled to determine the possible actions that need to be evaluated, for the entire environment (AV and other vehicles). Then the expected reward for each possible state are maximized to find the best policy to be executed.

Without a high penetration of automated vehicles in the real world vehicle-to-vehicle communication will remain based on non-verbal signals between drivers, as is today. The work in (Lenz et al., 2016) offers a method to participate in such exchange using Monte Carlo Tree Search (MCTS). It is defined that two vehicles are interacting if their respective reward functions are influenced by each other, which means that changes in the value function (the expected reward considering some fixed horizon) happen due to the behavior from another vehicle. In the defined context it is also assumed that all vehicles act in a rational manner, i.e. they try to maximize their reward function. The MCTS proposed is similar the ABT algorithm of (Kurniawati and Yadav, 2016) in the sense that it also uses a tree structure and the UCB algorithm to select which action should be used to expand the tree during its evaluation process. For each vehicle the reward function (in this case a cost function) is defined by the cost for the considered vehicle, itself defined by typical parameters like lane change cost or acceleration cost, calculated using a weighted sum, and a cooperative cost function defined as the sum of the vehicle cost and all other vehicles' cost multiplied by the cooperation factor. The first one is used in the tree expansion and the second updates the cost in the back-propagation. Multiple scenarios are tested, with different cooperation levels.

The starting ideal used in (Broadhurst et al., 2005) is to reason about the road users future paths and to assess the related danger from the combination of all of them. Pedestrians and vehicles were given geometric bodies (squares and rectangles respectively), with the latter following a front-wheel steering single track model. Two different goals are considered, straight line following and road following, so as to determine the future control inputs, which has its risk measured by a conditional probability, dependent of these control inputs. The integral resulting from the conditional probability is calculated using a Monte Carlo random sampling, which samples behaviors from different trajectories defined by different intentions (as stop, turn and stop, change lane, etc.). The end result allows the algorithm to detect intersections in the path of each road users, and according to the probability of this intersections to raise a warning of unsafe behavior in the environment.
Focusing in the intersection problem, (Barbier et al., 2018) proposes an POMDP to model the uncertainty related to sensor readings and other vehicle behavior but also key performance indicators to measure the calculated policy quality. The state evaluates is defined by the distance to the intersection and the speed of the ego-vehicle and the other vehicle together with the calculated intention from the other vehicle and the expectation for both vehicles in regards to each other. These three last variables, intention and expectations are calculated as proposed in (Lefèvre, Laugier, et al., 2012), which motivates the Bayesian network representation of the transition probability. A method known as POMCP, proposed in (Silver and Veness, 2010), solves the POMDP model using a combination of Monte Carlo update of the belief state and a MCTS representation. The key performance indicators are divided in four categories: safety, navigation, trust and comfort; they were used to evaluate two different policies calculated using different weights for the rewards' component terms. The set of indicators were able to represent the performance of the policy related to each of the categories and the trade-off available between then to improve the performance.

Decision-making can also be implemented using fuzzy logic; (Claussmann et al., 2018) employs a multi-criteria decision-making based on fuzzy logic to select the most appropriate trajectory to be executed by the AV in an highway scenario. A wide range of criteria is considered, from vehicle and passenger safety to passenger comfort and energy savings, to select which trajectory has the best behavior (if the AV should change lane or stay in the same one) and the most desirable acceleration/deceleration profile. The usefulness of such approach becomes clear due to the capacity to mix a fairly big number of criteria (eight in this publication) and reach a decision concerning multiple candidates of trajectories. Another application of fuzzy methods is the estimation of risk during driving. Using a two-level architecture (Derbel and Landry Jr., 2018) uses a fuzzy approach to measure the global risk of a situation.

Any type of negotiation between humans, that inevitably will fall under the AV's purview, can be focus of a learning method. Using the lane swap that might happen in an highway environment as an use-case, (Schmerling et al., 2018) proposed a learning algorithm capable of determine probability distributions over possible behaviors from human to human training data (obtained experimentally), to then determine a policy using conditional variational auto-encoders. Using as input the history of the interacting driver and the optimal response from the AV, this network is capable of estimating the future response of the driver, from a Gaussian mixture models used to evaluate the probability to observe some specific answer from the driver.

Lane changes are recurrently target of decision-making implementations, given its complexity in a highway scenario. Having as an objective the evaluation of a lane change desirability, (Scheel et al., 2018) adopted a bidirectional recurrent neural network (RNN), which can process information in both directions of time. According to the results, such arrangement allows the algorithm to improve its performance in detection when a lane change is possible in comparison with the same network exploring only the future and also in comparison with the results of an SVM-based risk assessment.
Markov decision processes, and particularly the partially observable variation, can take
a prohibitive amount of time and computational effort to be solve, without even pointing out
the necessity of variable discretization. One of the applications of deep learning has been the
policy representation of such problems using a neural network, facilitating the application
of reinforcement learning methods. (Qiao et al., 2018) compared the results of policies for
crossing intersections from three different methods: one based on time-to-collision, another which
implement calculates a POMDP via a long short-term memory (LSTM) neural network and a
MDP model with hierarchical decisions. This structure divides the possible policies in different
categories restricted only to certain states, and in the experiments conducted produces the safest
policy, in comparison with the other two implementations.

Every learning method so far dealt with the decision-making component of the automated
driving, always having the control as a separate piece of the pipeline, consisting on the information
flows named sequential or integrated, in figure 2.1. The first example of end-to-end driving
here comes from (Jaritz et al., 2018), with a deep reinforcement learning algorithm for race
driving. Using a realistic rally game to extract the training data and a state decoder composed
by convolutional neural networks (CNN) plus LSTM with a asynchronous actor critic (A3C)
framework, which allows the network escape from local minima at training, the end result is a
policy capable of driving the AV, although still with some crashes. The calculated policy also
shown some generalization with tested in unseen tracks.

One of the main problems with black-box type learning methods is the lack of assurances
about the existence of unsafe outputs, given the definition of safe for a specific context. To avoid
this inconvenient (Mirchevska et al., 2018) coupled a reinforcement learning formulation with a
safety verification of the next state given the action to be executed, allowing the end policy to
guide the AV through a highway scenario, executing a target velocity and navigating through
multiple vehicles, which sometimes demand lane change operations. The state used in the model
corresponds to only thirteen variables, the AV's velocity itself and the relative velocities and
distance towards other six vehicles considered in the policy calculation. Such limited set of
features also favors a faster convergence rate than larger implementations.

Targeting pedestrian collision-free automated driving, (Pusse and Klusch, 2019) used
an hybrid POMDP resolution method, combining the deep reinforcement learning and the
approximated POMDP planning. The approximated belief tree built during the POMDP planning
operation has its construction guided by the neural network, for each leaf expansion the new
belief distribution is given by the network's output. As training data the collision history recorded
in project GIDAS (German in-depth road accident study) are used, resulting in a policy capable
of avoiding such collisions while remaining competitive in terms of performance and smoothness
of driving.

Reinforcement learning does not restrain itself only to the use of deep learning methods
to calculate the policies. In an application of inverse reinforcement learning to obtain driving
styles from human drivers, (Kuderer et al., 2015) tried to determine parameters from real data
to improve the comfort during the automated driving. Features like longitudinal and normal acceleration, jerks, following distance and curvature were used to learn the closest policy that results in a behavior compatible to the one demonstrated by the driver.
## 2.2 Ethical decision-making

In more common applications an instance of decision making tries to emulate reasoning based on objective quantifiable concepts that are connected by logical relationships. Every bit of care is taken for ASs in general to adhere to strict limitations on performance, comfort, safety and so forth. However, as the number of applications where robots are employed without supervision increases, they get closer and closer to situations in which not only economical and scientific factors are important, but also certain moral features<fnref n="3" /> the consequences of an automated system's actions should be another parameter in its decision-making (Arkin, Ulam, and Wagner, 2012; Allen et al., 2000). The automated vehicle is an emblematic case, since controlling a one thousand to two thousand kilogram vehicle at 40km/h with unprotected humans around clearly demands an evaluation of the risk that actions might pose to multiple parties. Many other such morally salient cases exist and will continue to crop up in the future, such as the helper robot which will interact with the elderly, or more topically, the level of independence of "autonomous" weapons. As the point of depart of the discussion about artificial moral agents, the three main domains of normative ethics will be discussed to then detail some of the implementations of artificial moral agents proposed throughout the years.

### 2.2.1 Normative Ethics

#### Consequentialism

Consequentialist ethics can be defined by the idea that an action is morally acceptable, desirable or necessary in virtue of the results it produces (Gips, 1995; Alexander and Moore, 2020), rather than the nature of the action (or agent) themselves. Of course, before any type of evaluation can occur, what is of value needs to be defined. It is generally agreed upon that "the Good" is the value that must be targeted, i.e. an action is more morally justifiable if it increases "the Good". The definition of goodness varies according to the flavor of consequentialism considered. Taking the example of utilitarianism, the 'Good' which ought to be considered is underpinned by a monistic account of value, which implies that utilitarians hold that only one factor in a decision has moral salience, namely happiness or pleasure(Brink, 2018). Other consequentialist theories, on the other hand, may be underpinned by a pluralistic account of value, implying that multiple values ought to be seen as morally relevant in decision making: John Rawls, for instance, believed that the desirability of an action should also be connected with questions of justice, such as who receives this "Good", and how this effects inequalities in society.

Two main currents of thought from this domain of normative ethics will be discussed later on: utilitarianism, where the Good should simply be maximized; and egalitarianism, which defends that an equal distribution of the Good is morally preferable to its simple maximisation.

<footnote n="3">³The terms ethics and morals will be used interchangeably.</footnote>
Two main critiques may be levelled against consequentialist theories. The first is that many consequentialist theories, by for instance focusing exclusively on the maximization of happiness, do not capture enough about what is seen to matter morally. Other features that many people might find important in moral decision making, such as the motivations of the agent, the circumstances of the action, or any pertinent rights or entitlements are often disregarded. There is no list of a priori forbidden actions, everything boils down to the consequences produced by the action, however apparently abhorrent it may be. In the AV context, this would represent the act of targeting an older person to save two younger ones for example, considering only the general maximisation of utility. From this conclusion came the idea of relaxing the maximization requirement, allowing the consideration that only a certain amount of utility may be sufficient. To this end, the second critique addresses the practical feasability of these more monistic types of consequentialist theories, which compel an agent to consistently and categorically maximize utility, leaving little room for individual goals or preferences, or any weakness of the will on the part of the agent.

## Deontology

This domain of ethics defends that an action should be considered good or evil according to its nature, denying the justification of an action based on its results and imposing a rigid and immutable constraint that cannot be changed, a norm, which is the case of the categorical imperative from Kant. For an action to be good, it needs to obey a categorical imperative, i.e. the rightness of an action is assessed by its adherence to a universal maxim or law which all rational agents autonomously accept (Allen et al., 2000). One clear consequence of this approach aligns with the second critique of consequentialist theories, namely, that the uncompromising recommendations that deontology may yield are too much for many human beings to live up to. Some other lines of thought consider more flexible interpretation of the pre-defined norms, allowing exceptions to be made according to the situation.

One of these interpretations, proposed by W.D. Ross, consider the norms to act morally as *prima facie* duties. Such an interpretation is useful in the case of a conflict between the duties, were it is argued that a stronger duty can supersede another. It also offers a list of basic duties that a person should observe and a priority list, that creates an hierarchical order between them in case of conflict. Asimov's three laws of robotics is also an example of normative framework based on the essential premise of deontological ethics.

Another class of interpretations about how to use norms to define if an action is morally acceptable is the contractarian deontological theories. An act would be immoral if it violates a framework of norms defined by a social contract and accepted by society. The origins of Rawls' theory of justice resides in deontology, since the two imperatives which ground his theory– that inequalities are not acceptable and if they exist, they should benefit the worse off–are basically norms. Later on, a version of these two laws will be adapted to the AV context.
One of the main critics of this type of moral reasoning is that sets of norms resemble more heuristic attempts to capture a deliberation process that would be better represented with an utilitarian approach (Gips, 1995). Another is the lack of consideration of information uncertainty and uncertainty in actions' consequences into the definition of the normative framework, although some recent works address this question (Alexander and Moore, 2020).

## Virtue Ethics

Virtue ethics predates both previous ethical schools and departs from a focus on both actions and consequences. Its origins can be placed in ancient Greece, when ethical behaviour was understood in terms of an agent's virtues and dispositions, rather than an action's consequences or its rightness according to some normative framework. Thus, if an agent has a virtuous disposition—acting with wisdom, courage, temperance and justice (the four cardinal values proposed by Plato)—then right action would be a consequence of his reasoning and deliberation process.

One can already understand that such theory is based on highly symbolic values held by persons, the concept of a virtue, which can be defined as human excellence embodied in a list of character traits (Hursthouse and Pettigrove, 2016). Naturally, the substantive definition of these virtuous traits is the point of contention for this approach. Some, as Aristotle, argue that virtues are divided into intellectual virtues and moral virtues, with the first type has the possibility to be taught, while the second set must be learned practically through experience. This learning in practice is one of the main tenets of virtue ethics, allowing the agent to discern what to do to accomplish its intention through an action in any situation, and thus developing indirectly the virtue connected to this action.

### 2.2.2 Artificial moral agents

Artificial moral agents (AMA) is a qualifier that represents every application that tries to implement some sort of ethical reasoning. This goes from simple applications, like the ones proposed in (McLaren, 2003) and (Anderson, Anderson, and Armen, 2005) that are basically programs have ethical recommendations as an output, to (Thornton et al., 2017) and (de Moura et al., 2020) who propose ethical components close to real robotic applications. It should also be pointed out that in most cases, the aim of these approaches is to approximate human moral reasoning, able to consider a universal set of problems, using some form of generic formalism to translate the world into comprehensible data.

Another choice is to focus on specific applications, which is the case of the methods proposed in the next chapters, where the entire ethical deliberation process is designed to solve problems having a specific format and constant properties. Therefore, the question is not whether the agent is morally good or bad, since the approach itself does not aim to simulate moral agency.
Instead, what is important is that the artificial moral agent is capable of making ethical choices which align or coincide with what a human moral agent might decide in a similar context, using the same tools and available information. This argumentation is what motivates the use of the word automated instead of autonomous. Both cases, AMA for generic and specific cases, would be classified as explicit ethical agents using the classification proposed by (Moor, 2006), given that the ethical deliberation are coded into their systems, for more generic that they may be.

The role that uncertainty in information acquisition and processing has within any ethical deliberation (Anderson and Anderson, 2007) must also not be forgotten, because it can directly impact the end decision or invalidate the entire reasoning method. This is one of the main difficulties of the implementation of AMAs, since uncertainty is always present in measurement and most of the time it is not easy to estimate. Most of the works in the domain assume that the information received from other parts of the system is exact, avoiding this concern.

The three domains of normative ethics are viable options to be implemented into an AMA. Deontological and consequentialist approaches are ever present (Gips, 1995; Allen et al., 2000) with the Kantian categorical imperative and the utilitarian maximization principle respectively most of the time. Virtue based methods are less popular, and considering that an AMA does not have agency, an ethical reasoning method based on this approach could be proposed as having some sort of variables that represent virtues that might evolve through time, according to the success, failure and observed consequences of its actions. Another way to implement a virtue-based approach is to use the role morality concept (as is done in (Thornton et al., 2017)). According to (Gips, 1995), virtue-based systems are usually translated as deontological approaches for an application. The other two are the focus of much of the published works on the area, as we will explain shortly.

AMAs can be employed in a wide range of applications, from counseling a human's ethical decision to deciding whether a lethal action from a drone is ethically permissible. In the automated vehicle domain the ethical component is most of the time connected to the safety claim of the road users, meaning that there is always a risk of death involved. Therefore the domain is posed to be the first one that presents to laypeople an application that can present ethical behavior in some situations, given that it was already established that braking and relinquishing control from the AV to the driver is not always the best option (Lin, 2016).

## Related works

Since the advent of autonomous systems and our expectations for their deployment in the real world, certain ethical concerns related to these systems have become well known. In (McLaren, 2006), two implementations of the casuistry approach, were a real problem is compared to an instance of a similar case so as to guide the decision-making, are reported one. The first compares ethical dilemmas questioning if the truth or a lie should be told. Adopting the point of view from the person that ponders what to do in a dilemma, the algorithm points out the
motivations as to why the truth should be told that are valid for the current situation and the base
situation (the one loaded *a priori* in the machine to serve as a comparison point), that are more
strongly connected to one case or that it is only valid in one instance.

The second program, proposed in (McLaren, 2003), operates as an ethical board review
would, comparing past instances of deliberated cases and ethical codes. Then, given a new case
to be analyzed, the system would give a list of possible pertinent codes, a list of pertinent cases
and additional suggestions concerning the relationships that may exist between the cited ethical
codes. Its deliberation procedure involves a two-step graph-mapping algorithm, where in the first
each of the cases in the database are given a score according to the similarity to the one being
evaluated, which is used with a A* algorithm to establish the most similar cases.

Taking a similar approach, using recorded cases of ethical decisions as the baseline to
the resolution of new ones, (Anderson, Anderson, and Armen, 2005) implements the principles
of Biomedical Ethics (that are *prima facie* duties) into a program, which extract principles from
some cases and use these to solve new cases. The implementation is divided in three components:
a knowledge-based interface, that manages the selection of principles to be applied, a advisor
module, that make the decision and a learning module, that abstract principles from particular
cases. This last one uses inductive logic programming to generate the decision rules that are
representative from the problems given as training and that might passed undetected given that an
reflection of multiple cases is necessary to detect them.

Ethical constraints for autonomous weapons were addressed by (Arkin, Ulam, and
Duncan, 2009) through the definition of a framework that contains a ethical governor, proposed
in (Arkin, Ulam, and Duncan, 2009) and an ethical adaptor, proposed in (Arkin and Ulam, 2009).
The first module restrains the lethal actions that a robot can take given constraints defined by
the Laws of War and the rules of engagement, which are grouped in obligations and forbidden
constraints for the current mission. Such constraints are applied to the robotic response calculated
by the system, and if it is not a permissible action another one is selected and then executed.
Two components define the action selection: one deals with evidential reasoning, extracting from
perception, *a priori* information, target data and current behavior the logical assertions that will
confront the current constraints; and the constraint applicator, that process such logical assertions,
composed by the constraint interpreter, that translated the general language used to restrictions
that should be applied in the current situations and the damage estimator, that estimates the
consequences of an action in an utilitarian fashion, accounting for structural damage and loss of
life. However it is assumed that accurate targeting with precise uncertainty correction is employed,
which may be too optimistic to consider.

The ethical adaptor acts in the level of the constraints used to evaluate the chosen
behavior, and more generally tries to modify the robot's behavior so as to insert an emotion-like
deliberation during the behavior selection. It functions both as a reviewer of the robot's actions
after the fact and it measures the effect of a violation of the LOW or ROE using emotion-based
functions; both mechanisms have as objective the evolution of the robot's procedures so as to
prevent another violation of its constraints. As such, it works only by increasing the intensity of
restrictions, never on the other direction. In (Arkin and Ulam, 2009), it is the second function
that is discussed. It employs a measure of guilt towards violations of the restrictions, which
can accumulate throughout the mission and result in then necessity to disable temporarily or
permanently the lethal actions available to the robot until an after-action review is completed. In
this context the guilt "feeling" works as a representation of the overall ability of the machine to
behave ethically.

(Berreby et al., 2015) proposes a formal language to model a generic ethical dilemma, allowing the artificial agent to reason about an ethical choice during its occurrence using the information at hand. Taking the trolley dilemma as an example, a model of causality is established as an Event Calculus model, which enables the program to reason about responsibility of actions while taking into consideration the actual state of the world and also account prevented situations. This framework then uses the deliberation given by the formalization of the Doctrine of the Double effect (DDE), represented here by the nature-of-the-action, that measures if an action is appropriate from its inherent nature, the means-end and right-intention condition, that avoids negative intentions and instances that use negative actions to achieve positive ends, and the proportionality condition, that demands that positive and negative effects be proportional.

On the same line, trying to give the machine the capacity to deliberate similarly as an
person might do in ethical dilemma situations, (Bonnemains et al., 2018) propose formal tools to
describe a situation and some models of ethical principles that can be used with this descriptions
to achieve an ethically motivated decision. Three ethical frameworks are proposed, based on
utilitarian and deontological ethics and another inspired by the Doctrine of Double effect. Given
a particular situation, it is described as logical facts which are taken into account to deliberate on
a decision by a respective profile; the utilitarian approach chooses the decision that present the
greater good having also the lesser evil; the deontological approach judges the decision by its
nature; the DDE is implemented with the same formalization than the proposed in (Berreby et al.,
2015). The same assumption made in (Arkin, Ulam, and Wagner, 2012) and in (Berreby et al.,
2015) is present here: all decisions and facts are considered to be certain, hence no uncertainty is
taken into account inside the deliberation process.

Using a new approach to decide under ethical dilemma, (Leben, 2017) proposes a criteria
based on Rawls’ Maximin principle as an alternative to an utilitarian approach or the usage of the
Doctrine of the Double effect, outlining an algorithm to implement such a principle while using
a "veil of ignorance" to conceal information that could create a bias. The procedure applied in
a dilemma, using an automated vehicle in a inevitable collision as an example, is to put every
involved road user in an original bargaining position of fairness to find the final decision. The
biggest difference from the utilitarian approach if that the proposed decision procedure operates
trying to increase the worst possible option that might happen, while the utilitarian approach
always based its decision in maximizing its expected criteria in uncertain situations, without
looking to what might happen in the worst possible option.
But one can only go so far with hypothetical situations. Parameters such as dynamic interactions between agents and uncertain action consequences must be taken into account to produce fair, realistic, and acceptable ethical deliberation. Focusing on a situation when an AV must decide between a collision with pedestrians or a physical barrier, (Pickering et al., 2019) used an estimation of the AV’s deformation against the barrier and statistical data to define a risk velocity for the pedestrian collision. A bi-linear model of the deformation is tuned to be similar to a finite element analysis (FEA) instance of a full-frontal collision, and from that model the maximum deformation that can be produced so as the injuries involved are minor is obtained. The pedestrian injury severity is then represented by the vehicle’s velocity obtained by a statistical analysis of collisions in another study. Then the deliberation becomes clear if one or the other possible decision, collide with the barrier or with the pedestrian results in minor injuries, but the case when it is equally bad to do either is not treated.

Taking a design approach to infuse ethical constraints in the control component of an
AV, (Thornton et al., 2017) uses concepts from deontology, consequentialism and virtue ethics
to define a Model Predictive Control (MPC) that respect ethical constraints by design. Such
MPC is proposed in an straight road, with shoulder and an obstacle ahead of the vehicle. Every
choice that may be taken in this scenario have an ethical component: if the vehicle uses the other
lane while there is a double solid yellow line it will break the traffic code; if it uses the should
lane then it needs to be unoccupied and can only be used for brief periods of time; and if the
stop behavior is chosen then the mobility property of the vehicle is affected. Firstly, the path
tracking cost is dependent to the necessity to deviate from the reference trajectory while the
steering angle have two constraints from different philosophic origins: a limit on the steering
angle limits (in a deontological sense) and a cost function connected to its rate of change (in a
consequentialist sense), a process to avoid the obstacle with absolute certainty and the adherence
to the traffic code, which is treated as a soft constraint that can be set with a high weight
(thus approach a deontological behavior) or with a low weight (approaching a consequentialist
behavior). Two different experiences are made, one with different weight values from each of the
reward parameters and another simulating a form of role morality connected to an emergency
vehicle goal.
## 2.3 Behavior prediction

An essential role of the AV during execution is the capacity to predict other road users' behaviors, given the environment that they are in. Multiple information sources can be used to predict what road users intent to do next, from the road structure itself to wireless communications and traffic rules, without forgetting the road users' dynamics itself. The most immediate use of these methods are in advanced driving assistance systems (ADAS) to detect possible dangers to the driver and passengers, but without the need to deliberate on an action based on this information.

Different types of road users are present and interact between themselves in urban environments. A useful classification of this environment is the definition of vulnerable road users (VRU), which assemble pedestrians, cyclists and two-wheeled drivers into one single category that distinguishes itself for the lack of protective "shell" (WHO, 2018) surrounding the user. Every one of these groups is the focus of multiple studies to predict the behaviors of each specific road users type, but the two most studied groups are pedestrians and car-like vehicles, given that 66% of deaths in EU roads in 2018 were pedestrians or vehicle passengers (Commission, 2018). Pedestrians and car-like vehicle passengers are the only two types of road users considered in this thesis.

According to (Rudenko et al., 2020), motion prediction procedures contain three main elements:

* Stimuli: represents the agent's motivation to execute the trajectory observed. It can be divided in two parameters, the agent motion intent and other influences, exerted by the environment itself (and in this case the road infrastructure) or by other road users.

* Modeling approach: encodes the agent's reasoning; given a stimuli composed of an intent and the environment influence, it produced as output what the agent will do in the future to accomplish its intent.

* Prediction: the format of the output from the previous element; it can be the a trajectory itself to a probability distribution given some possible maneuvers for example.

The reasoning model is the main component of the behavior prediction. Three different approaches may be taken to reason about an agent behavior: focus on a physical description of the agent to predict on a short-term basis, try to learn these behaviors from data and reproduce it generically or reason about each agent motivations to then find the correct behavior. In these three options the term behavior represents a different quantity being estimated. Figure 2.2 shows which is the meaning of behavior in a short *Δt*, a mid-range *Δt* and a long-term *Δt* prediction<fnref n="4" />.

<footnote n="4">⁴Roughly speaking, one can consider a short *Δt* as less than 1 second, and a long-term *Δt* as more than 4 seconds</footnote>
This structure can be identified in the survey done in (Rudenko et al., 2020), where physics-based methods predict short-term movements, pattern-based methods try to learn features and cues from past agents’ trajectories and planning-based methods that reason about the agent’s motivation.

<figure><img src="image_12.png" /><figcaption>Figure 2.2 – Hierarchy of possible significations for behavior</figcaption></figure>

A different classification is proposed by (Lefèvre, Vasquez, et al., 2014), where three different types of behavior prediction are also proposed, with the first pertaining to the physical prediction, short-term models that takes into account the mechanical properties of the agent. The difference between both classifications comes from the other two categories, maneuver based prediction and interaction based prediction, which represents the capacity to observe a specific maneuver being executed, already accounting the possible intention determination that lead the agent to choose a maneuver and, lastly, changes in behavior during interactions between road users. What becomes clear from this classification is that the three levels as defined are not disjoint, they can complement each other, going from prediction close to the seconds scale to accounting interactions between agents, as to plan and execute a mission.

In comparison between the classification proposed by (Rudenko et al., 2020) the learning method does not need to restrain itself only to a maneuver abstraction level, it can determine the intent of a road user using the data available, that usually is also composed by interactions with other road users. Clearly, the proposed organization it is not completely rigid in its definition. But, since it is more pragmatic, it considers the implementation method for behavior prediction, thus interactions between agents are considered at every level. To understand the body of work in behavior prediction (which is also present in some decision-making methods too, since the former frequency is a part of the latter) it is important to consider the type of method being used to implement the prediction model and what is really being observed as a behavior.

### 2.3.1 Vehicle prediction

Methods that use the physical prediction approach usually search the minimization of measurement errors while predicting the position of the vehicle in the near future. Aligned with the ability to predict the behavior in short-term periods of time, one the main use cases of such approach is to estimate risk of collision given a specific situation. Considering a cooperative group of vehicles in a road with the possible presence of cyclists and pedestrians, (Batz et al.,
2009) uses unscented Kalman filters (UKFs) to predict trajectories during a specified Δt and thus monitor the distance between pairs of agents, taking into account the physical dimensions of each road user. The distance is calculated from a set of vectors defined by the Minkowski sum between the uncertainty ellipsis, calculated from the covariance estimated by the UKF, the possible rotations of the rectangle that represents the body of the road user, which also considers a range of values extracted from the covariance matrix, and the mean position. Inside a group of vehicles, one of them is designated as leader, which will execute the probabilistic prediction, check if all vehicles are at a minimal distance from each other, and if there are not then signal that the situation is dangerous.

The trigger time of AEB systems is a critical parameter that might prevent a collision or even reduce its severity. It is in the short term that the real need of activation needs to be checked, which is proposed in (Kaempchen et al., 2009) to be determined considering the trajectories of all road users involved. Only if all possible trajectories evaluated result in a collision that the vehicle must trigger the braking (reason why only the maximal acceleration is considered to determine the trajectory). One sensible point is the determination of which trajectories should be checked, which is done by sampling the Kamm's circle<fnref n="5" /> to obtain the different values of longitudinal and cross accelerations that might be applied in a short period of time. Given the infinite number of possible trajectories, a search through the circle is done using the approximate collision intersection area between the involved parties. When no zero area is detected after a gradient descent search, the AEB must be triggered.

In (Brännström et al., 2010) a linear bicycle model is used to model vehicles in near accident scenarios and assess the risk of collisions. These models are then tested to verify if there are possible collisions in the future, and if there is, to determine and execute different policies according to the driver's preferences and the other vehicle's actions. Observations that, for example, drivers tend to use constant steering angle velocity followed by a constant steering angle (Godthelp, 1986) during normal driving or in evasive situations, specially in the moose test<fnref n="6" />, that the steering velocity is correlated with the posterior steering angle (Breuer, 1998) were used to model possible maneuvers to be tested. They are a combination of swerving and acceleration or braking, always determined to avoid contact with other road users, given that each one of them are considered as rectangles. The system is triggered if no possible safe maneuver that respects the driver's preferences (orientation position and its rate of change and acceleration value and its rate of change) and proceeds to a two-step verification: considering the other road user as deterministic, it finds the maneuvers that the ego-vehicle should execute, and also does the opposite for the other vehicle. As such, it can improve the timing of AEB activation as assess how the driver can avoid collisions.

Following the same line of (Brännström et al., 2010), the uncertainties connected to road geometry detection and measurement are accounted in the sampling of possible trajectories

<footnote n="5">⁵Encompass all possible direction of the forces between the interaction of the tires and the road.</footnote>

<footnote n="6">⁶The moose test is a high-speed avoidance maneuver test that tries to emulate a vehicle avoiding an obstacle ahead maintaining its velocity constant during a lane change and going back afterwards</footnote>
by (Petrich et al., 2013). Each lane center-line is approximated by a cubic Hermite curve, and the mean value of the vehicle's state (estimated by an EKF) is projected into this center-line, defining a way-point. Since there is also uncertainty in the lane's determination, they are also considered to be distributed normally, thus making the assignment of a dynamic object to a lane by an $\chi^2$-test possible. Each lane, to be considered as a viable hypothesis, need to score higher than a determined threshold in the test. Then all possible trajectories are predicted by the EKF, considering constant acceleration and that the vehicle always follows the orientation of the center-lane. These hypothesis over time are evaluated by a multivariate cumulative sum algorithm, used to detect small and moderate mean shifts in probabilistic distributions, which is adapted to consider the vehicle's possible lane change.

As it can be seen, for the physical methods approach the most used implementations to model the vehicle are constant models, for example constant velocity (CV), constant acceleration (CA) or constant turn model (CT) with a bicycle model to represent the dynamics. But more complexity can be necessary in some contexts, even more in dangerous situations that tend to approach the vehicle to high lateral accelerations (Polack et al., 2017). Kalman filters are the go to method to account for uncertainties, but there are implementations that use Monte Carlo methods or dynamic Bayesian network (DBN) to relax the Gaussian incertitude assumption (Rudenko et al., 2020). Other methods that can be applied are potential fields derived algorithms and interaction multiple model (IMM) implementations.

Using maneuver recognition, with pre-determined maneuvers, and a constant yaw rate and acceleration (CYRA), (Houenou et al., 2013) achieves an improved prediction accuracy in comparison if only the physical model was used to predict the trajectory. Three types of maneuvers, keep lane, change lane and turn at intersection, are used to generate different trajectories using the current state and the road's parameters. A Malahanobis distance between the current position and the center-lane is used to define the correct lane and, by consequence, the maneuver being executed. The selection of the most appropriate one is done by a cost function that accounts for the comfort during the execution of the trajectory (which means no high normal accelerations) and a time parameter to punish longer maneuvers. The physical prediction is done using the CYRA model, as if the vehicle was a determinist agent. This physical prediction and one of the sampled trajectories are fused using a pre-defined weight function.

Also considering maneuvers, but this time taking an offline learning approach to learn following, overtaking and flanking maneuvers, (Firl and Tran, 2011) uses a Hiden Markov Model (HMM) to represent each one of them. The learning method chosen is an expectation-maximization-type (EM) algorithm, with the online recognition being done by calculating the value given by $\operatorname{argmax}_i P(\lambda_i|O) \propto P(O|\lambda_i) \cdot P(\lambda_i)$, with $\lambda_i$ being the HMM model and $O$ the observation vector. The likelihood $P(O|\lambda_i)$ is modeled as a mixture of Gaussians (MoG), with is obtained, together with the prior, in training. Still, roads with different spatial disposition and interaction between more than one vehicle are not considered.

Further improvements came in (Tran and Firl, 2013) where a bi-dimensional Gaussian
process was used to model traffic situations at intersections and an UKF to estimate the trajectory. The parameters of the Gaussian process are obtained by maximizing the log marginal likelihood given some training data, which classify the behavior of other vehicles as turn left, turn right or go straight. With the most probable maneuver identified, the correct Gaussian process is used in the update step of the UKF to correct the prediction. In another implementation, (Tran and Firl, 2014), the same structure is used, but this time the algorithm combines 3-dimensional Gaussian processes with a particle filter, instead of the previous UKF. Another dimension was added to the processes to allow training the model with data that originated from different intersections and similarly, the process that correctly represents the situation is used to calculate the weight of each particle in the filter.

The road structure configuration exert an important influence into the behavior of all road users. Together with distances to surrounding vehicles and road characteristics, (Gindele et al., 2010) employs a dynamic Bayesian network (DBN) to model the relationship between position, context, behavior and trajectory. Using a bicycle model without slip to model vehicles and six possible maneuvers (free ride, following, acceleration, sheer out, overtake and sheer in), it predicts the most probable trajectory, which is approximated by a cubic Bézier curve. The resulting filter is solved using a particle filter approach to calculate the update equation. The model is further improved in (Gindele et al., 2013) adding a learning step to determine the correct policy model for other road users given a specific context.

Up until now probabilistic methods composed the entirety of algorithms discussed, but in pattern approach and also later, in planning-based methods, two other types of methods will start to appear. The use of logical reasoning is one of them. In (Hummel et al., 2008), its description logic is used to describe all the possible different forms and configurations of intersections that may exist in a city. A case-based approach is taken by (Vacek et al., 2007) to interpret situations and deliberate on a maneuver to be executed. Each case is composed by a description of a situation that might occur and the correct behavior that needs to be executed. During the execution new knowledge can be added, possibly modifying a case solution.

Deep learning is the other technique that is increasingly popular in behavior prediction. Long short-term memory (LSTM) is used as a recurrent neural network (RNN) in (Cho et al., 2019) in the implementation of the encoder, interaction and prediction components. The first models patterns of trajectory of other vehicles, the second measures both multi-modality (how many situation can occur) and robustness slackness related to a rule (exclude situations that cannot occur) while the third effectively predicts the trajectory and the robustness of a rule. Maneuvers are considered as a logical relation, formalized by a signal temporal logic (STL) approach, which has a robustness slackness measure defined to create an order of priority in a set of rules. The last component of the algorithm is a controller, implemented by an MPC.

Another work that uses deep learning is (Messaoud et al., 2021), which considers the environment surrounding the ego-vehicle as a grid, to encode drivable areas and all vehicle present into the input vector to the encoder layer. Then a middle layer, called attention layer, decides
which vehicles must be prioritized when the trajectory is being defined. The output of this layer
is fed to the decoder layer, that executes the trajectory prediction, formed by two networks: the
LSTM decoder and two fully connected layers separated by a leaky rectified linear unit (ReLU).
Each output of this last network represents the probability of the predicted trajectories.

Pattern approaches can use pre-defined maneuvers or offline learning methods but with a
defined set of maneuvers. Popular methods are GPs, HMMs, DBNs, neural networks (Rudenko
et al., 2020). But there are also methods that use learning to model and detect the intention of
other road users. Intersections are one of the most dangerous road environments, given the number
of accidents that are observed in them. The work in (Lefèvre, Laugier, et al., 2012) proposed
to use the difference between what is expected from road users from what they intent to do as
a measure of risk. A DBN model is used to estimate the vehicles’ motion while the behavior
intention and expectation is estimated jointly. Both the context at the moment of estimation and
the interaction between road users, through the jointly estimation, are considered to measure the
risk. An RNN with LSTMs is used in (Zyner et al., 2018) to predict the intent of other road users
in non-signalized intersections. The proposed method is applied in tangential roundabouts<sup>7</sup>, with
lidar data as input.

In an implementation of a system capable to predict vehicle behavior in generic envi-
ronments, (Bonnin et al., 2012) proposes the use of an hierarchy of cases, where each node
represents a specific behavior that might be detected in different locations. Inside each node there
is multiple models, itself defined by a set of features and classifiers. A node is activated based on
GPS readings and road infrastructure information collected from an *a priori* map, and it competes
with its children nodes to find the one that better fits the situation.

Uniting physical, pattern and planning based approaches into one single framework,
(Lefkopoulos et al., 2021) implemented a predictor that uses an interacting motion model Kalman
filter (IMM-KF) with 6 different longitudinal and lateral behaviors for each vehicle, which passes
through an selection based on the detection of collision during prediction, given the size of each
vehicle. Then an hierarchical approach allows the algorithm to define an order of priority, taken
into account the Highway Code, decoupling the multiple prediction of N vehicles into N single
prediction operations.

Focusing on a long horizon prediction of local vehicles in highways, (Xin et al., 2018) used two LSTM networks, one that concentrates into determining the driver's intention, and a second dedicated to predict the future trajectory. All the data used in classification and prediction is obtained by the ego vehicle.

<footnote n="7"><sup>7</sup>Tangential roundabouts are characterized by higher speeds given that the entry curve is tangential to the center island; this configuration differs from the radial approach, adopted mostly in Europe, that ensures the entry into the roundabout through a deliberate turn maneuver to reduce speed.</footnote>
2.3.2 Pedestrian prediction

The pedestrian’s behavior estimation methods can also be divided into the physical,
pattern and planning approaches, with probabilistic and data-driven philosophies being the most
popular implementations. Since, the trajectory prediction in the algorithms proposed in chapters
3, 4 and 5 will be made considering a constant velocity model, only a short state of the art will
be commented here, nonetheless containing the most used approaches in the domain. A more
detailed survey can be found in (Ridel et al., 2018) and for deep learning based approaches,
(Ahmed et al., 2019).

Considering the context of an automated vehicle, it is important to determine the behavior
of an pedestrian not only in correspondence with interactions with vehicles but also taking into
account the interaction between pedestrians. Using bird-eye images to as support to predict the
pedestrian behavior, (Coscia et al., 2018) represents the agent by its position and velocity. This
last one is the focus of a prediction dependent on four parameters: semantics of the position, ob-
servation from training data, constant velocity inertia and a destination probability. The semantics
of a position is supported by measures of desirability of the pixel, according to the number of
pedestrian trajectories that passed close to it and resistivity, which represent the proximity of
obstacles.

In contract to social forces prediction methods, which are usually hand crafted, (Alahi et al., 2016) uses a LSTM network to model not only the constant and predictable movement that originates from attraction and repulsion approaches, but also disruptive behaviors, as for example the response of a pedestrian when it perceives a crowded environment. To account the interaction between pedestrians the hidden states from an LSTM are shared with neighboring LSTMs.

Taking a probabilistic approach to predict long-term behavior of pedestrians and their
intent was done in (Karasev et al., 2016) by modeling the latter as a function of the goal,
considered hidden (but with a goal space known) and the state. This unknown goal is represented
by the posterior probability of goal and state given past observations, and it is updated using a
Rao-Blackwellized particle filter. Then the intent function, which is considered as a sample from
an MDP policy, is estimated not by the optimal policy, but by an approximation, since to use the
optimal solution would be to consider the pedestrian completely rational limiting too much the
choices of possible trajectory. In the policy it is considered too traffic signals states, enabling the
model to predict a stop from the pedestrian due to a red light.

As it can be seen, the methods for predicting behavior for vehicles and pedestrians are
almost the same, with the exception that for pedestrians there is another source of information
available: the body language, and more importantly for intention estimation, the head orientation.
The 3D body language of the pedestrian is modeled in (Quintero et al., 2014) using a Gaussian
process dynamic model (GPDM), one for each hypothetical behavior, for example starting to
walk, stopping and walking combined with left and right. A feature vector for each pedestrian is
formed by the 3D coordinates of specific body joints and their velocities, which has the dimension
reduced by the GPDM and used to train the correct model. A naive Bayes classifier is used to
classify an observed pedestrian according to the correct model and a maximum *a posteriori*
(MAP) decision rule determines the correct hypothesis.
## 2.4 Game theory

Game Theory assembles analytical tools that may be used to model a situation when an agent's best action depends on its expectations from the actions executed by other agents, and vice-versa (Ross, 2001). Its first foundations, in the economics context, were established in (Von Neumann and Morgenstern, 1966), with the following definition: *They*<fnref n="8" /> *have their origin in the attempts to find an exact description of the endeavor of the individual to obtain a maximum of utility, or, in the case of the entrepreneur, a maximum of profit*. In this definition three main entities can be identified:

* Individual: it represents the agent, the decision-maker that interacts with others.

* Utility: quantify the agent's preference towards some object or event, expressing these preferences into all possible choices of action.

* "Maximum of": what the individual wants from the interaction; corresponds to some deliberation method to determine the action with the most utility.

The concept of utility came about as a quantity that represented subjectively some form of fulfillment for the agent, thus its main objective is to maximize it. The relationship between choices and utility that emanates from them is represented by the utility function. It allows the mathematical formalization for the maximization operation that is executed by every agent. Two forms of utility function exists, an ordinal<fnref n="9" /> form, which express a preference order without a particular meaning for the magnitude of these utilities, and a cardinal one, where magnitude matters (Ross, 2001), such that the utility measures directly the desired property. One example of a cardinal utility functions is when such function represents a currency.

The definition of a game is the realization of some situation when an agent can only maximize some utility if it anticipates the behavior of other agents. Such abstractions allows different situations to be represented and analyzed by the same set of tools. Examples of different backgrounds that may use a game formulation are the economical domain, to study social interactions and even in robotic implementations. As for the anticipation towards other agents decision, it is based on the rationality model assumed to explain the behavior of the other agents. In normal life, rational behavior means that an agent look for the best mean to achieve a goal (Harsanyi, 1976).

Such definition of rationality is close but not exactly the same as the classical one, that consider not only a set of means but also multiple ends. It is assumed as constraints that the decision-maker have perfect access to all relevant knowledge concerning its environment,

<footnote n="8">⁸Problems arising from economic behavior</footnote>

<footnote n="9">⁹When the type of utility function is not mentioned, it should be considered as an ordinal function.</footnote>
cognitive capacity to deliberate on an action and clear preferences about its action consequences (Osborne and Rubinstein, 1994; Simon, 1955). Equation 2.1 formulates the usual optimization executed by the classic rationality assumption under certainty, where A is the set of available actions, g(·) is the action-consequence function and U(·) is the utility function.

$$a^* = \underset{a \in A}{\operatorname{argmax}} U(g(a)) \qquad (2.1)$$

However, the classical model of rationality have clear downfalls and approximations. This subject is pointed out in (Simon, 1955), where a number of adjustments are discussed. For example, in real situations the perfect information hypothesis is almost never realistic, each agent only has access to some part of the total information necessary to define the entire situation. Other two problems pointed out are the limited cognitive capacity of each agent, which may impede the optimization of the utility if it needs a complex quantification to be determined and an inability of the classical rationality to model situations when utility preferences are not clearly comparable (Simon, 1955). Another practical problem is the limited period of time available to deliberate on an action. Even though these limitations are well known, the classical rational model is still widely adopted but sometimes some *a priori* constraints are relaxed, notably the perfect access to information.

The properties below are useful to characterize different types of games and to establish the conditions in which a game unfolds (Osborne and Rubinstein, 1994).

*   **Interaction between agents:**

-   **Non-cooperative:** games with no communication or enforceable agreements (Nash, 1951), where the individuals decide on their own volition (Shoham and Leyton-Brown, 2008).

-   **Cooperative:** games with communications and/or enforceable agreements, where reasoning as a collective is possible.

*   **Decision time:**

-   **Strategic game:** each player makes only one decision, at the beginning of the game; all players decide at the same time.

-   **Extensive game:** each player has the liberty to make a decision and revisit it whenever it wants.

*   **Information:**

-   **Perfect information:** All agents have access to all information about the other players.

-   **Imperfect information:** Some information might not be accessible for the agents.
Depending on the type of game an analytical solution might exist. Non-cooperative games are the most studied type of game, since it involves competition between individuals and because cooperative games can be remodeled into non-cooperative bargaining games (Harsanyi and Selten, 1992). In this context, a game that considers the classical model of rationality is guaranteed to have an equilibrium point (Nash, 1951).

One of the most important interaction scenarios to be considered is when the decision makers do not have knowledge about preferences and motivations of the other with which it interacts. This incomplete game can be transformed into a complete game according to (Harsanyi, 1967) if a joint probability function about these unknown information exists, then the incomplete game is equivalence to a game with complete information and any equilibrium point determined in this equivalent game represents also an equilibrium point for the original game (Harsanyi, 1968b). Chapter 5 will use this transformation to estimate the behavior of other road users, given that the AV does not know their motivation.

### 2.4.1 Related works

As one would expect, all the instances where a game theoretic approach was taken involves interaction with other road users. It can be used in physical, pattern or planning approaches. In a racing scenario, where two vehicles try to overtake one another, (Wang et al., 2019) adds a prediction step into the game theoretic controller that is able to estimate how much the other vehicle will yield to the ego-vehicle. Collision is avoided because both vehicles share the same collision constraint into their controller. One player use the same game-theoretic controller while the other uses an MPC, which allows the demonstration of typical racing behaviors, as blocking and overtaking. This game controller was inspired by the implementation in (Spica et al., 2020) for two drones racing, but with the addition of the bicycle model to describe the dynamics of the vehicles involved.

The previous algorithm depends on reliable information about the other player, hence it is susceptible to measurement errors. To fix such vulnerability (Notomista et al., 2020) proposes to use the algorithm proposed in (Wang et al., 2019) as a high-level controller (notably named Senna), while implementing a low-level planning algorithm (this one named Prost) to deal with possible unreliable information. This second algorithm uses a control barrier function as a constraint to mitigate uncertainties in the opponent's model or in its state estimation.

In (Turnwald et al., 2016) the Nash equilibrium is used to reason about the interactions between agents. The use-case considered is a robot moving inside a crowded environment. Two game models are considered, one static, where all players take decision simultaneously, and one dynamic, where decision comes sequentially. The cost functions<fnref n="10" /> is defined as a sum of two

<footnote n="10">¹⁰Cost function, payoff function and utility function are three names that represent the same entity, the utility function, as explained in the beginning of the section 2.3.</footnote>
terms, one involving the state of the robot and another accounting for the interaction with other agents (notably if there is a collision predicted or how close a human pass another). Contrary to the last two examples, where the utility function to be optimized was the difference in position of two racing drivers in reference to how ahead one is from the other, the utility function here is based more on ordinal preferences.

One simple situation where interaction between agents is vital to achieve an acceptable behavior is the lane change maneuver. Usually the AV has to "negotiate" with a surrounding vehicle(s) to insert itself into another lane. Vehicle to vehicle communications can help a lot in this negotiation, but even in a far future there will be manual vehicles in highways. Therefore, in (Meng et al., 2016) a method to evaluate if a change of lane can be executed consists basically in a Nash equilibrium calculation, where the actions for the AV are to change or not the lane, and to the other vehicle are to decelerate or accelerate. The payoffs for the AV are the difference between the maximal cruise velocity in two situations: if it continues in the current lane (which is the initial one) and if some safety gap is respected during the lane change operation; otherwise the payoff if defined as a cost. For the other vehicle the payoffs are defined as the inverse of the acceleration (or the absolute value of deceleration), also if the security criteria is respected.

The lane change use-case is also explored in (Ding et al., 2018) but now using a learning approach. The maneuver is considered to be composed by two moments, first when one vehicle adjust its state to allow an other vehicle to merge, and second when the merging maneuver happens. Two possible controllers for the operation ae examined; the first one, called asynchronous, controls the vehicles with a controller trained using a deep Q-learning algorithm that acts as a single agent, hence it does not take into account the behavior of other vehicles. The second controller, called synchronous, is implemented using a Markov game<fnref n="11" /> to account the interaction between both users. The reward function in this case has a cost term connected with the occurrence of a collision, and every Markov game with a stationary policy has at least one Nash equilibrium. It is observed that the first scheme fails constantly, while the second is successful after a reasonable amount of training episodes.

Interaction between the AV and a human driver is usually treated using an open-loop information structure, as was in (Spica et al., 2020) for example. The approach taken in (Fisac et al., 2019) is to consider a fully coupled interaction model, with two levels: a strategic one where interactions are treated integrally and dynamics in a simplified way; and a tactical level, which uses the opposite arrangement, since it operates in short time periods. The result of the strategic level (and the value functions calculated) is used as the best outcome for the tactical level, that takes such information in considerations in its planning, solving a high-fidelity model of each vehicle with a receding horizon approach. A Stackelberg game is used to model the game in the high-level layer, with the AV as the leader.

It is well known that human drivers make decisions based on experience and emotions,

<footnote n="11">¹¹Also called stochastic game, is a game defined as a Makov system, with the payoff function equal to the value function.</footnote>
while most of the proposed methods for implementations in AVs are based on procedural analysis
of the environment and prediction of the other assuming that their behavior can be approximated
by another procedural representation. The work done in (Ji and Levinson, 2020) tries to estimate
the behavior difference between the real decision taken during a discretionary lane change
situation and one that is taken using a game theoretic approach with payoff function defined by
safety and time-saving terms with adjusted parameters using real data collected by the NHTSA.
The result of simulations with different initial gaps and initial velocities are that greater initial
distances allow the vehicles to pursue more selfish non-cooperative behaviors, while high-velocity
allows a fast maneuver but worsens the total payoff since also extends the period in which a
dangerous choice can be made by one of the drivers.
## 2.5 Conclusion

As it was seen in the section about decision-making methods for the automated vehicle, two main approaches dominate the domain: Markov-based application or learning methods. The method proposed here is based on the first approach, with a key simplification to avoid considering the changes in other road users' behavior into the decision process. Without such simplification it would be necessary to consider a complex model to calculate the transition probability, as it is done in (Brechtel et al., 2014) for example, and adopt a sampling-based solving algorithm, a common resolution method in many MDP and POMDP applications (Ulbrich and Maurer, 2013), (Hubmann et al., 2018), (Wei et al., 2011). The proposed decision-making is designed to work in any type of environment, urban or in highways, and it was tested in an urban scenario.

The literature about ethical decision-making is rich on thought experiments but less numerous on real applications. Most works deal with logic rules of some sort, but there are examples using other approaches such as trajectory control (Thornton et al., 2017) or collision severity analysis Pickering et al., 2019. The methods proposed in this thesis to deliberate under ethically sensitive situations are based on consequentialist ethics and are specific to situations where the ethical consequences need to be accounted for, in opposition to Thornton et al., 2017 that includes by design the ethical component of the decision in situations where it is not necessary. Another difference from the literature is that, during the ethical deliberation uncertainties play a main role, differently to the applications proposed by (Bonnemains et al., 2018) and (Berreby et al., 2015) that relies only in deterministic logical relations for example.

Finally, the last part of the thesis deals with the prediction of other road users' behavior and how they should modify its decision accordingly. An incomplete game is then modeled using the behavior probabilities for the other road users, applying the Harsanyi's transformation to enable a resolution via Nash equilibrium. Two main differences from the standard application of game theory in the current literature can be pointed out: it is used to make the AV's decision more robust, given the max-min nature of the Nash equilibrium itself and the influence of the uncertainties into the final deliberation; this last one is rarely seen in game-theoretic applications ((Meng et al., 2016), for example). The approach, as was used here, is similar to (Turnwald et al., 2016) in that he models the interaction between multiple agents in a higher symbolic level, but the proposition will go beyond since it also accounts for uncertainties; although such use is second to the most popular application: to model and exploit agent interaction in low symbolic level, as for example in the control component of agents (Wang et al., 2019), (Notomista et al., 2020).

Each symbolic option of the game is represented by behavior profiles, modeled using CV (constant velocity) or CA (constant acceleration) policies for pedestrians or vehicles. This method represents a typical physical-based approach application to behavior prediction, given that the prediction happens in the dynamic level and that the interval range considered for the implementation is a small one (Rudenko et al., 2020). A similarity analysis is then executed based on the expected behavior given the assumed profile, that generates a prediction at each
iteration using a Kalman filter, and the observation of the environment evolution, typical of pattern-based approaches such as (Houenou et al., 2013). The behavior probabilities calculated with this approach are used by the game model to deliberation on the best strategy.
# Chapter 3

# MDP for decision making

## Contents

<table><tr><td>3.1</td><td>Theoretical background</td><td>47</td></tr><tr><td>3.1.1</td><td>AV's Architecture</td><td>48</td></tr><tr><td>3.1.2</td><td>Markov Decision Process</td><td>50</td></tr><tr><td>3.2</td><td>AV decision-making model</td><td>55</td></tr><tr><td>3.2.1</td><td>State and action sets</td><td>55</td></tr><tr><td>3.2.2</td><td>Transition function</td><td>57</td></tr><tr><td>3.2.3</td><td>Reward function</td><td>59</td></tr><tr><td>3.3</td><td>Results and discussion</td><td>66</td></tr><tr><td>3.3.1</td><td>Value iteration</td><td>66</td></tr><tr><td>3.3.2</td><td>Simulation</td><td>68</td></tr><tr><td>3.3.3</td><td>MDP policy results</td><td>70</td></tr><tr><td>3.4</td><td>Conclusion</td><td>74</td></tr></table>

## 3.1 Theoretical background

This chapter starts with a discussion on the architecture most commonly used for AVs, considering the reactive and hierarchical paradigms approaches presented in chapter 1, which is followed by the theoretic definition of a Markov Decision Processes (MDP), from its components to the conditions of uniqueness and existence for the policy calculation. Section 3.2 details the specification of the MDP formulation used in de Moura et al., 2020 and the results obtained in simulation, together with the value iteration procedure used to calculate the resulting policy are discussed in section 3.3.
### 3.1.1 AV's Architecture

Before talking about the MDP implementation for an AV decision-making, it is necessary to discuss the architecture used in automated vehicles, which appear after the subsumption architecture, cited in chapter 1, reached its "capacity ceiling". After implementing an airplane controller using a subsumption architecture, Hartley and Pipitone, 1991 noted that one flaw in such organization is the lack of modularity, since each behavior layer interferes with the one below only in terms of suppressing it or allowing it to change the output of the controller. This means that complexity scales fast according to the number of layers and changes in one layer needs to be met with changes in all superior layers.

Since the beginnings of the reactive approach other architectures were proposed, similar to the subsumption although having key differences with respect to it. One common point in these architectures was the presence of three layers, one containing no internal state, another containing information about the past and one last with predictions about the future, according to Gat, 1998. Some examples of such organization are the AuRa robot (Arkin, 1990), the task control architecture, notably used in (Simmons et al., 1997) and in many robots designed for NASA (Murphy, 2000) and the 3-tiered (3T) architecture (Gat, 1991). Every single one of these, since there are modified the ideas put forth by subsumption to be more modular and to allow planning, are classified as belonging to the hybrid paradigm (Murphy, 2000).

The three layers mentioned earlier and present in many of the hybrid approach architectures can be divided in (using the nomenclature presented in Gat, 1998):

* **Controller:** It is the layer that communicates with the actuators representing the low-level algorithms. Usually it does not have any internal states, it deals with the execution of some behavior passed from higher layers.

* **Sequencer:** Its role is to choose which behavior the controller must execute, while receiving information about the general planning from the upper layer.

* **Deliberator:** Executes the time consuming strategic planning tasks.

As it can be seen in figure 3.1 the relationship between layers are modified to input and output, differently from the suppression relation employed in the reactive paradigm. This structure is curious because it is outdated by the three levels of control during a driver task, presented in Michon, 1979: strategic level, tactical level and operational level (apparently there are no direct connection between the these works). The highest level deals with the global planning of the mission, the route determination, traffic level evaluation during the mission and possibly the risks involved in the chosen route. The tactical level deals with local constraints, adapting the route to interactions with other road users, while the operational level deals with the execution of the trajectory that possibly was modified by the previous layer. The same organization later appeared in Donges, 1999, with a different nomenclature (navigation, guidance, stabilization)
and is adopted by multiple AV decision-making publications (Ulbrich and Maurer, 2013).

<figure><img src="image_13.png" /><figcaption>Figure 3.1 – Three tiered (3T) architecture</figcaption></figure>

Nowadays the three layers architecture is the dominant one, being the one used in the Stanley vehicle at the DARPA challenge (Thrun et al., 2006) for example, and also in the majority of publications that deal with the decision-making of autonomous vehicles. Hence, the vehicle architecture considered here uses such organization in its planning section, as it is shown in figure 3.2.

<figure><img src="image_14.png" /><figcaption>Figure 3.2 – AV architecture adopted</figcaption></figure>

The perception node involves all communication, localization and mapping procedures together with sensor data acquisition. It can receive information from the operational layer and the tactical layer (data from the strategic layer may come using the tactical link since the latter is expected to function at a higher frequency than the former; the same is valid with the controller data and the operational layer link to perception). The plan step is formed by the three layers discussed earlier, with the strategic layer calculating the global route, the tactical adjusting this route to local constraints and the operational one converting the resulting route into a trajectory
for the controller. The proposed architecture works according to the hybrid approach, since the
sense plan act structure is respected, but the tactical and operational layers are not limited by the
strategy layer in their capacity to react to external stimuli.

The discussion in the next sections and next chapters will focus mostly in the tactical layer, considering the operational layer and the controller component only to explain how the implementation was done to allow the simulation of the entire system. An *a priori* route will be considered as given, and the perception component will be short-circuited by the simulation supervisor that can detect the configuration of every agent at any time.

**3.1.2 Markov Decision Process**

***About the MDP choice***

As it can be seen in the chapter 2, specifically in the section that presents the state of the
art for decision-making, two main types of algorithms are used to give a robot, or in our case
a vehicle, the capacity to function without supervision and in a flexible way, so as to deal with
uncertainties and variations of environment parameters that are common in dynamic scenarios.
One is the Markov-based algorithms and another is the deep learning (DL) based methods. Both
have advantages and inconveniences, but one of them cannot, at least not currently, does not have
some essential properties to be used as a decision-making model for AVs.

To model the deliberation process, in normal and ethical situations, a Markov decision
process will be proposed in the rest of this chapter. This was done because this method offers a
well defined theoretic framework to deal with uncertainty into action selection and also because it
has tree main characteristics that deep learning does not have (Barredo Arrieta et al., 2020):

* Comprehensability: The ability to represent its learned knowledge in some representation that is understandable by humans.

• Explainability: The ability to explain in human terms why a decision was taken.

* Transparency: If the model is understandable (there are different levels of transparency)$^a$.

Given that every single decision made by an AV needs to be verified and validated, the
three characteristics are essential, because not only one must be able to explain why an AV did
what it did. It is also necessary to be certain concerning the limits of operation and which reactions

<footnote>aThe important point is that deep learning methods are not transparent, the discussion about different levels of transparency is left to Barredo Arrieta et al., 2020</footnote>
might occur in extreme situations, mechanically and ethically to be able to define when dilemma situations might occur or not; for example, for MDP it is possible to verify the convergence of its policy calculation, which theoretically is not possible with DL methods.

And the point of this document is to propose methods of ethical deliberation inspired in ethical theories, it is more coherent to do it in an understandable fashion. Of course, this does not mean that any type of ethical oriented decision-making using deep learning is possible, nor that it should not be researched and implemented, just that considering the points made previously this was not the choice made here.

## MDP definition

A Markov decision process (MDP) is a stochastic process that has the Markov property, i.e., that is memoryless and that assigns values, positive or negative, to state transitions, according to the desirability of such transition (Garcia and Rachelson, 2013).

**Definition 1 Markov Property**

Let {$X(t), t \ge 0$} be a stochastic process defined on a measure space $(\Omega, \mathcal{F}, P)$, with $\Omega$ being the sample space, $\mathcal{F}$ being the $\sigma$-algebra of $\Omega$ and $P$ the probability measure on $\mathcal{F}$.
{$X(t), t \ge 0$} is a Markov process if:

$$P(X(t_{n+1} \in \mathcal{F}) | X(t_n), \dots, X(t_0)) = P(X(t_{n+1} \in \mathcal{F}) | X(t_n)) \quad (3.1)$$

The 5-tuple $(S, A, T, R, \gamma)$ defines an MDP. What each component represents is detailed below:

### Components of an MDP

* State space ($s_i \in S$): represents all possible process configurations.

* Action set ($a_i \in A$): represents the set of all possible actions available; triggers the transition from one state to another.

* Transition probability (T): represents the probability whether, given a state, executing an action takes the process to some state; formulated as $p(s_{t+1}|s_t, a_t)$.

* Reward function (R): quantifies how good or bad the transition to another state was according to a defined criteria.

* Discount constant ($\gamma$): represents the factor used to adjust the utility at a time $t+n, n \in [0, \infty]$ to the present (time $t$); defined as $\gamma \in [0, 1]$.
What makes an MDP a rather popular method to model stochastic processes is the ability to expand on the capacities from a usual Markov chain and add uncertainty into the transition between states. Figure 3.3 illustrates an MDP with three possible states and two actions. From the state $s_0$, if the action $a_0$ is executed, there is a probability of $p_{t_n}(s_1 | s_0, a_0)$ that the process at $t_{n+1}$ will be at the state $s_1$ and $p_{t_n}(s_2 | s_0, a_0)$ that it will instead be in $s_2$, with $p_{t_n}(s_2 | s_0, a_0) + p_{t_n}(s_1 | s_0, a_0) = 1$.

The reward depends on the current state, the chosen action and the final state. If, from $s_0$, the action $a_0$ is chosen and the process ends up in state $s_2$ the reward would be $r_{t_n}(s_0, a_0, s_2)$. The expected reward from state $s_0$ and action $a_0$ can be calculated as $r_{t_n}(s_0, a_0) = \sum_{i \in S'(s_0)} p_{t_n}(i | s_0, a_0) \cdot r_{t_n}(s_0, a_0, i)$, with $S'(s_0)$ being the set of possible next states from $s_0$.

<figure><img src="image_15.png" /><figcaption>Figure 3.3 – Simplified example of an MDP</figcaption></figure>

The output of an MDP is a policy, a data structure that encloses multiple decision rules, one for each time epoch. Each one of these decision rules give, for each state, the optimal action to be executed according to the transition probabilities and the reward function chosen (Puterman, 1994c). A policy usually is represented by the greek letter $\pi$. The decision rules can be Markov-based (the input is the current state) or history-based (the input is a series of past states and actions) and they can also be deterministic (one input gives one action) or stochastic (one input gives a distribution of possible actions). Equation 3.2 shows a policy based in Markov-deterministic decision rules.

$$ \pi = (d_t(s_t), d_{t+1}(s_{t+1}), \dots, d_{N-1}(s_{t+1})) \qquad (3.2) $$

There are multiple criteria to select which action should be executed at each state to transfer the process to another state, supposedly closer to the objective. The criteria that will be used for the rest of this document is the discounted reward criteria, which uses a discount
factor to scale down the influence of future rewards into the current decision. This constant also allows the convergence of the value function in infinite horizon MDPs. Solving an MDP means obtaining a policy that has the best reward throughout the entire execution, based on the current transition and all the future transitions that the process might choose. Equation 3.3 defines the value function, that evaluates the total amount of reward that a policy produces, and equations 3.4 show how to calculate the optimal policy can be determined.

$$V^{\pi}(s_t) = E \left[ \sum_{t=0}^{\infty} \gamma^t r_t(s_t, a_t) \mid s_0 \right] \qquad (3.3)$$

$$\left\{ \begin{array}{l} V^*(s_t) = \max_{a \in A} E \left[ \sum_{t=0}^{\infty} \gamma^t r_t(s_t, a_t) \mid s_0 \right] \\ \pi^* \in \argmax_{\pi \in \Pi^{HS}} V^\pi(s_t) \end{array} \right. \qquad (3.4)$$

The calculated optimal policy in 3.4 was considered to be the most general possible, having the history-based stochastic type (HS). However, Markov-based deterministic policies are easier to calculate. The proposition 1 shows that for each history-based stochastic policy there exist a Markov-based stochastic (MS) one with equal value function<fnref n="1" />, hence allowing the consideration of a Markov-based stochastic policy as a solution.

**Proposition 1** *Equivalence of history and Markov based policies:*

Let $\pi \in \Pi^{HS}$ be a stochastic history-based policy; for each initial state there exists a Markov-based stochastic policy $\pi' \in \Pi^{MS}$ such that:

$$V_{\gamma}^{\pi'}(s) = V_{\gamma}^{\pi}(s) \qquad (3.5)$$

To further verify that the optimal policy can be obtained using a deterministic policy, first the optimal equation needs to be determined. An infinite horizon will be considered, since the simplification for finite horizon can be easily done. The following simplification assumptions will be adopted:

### MDP Optimality Assumptions

* Rewards and transition probabilities are stationary: they do not vary according to time.

* Rewards are bounded: $|r(s,a)| \le M < \infty$.

* The state space is discrete.

<footnote n="1">¹The proof of this proposition can be found in Garcia and Rachelson, 2013 or Puterman, 1994b.</footnote>
Since rewards and transition probabilities are stationary through time, then the policy itself can be considered stationary, i.e. being composed by only one decision rule, $\pi = (d(s_t), d(s_{t+1}), ..., d(s_{t+1}))$. All these assumptions are valid regarding the implementation discussed in this and the next chapters. Then, the optimal value equation for infinite horizon MDPs is defined by equation 3.6, called *Bellman equation*.

$$V(s) = \max_{a \in A} \left[ r(s, a) + \gamma \sum_{s_j \in S} p(s_j | s, a)V(s_j) \right] \quad (3.6)$$

Transforming equation 3.6 into the vector form the operator L on V can be defined, as shown in equation 3.7, for $\forall \pi \in \Pi^{MS}$.

$$LV = \max_{\pi \in \Pi^{MS}} (r_{\pi} + \gamma P_{\pi} V) \quad (3.7)$$

From it the proposition 2 can be established<fnref n="2" />, stating the equivalence between deterministic and stochastic policies under the previous assumptions. The space $V$ refers to the space of all functions $V: S \to \mathbb{R}$.

**Proposition 2** *Equivalence between stochastic and deterministic policies:*

For all $V \in V$ and $0 \le \gamma \le 1$

$$\max_{\pi \in \Pi^{MD}} (r_{\pi} + \gamma P_{\pi} V) = \max_{\pi \in \Pi^{MS}} (r_{\pi} + \gamma P_{\pi} V) \quad (3.8)$$

Finally, from the stationary equivalent policy, it is only necessary to prove the existence of an optimal policy. For that, the next theorem,¹³ establishes the existence and uniqueness of an optimal solution for the *Bellman equation*, while theorem 2⁴ shows that there is an optimal policy $\pi^*$ connected to such $V^*$.

**Theorem 1** *Existence and uniqueness of Bellman equation solution*

If $V = LV$, for $V \in V$, then $V = V^*$ and is the only optimal solution for the Bellman equation.

<footnote n="2">²Proof found in Puterman, 1994a; the proof of this proposition is done during the proof of theorem 1.</footnote>

<footnote n="3">³The proof of existence can be found in Puterman, 1994a, and of uniqueness in Garcia and Rachelson, 2013.</footnote>

<footnote n="4">⁴Proof found in Garcia and Rachelson, 2013.</footnote>
**Theorem 2** Existence of optimal policy

For $\gamma < 1$:

* $\pi^* \in \Pi^{MS}$ is an optimal policy $\Leftrightarrow V^{\pi^*}$ is a solution of $V = LV$ and $V^{\pi^*} = V^*$

* Any stationary policy $\pi^* \in \operatorname{argmax}_{\pi \in \Pi^{HA}} r_{\pi} + \gamma P_{\pi} V^*$ is an optimal policy.

Then, under the conditions assumed earlier, an MDP has a unique optimal value solution and an optimal policy connected to it. How to determine such policy will be discussed in subsection 3.3.1.

## 3.2 AV decision-making model

In this section the physical model of the AV will be detailed, together with the definition of the state set and action set (subsection 3.2.1), the transition probability function (subsection 3.2.2) and the reward function (subsection 3.2.3).

### 3.2.1 State and action sets

#### State Set

Unlike many MDP (or POMDP) implementations that consider the state as the descriptor of the environment including other road users' configuration together with the AV's configuration as the state, the definition used here only includes the AV configuration, as seen in 3.9. All other road users are considered through their interaction with the AV in the reward function. The state is composed by the AV's middle rear-axis point coordinates $(x, y)$, direction $\theta$, scalar velocity $v$ and steering angle $\phi$.

$$s_t = [x_t, y_t, \theta_t, v_t, \phi_t] \qquad (3.9)$$

For the AV's model, a non-holonomic single-track vehicle model without slippage was chosen, as it can be seen in figure 3.4. The correspondent model, using front-wheel driving, is given by equation 3.10.
<figure><img src="image_16.png" /><figcaption>Figure 3.4 – AV’s kinematic model</figcaption></figure>

$$
\left\{
\begin{aligned}
\dot{x}_{t+1} &= v_t \cos \theta_t \cos \phi_t \\
\dot{y}_{t+1} &= v_t \sin \theta_t \cos \phi_t \\
\dot{\theta}_{t+1} &= \frac{v_t}{l} \sin \phi_t \\
\dot{v}_{t+1} &= a_{t,1} \\
\dot{\phi}_{t+1} &= a_{t,2}
\end{aligned}
\right.
\qquad (3.10)
$$

Action set

Both acceleration and steering angle rate of change are defined as discrete actions for the MDP (3.11). The action set is then defined as the set of pairings considering the possible values for $\dot{v}$ and $\dot{\phi}$ (values are presented in table 3.1).

$$
a_t = (\dot{v}_t, \dot{\phi}_t) \tag{3.11}
$$

State space discovery

Using this finite number of actions, the state space can be determined expanding the
initial state during *N* transitions using the vehicle model given by 3.10 and each action. Each
transition is defined to last *Δt<sub>trans</sub>*. Such expansion is clearly exponential, requiring a limited
number of transitions to form the state space for the problem. All actions were used at each state
to generate possible next states. Considering *N*<sub>a</sub> as the number of possible actions (i.e. size of *A*),
equation 3.12 gives the total number of states. The state space discovery produces a tree of states,
with each level corresponding to a specific time epoch and the leafs being the terminal states.

$$N_s = \sum_{i=0}^{N} N_a^i \qquad (3.12)$$

During the propagation of states, each one is checked if it remains in the bounds of the environment being simulated. If it is outside, then for this specific state the action chosen is not used and the state is removed from the tree. Another criteria to eliminate possible states is the mechanical limit for the steering angle of the AV. It the current state already achieve the maximum angle, then all actions that increase this angle are discarded. The same is valid for null or negative velocities coupled with actions with negative acceleration, since velocities smaller than zero are not considered in this implementation.

Figure 3.5 depicts an example of how the state space discovery is done for an hypothetical MDP with 2 transition and 3 possible actions. Stating from $s_0$, the states $s_4$, $s_5$, $s_6$ and the ones that remain to be discovered from $s_1$ and $s_2$ are the terminal states of this process.

<figure><img src="image_17.png" /><figcaption>Figure 3.5 – Example of state space discovery</figcaption></figure>

All constants that concern the state space discovery used in the implementation discussed here are displayed in table 3.1.

### 3.2.2 Transition function

The main source of uncertainty in planning for AVs comes from other road users' behavior estimation. Since this knowledge is considered to be known during the planning (hence it is also why the state is defined entirely by the AV's configuration) the only source of uncertainty
<table><caption>Table 3.1 – Parameters used in the state space discovery</caption><thead><tr><th>Parameter</th><th>Possible values</th></tr></thead><tbody><tr><td>v&#x0307;(m/s<sup>2</sup>)</td><td>-1, 0, 1</td></tr><tr><td>&phi;&#x0307;(&deg;/s)</td><td>-40, -20, 0, 20, 40</td></tr><tr><td>&Delta;t<sub>trans</sub>(s)</td><td>0.5</td></tr><tr><td>N (number of transitions)</td><td>4</td></tr><tr><td>N<sub>a</sub> (number of actions)</td><td>15</td></tr></tbody></table>

becomes the imprecision due to the vehicle model considered. The transition probability was defined using the steering angle rate of change, i.e. there are no uncertainty concerning changes in velocity.

In each set of actions with equal acceleration, the chosen action will have a probability of 0.8 of being successful, meaning that for state $s_0$, in figure 3.6, the action $a_3$ takes AV to $s_4$ with probability of 0.8 and to $s_3$ or $s_5$ with probability of 0.1 each. For example, if $a_3 = (-20, -1)$, there is an 0.8 probability that the next state will be the correct one, given the model equations and the current state, 0.1 probability that the process ends up in the next state from $(-40, -1)$ and 0.1 that it will arrive in the state from $(0, -1)$. In cases when only one neighbor exists, notably when the steering angle is at its mechanical limit, then the transition probabilities become 0.9/0.1 (action $a_0$).

<figure><img src="image_18.png" /><figcaption>Figure 3.6 – State transition uncertainty for $a_0$ and $a_3$</figcaption></figure>

The choice of parameters for the transition probability was made arbitrarily. A possible tire slippage, that is not modeled by the single track model presented in figure 3.4, is represented by the incertitude in the AV's steering angle rate of change with values (0.1 and 0.8) inspired by MDP grid-like applications that are frequently used as an example of Markov processes. Such definition is enough to display the entire AV's behavior but it is without saying that for a real application some form to calculate this probability, including the uncertainty of the other road users' behavior, is necessary (and it will be presented in chapter 5).
### 3.2.3 Reward function

The reward function indicates to the system which actions are preferable in regards to achieve a certain goal. It is based on two parameters: performance ($s_{perf}$) and action consequences ($s_{conseq}$), as given by equation 3.13.

$$R(s_t, a_t, s_{t+1}) = s_{perf} + s_{conseq} \qquad (3.13)$$

#### Performance term

Performance for the vehicle is measured as lateral distance to the strategic path, direction offset and time to arrival at goal point. Equation 3.14 calculates the reward using three variables: $q_{lat}$ represents the lateral distance to the trajectory, $\Delta\theta$ is the offset angle between the direction of the AV and the trajectory and $q_{eta}$ represents the approximated time of arrival (ETA).

$$s_{perf} = w_{lat} \cdot q_{lat} + w_{dir} \cdot \Delta\theta + w_{eta} \cdot q_{eta} \qquad (3.14)$$

Both variables $q_{lat}$ and $q_{eta}$ are actually offsets from the real lateral distance ($d_{lat}$) and the approximated time to arrival ($t_{eta}$), as equations 3.15 and 3.16 show. For the lateral distance, since the ideal is that $d_{lat} = 0$, the constant $r_{lat}$ sets the reward of this ideal situation. The same idea is applied with $r_{eta}$, where it represents the maximum allowed ETA before $q_{eta}$ becomes a cost (both $w_{lat}$ and $w_{eta}$ are positive).

$$q_{lat} = r_{lat} - d_{lat} \qquad (3.15)$$

$$q_{eta} = t_{eta} - r_{eta} \qquad (3.16)$$

This approximated ETA is calculated using the projection of the AV's velocity onto the direction of the distance between the front axis middle point ($p_{fr}^{av}$) and the trajectory goal (equation 3.17). More details about how this projection is done will be presented by equation 3.21. It is an hypothetical measure, since the vehicle does not necessarily has the same direction than this distance vector, but is enough to capture some idea of how much time it will take to arrive at the goal given the current speed and direction.

$$t_{eta} = \frac{d_{obj}}{v_{av}^{proj}(\hat{d}_{obj})} \qquad (3.17)$$
If the AV has a velocity equal to zero, then equation 3.14 is replaced by a fixed cost $c_{eta}$. The weights $w_{lat}$, $w_{dir}$, $w_{eta}$ together with the constants $r_{lat}$ and $r_{eta}$ are calibrated heuristically, enabling the AV to arrive at its goal following a trajectory given by the strategic layer of the AV. Since the strategic layer is not of concern here, the trajectory comes from the simulation's input and is the same throughout the execution.

<figure><img src="image_19.png" /><figcaption>Figure 3.7 – Performance reward parameters</figcaption></figure>

### Action consequences term

The action consequences score is measured by two parameters, adherence to the traffic code ($s_{traf}$) and proximity to other road users ($s_{prox}$), as equation 3.18 indicates. The values $s_{traf}$ and $s_{prox}$ can assume negative values or 0, with the latter approximately 10 times lower than the former. This difference is necessary since $s_{prox}$ has two functions: evaluate how close the AV is from other road users and detect collisions; if no collisions are detected the term $s_{traf}$ must always prevail in case of traffic code violation. In case of a collision, as said before, the entire reward function (equation 3.13) is replaces by a negative constant costs.

$$s_{conseq} = s_{traf} + \sum_{i=1}^{i<N_{ag}} s_{prox}^{av,ru_i} \qquad (3.18)$$

However, traffic code violations are not considered to be constitutive of a dilemma situation event. If, for example, there is one action that violated the traffic code and all others end up in collisions, then the AV will execute the action that violates traffic code to avoid the accident. The objective of this implementation is to focus in unavoidable collisions, not in the ethical and legal question of a possible trade-off between code violation and possible accidents. A cascade of
*if-elses* emulates some traffic rules into the AV’s decision process by adding the resulting costs. If no infringement is detected, $s_{\text{traf}} = 0$.

If the AV’s velocity surpasses the legal limit, then the cost $c_{\text{vel}}$ is added to $s_{\text{traf}} = 0$, but if the acceleration is negative, then $r_{\text{acc}}$ is also added, to favor actions that decrease the velocity in this context. Five points are considered to analyze a possible AV intrusion in the opposite lane or in the sidewalk: its four corners and the rear axis middle point. If two of these points are in the opposite lane, then $s_{\text{traf}} = s_{\text{traf}} + 2 \cdot c_{\text{oplane}}$ (if it is inside the sidewalk and the opposite lane the cost accumulate).

## Traffic code evaluation

* Velocity above limit: add the cost $c_{\text{vel}}$ to reward.

* AV in opposite lane: add the cost $c_{\text{oplane}}$ to reward for each point in the opposite lane.

* AV in the sidewalk: add the cost $c_{\text{sidewalk}}$ to reward for each point in the sidewalk.

To ascertain if the AV is too close to another road user, a minimal distance frontier is defined in figure 3.8. These security zones are the spaces between the vehicle’s body and the red lines. All positions, orientations and velocities used to evaluate these parameters correspond to the time epoch *t*, the same as the current state (unless it is said otherwise). These frontiers represent an implicit risk measure for the reward function, since their role is to verify if breaking while maintaining the same direction is still a valid collision avoidance strategy for this state and action and if it is not, the action’s reward is negatively impacted.

<figure><img src="image_20.png" /><figcaption>Figure 3.8 – AV with all the proximity limits</figcaption></figure>

The region around the vehicle are divided in front, left, right and back. The front is defined as the region inside the frontal cone, delimited by the lines formed by the two frontal
rectangle's corners and the frontal axis middle point (blue lines in figure 3.8). The left zone is defined by the two left corners and the frontal axis middle point; the right zone is defined analogously, while the rear zone is defined by the rear cone. The frontier checked depends on with region the closest road user corner is. If it is inside the frontal zone, then the frontier defined by $d_{fr} + d_{br}$ will be used to verify it there is a potential dangerous situation, while it is in one of the lateral zones, $d_l$ is used. No frontier in the rear is defined.

Lateral frontiers are placed at a distance equal to $d_l$ from the AV's body ($d_w$). Equation 3.19 gives the calculation of the $d_l$, with all parameters corresponding to the current time epoch $t$. This variable takes into account the lateral security distance $d_{sec_l}$, that is a static input of the simulation, and the lateral displacement of the other road user during $t$ and $t + 1$, evaluated by $\Delta t_{trans} \cdot \|\vec{v}_{ru}^{proj}(\hat{\theta}_{av}^{\perp})\|$. To calculate this displacement, the velocity of the other road user is projected perpendicularly to the AV's direction (equations 3.20 and 3.21), this last defined by 3.22.

$$d_l = \Delta t_{trans} \cdot \|\vec{v}_{ru}^{proj}(\hat{\theta}_{av}^{\perp})\| + d_{sec_l} \quad (3.19)$$

$$\vec{v}_{ru}^{proj}(\hat{\theta}_{av}^{\perp}) = \vec{v}_{ru} - v_{ru}^{proj}(\hat{\theta}_{av}) \quad (3.20)$$

$$v_{ru}^{proj}(\hat{\theta}_{av}) = \hat{\theta}_{av} \cdot \vec{v}_{ru} \quad (3.21)$$

$$\hat{\theta}_{av} = [\cos(\theta_{av}), \sin(\theta_{av})] \quad (3.22)$$

The frontal limit is given by $d_{fr}$ plus $d_{br}$, the breaking distance given $v_{av}$ (the AV's velocity at $t$) and calculated by equation 3.24. The distance $d_{fr}$, as $d_l$ did, also takes into account the displacement of other road users during $\Delta t_{trans}$, but now using the term $\Delta t_{trans} \cdot v_{ru}^{proj}(\hat{\theta}_{av})$ to do so, with the velocity calculated previously by equation 3.21. The constant $d_{sec_f}$ is the frontal security distance, similar to the previous $d_{sec_l}$, while the deceleration constant $\dot{v}_{break}$ is also a static input of the simulation.

$$d_{fr} = -\Delta t_{trans} \cdot v_{ru}^{proj}(\hat{\theta}_{av}) + d_{sec_f} \quad (3.23)$$

$$d_{br} = \frac{1}{2} \frac{(v_{av})^2}{\dot{v}_{break}} \quad (3.24)$$

It is assumed as an hypothesis that if an emergency breaking happens the AV will continue at the same direction ($\phi_t = 0$), thus no term related to the change in direction is necessary in equations 3.19 and 3.23. The behavior of the other road user in the calculation of these equation is that it will continue in the same direction, with the same velocity.

If a road user is predicted to remain outside the security frontiers, then $s_{prox}^{av,ru_i} = 0$; otherwise the correspondent score becomes a cost, calculated by equation 3.25. To check this
condition the position of the road user at $t+1$ is used. In equation 3.25 there is a static cost, $c_{st}$, to punish the next state due to a frontier violation, a static weight $w_v$, defined heuristically and the difference of velocity variations.

$$s_{\text{prox}}^{\text{av,ru}_i} = c_{st} + w_v \cdot \left[ \left( v_{\text{ru}_{i,t+1}}^{\text{proj}}(\hat{d}_{t+1}) - v_{\text{av}_{t+1}}^{\text{proj}}(\hat{d}_{t+1}) \right) - \left( v_{\text{ru}_{i,t}}^{\text{proj}}(\hat{d}_t) - v_{\text{av}_t}^{\text{proj}}(\hat{d}_t) \right) \right] \quad (3.25)$$

Each of the difference of velocities refers to a time epoch. Defining the distance vector between the AV and the considered road user ($RU_i$) as the vector from the AV's front axis middle point ($p_{fr}^{av}$) to the closest corner of the road user's body, the difference of velocity refers to the projection of each velocity onto this distance versor.

This measure shows if the AV is converging on ($\Delta v$ negative) or diverging from ($\Delta v$ positive) the road user with the proposed action, while the weight $w_v$ (always negative) controls how important it is to avoid a situation where the AV tends to cross other road user's immediate direction while being too close to it. The equation 3.21 is used to calculate the projected velocities, but with the distance versor ($\hat{d}_t$) instead of the AV's direction versor. Figure 3.9 given an example of the evaluation procedure of this velocity variation for $t+1$.

<figure><img src="image_21.png" /><figcaption>Figure 3.9 – Calculation of velocity projections</figcaption></figure>

## Collision detection

To detect collisions during a transition, each road user's position (including the AV) is predicted ten times during a transition period $\Delta t_{trans}$. Each road user (including the AV) is represented by a rectangle (pedestrians are particularly represented by squared), reflecting their real dimensions. This evaluation is done before the verification if the road user is too close to the AV, as it can be seen in the workflow presented by figure 3.10.
<figure><img src="image_22.png" /><figcaption>Figure 3.10 – Workflow for $s_{\text{prox}}$ calculation</figcaption></figure>

In two moments the algorithm checks for collisions involving the AV: at the beginning of the procedure to evaluate $s_{\text{prox}} + = s_{\text{prox}}^{\text{av,ru}_i}$ in equation 3.18, to determine if the AV already collided and if the road user *i* is detected to be inside the safety frontier. In this last case, the collision is checked during the transition. If it is detected, the algorithm stops and sets 3.18 to $c_{\text{col}}$. Two different situations can be labeled as a collision, an intersection with the rectangle that represents the other road user, or if the AV is out of the bounds of the environment being simulated. The limits of the state space are considered to be rectangular walls.

According to Gottschalk et al., 1996, one possible way to verify if two convex 2d-
polygons intersect each other is to search for an axis where the projection of both polygons
do not intersect each other. If this axis exist, then the line perpendicular to such axis separates
both polygons. It is only necessary to check, for each polygon, a set of lines parallel to each
side, since the separation line, if it exists, is parallel to one of the edges of the polygon; hence,
since a rectangle have two parallel sides, only two lines need to be checked, per rectangle. This
theorem is originated from the hyperplane separation theorem, presented in theorem 3 (Boyd and
Vandenberghe, 2004):

**Theorem 3** *hyperplane separation theorem*

Suppose C and D are nonempty disjoint convex sets (C ∩ D); then there exists a ≠ 0 and
b such that a^T x ≤ b for all x ∈ C and a^T x ≥ b for all x ∈ D. The hyperplane {x | a^T x = b}
is called a separating hyperplane for the sets C and D.

Figure 3.11 shows an example of the procedure for the rectangle $V_0V_1V_2V_3$. One of the sides taken as a separating axis, $V_0V_1$, generating the axis $r$, has an intersection between the projection of the square $P_0P_1P_2P_3$ and the projection of the rectangle, which is the edge $V_0V_1$ itself. But the second side chosen as separation axis, $V_0V_3$ (line $l$) does not have an intersection between projections, therefore it is a separation axis (and a line perpendicular to it separates both rectangles).

<figure><img src="image_23.png" /><figcaption>Figure 3.11 – Calculating the separation line</figcaption></figure>

Table 3.2 shows the values of all constants used in the reward calculation. The information
about the parameters for the AV (mass, acceleration, etc.) and for the other road users in the simulation will be given in the next section.

<table><caption>Table 3.2 – MDP parameters used</caption><thead><tr><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th><th>Parameter</th><th>Value</th></tr></thead><tbody><tr><td>w<sub>lat</sub></td><td>60</td><td>w<sub>θ</sub></td><td>-50</td><td>w<sub>eta</sub></td><td>-35</td></tr><tr><td>r<sub>lat</sub></td><td>10</td><td>r<sub>eta</sub></td><td>30</td><td>c<sub>eta</sub></td><td>-1250</td></tr><tr><td>c<sub>vel</sub></td><td>-1000</td><td>r<sub>acc</sub></td><td>750</td><td>c<sub>oplane</sub></td><td>-50</td></tr><tr><td>c<sub>sidewalk</sub></td><td>-1500</td><td>w<sub>v</sub></td><td>30</td><td>d<sub>sec<sub>f</sub></sub></td><td>5m</td></tr><tr><td>d<sub>sec<sub>l</sub></sub></td><td>0.5m</td><td>Δt<sub>trans</sub></td><td>0.5s</td><td>c<sub>st</sub></td><td>-1000</td></tr><tr><td>c<sub>col</sub></td><td>-15000</td><td>γ</td><td>0.9</td><td></td><td></td></tr></tbody></table>

In the proposed implementation the $\gamma$ value was arbitrarily set to 0.9, given that only four transitions are chosen and that the current AV needs to stay aware of future collisions and transgressions. A lower $\gamma$ might dampen the costs given to collisions. As for the other constants, they impact the reward and consequently the behavior of the AV in the following manner:

* The parameters related to the proximity term of the reward ($c_{st}$, $w_v$ and $c_{col}$) should have a highly punitive nature to the vehicle with no possibility of generating a positive reward. The decision if it should be calculated is controlled by the frontier around the AV ($d_{sec_l}$, $d_{sec_f}$).

* The parameters related to traffic code violations ($c_{vel}$, $r_{acc}$, $c_{oplane}$ and $c_{sidewalk}$) have a similar nature but they are always verified.

* The parameters related to the performance have the possibility to produce positive rewards, which are controlled in value by the constants $r_{lat}$ and $r_{eta}$. The cost of not driving is expressed by $c_{eta}$. How important each of the parameters related to lateral distance, direction offset and estimated time of arrival is defined by the three weights $w_{lat}$, $w_{\theta}$, $w_{eta}$, respectively.

## 3.3 Results and discussion

### 3.3.1 Value iteration

The output of a MDP algorithm is a policy $\pi^*$ which, for each state, yields the optimal action to be executed, as discussed in section 3.1. It was already determined that this optimal
policy is Markov-based, deterministic and that it exists. The only remaining piece of the puzzle is a tool to calculate it given an MDP formulation with the assumptions declared before.

$$V^*(s) = \max_{a \in A} \left[ r(s, a) + \gamma \sum_{s_j \in S} p(s_j | s, a)V(s_j) \right] \quad (3.26)$$

Equation 3.26 needs to be solved to obtain the policy. There are many ways to solve a Bellman equation, but the one adopted here will be the value iteration, where in each iteration the value for all states is calculated, until an equilibrium is reached. At this point the value function with the selected actions will be the solution, and the optimal policy can be determined by the actions that produced such values (Garcia and Rachelson, 2013). This algorithm is shown in 1.

At each iteration the mean squared error of the difference between each value calculation for every state is calculated. Such iteration can also be represented using the L operator, as is in equation 3.27. The algorithm is stopped if the calculated error becomes smaller than $\epsilon = 0.5$ (defined heuristically) and the current value iteration is then used by equation 3.28 to obtain the policy.

$$V^{t+1} = LV^t \quad (3.27)$$

Algorithm 1 convergence is verified by theorem 4 in Puterman, 1994a.

**Theorem 4** Optimal solution via value iteration

Let $V \in \mathcal{V}$, $\epsilon > 0$ and let $V^t$ satisfy 3.27 for $n \ge 1$; then:

1. $V^t$ converges in norm to $V^*$

2. The stationary policy defined in equation 3.28 is $\epsilon$-optimal
**Algorithm 1: Value Iteration**

**Data:** Spaces S and A, functions R and P, constant γ, environment data e

**Result:** Policy π*(s), Optimal Value V*(s)

1 t = 0

2 **do**

3 **for** every $s_i \in S$ **do**

4 $V^{t+1}(s_i) = \max_{a \in A} [R(s_i, a, s', e) + \gamma \cdot \sum_{j'} P(s'_{j'}|s_i, a)V^t(s'_{j'})]$

5 $t = t + 1$

6 **end**

7 while $MSE(V^{t+1} - V^t) > \epsilon$

8 **for** every $s_i \in S$ **do**

9

$$ \pi^*(s_i) = \underset{a \in A}{\operatorname{argmax}} V^t(s_i) \qquad (3.28) $$

10 **end**

### 3.3.2 Simulation

#### Configuration

Using the WeBots simulator (Michel, 2004), the aforementioned algorithm was tested in the scenario shown by figure 3.12. A real depiction of the simulation environment is shown in figure 3.13. While the AV is traveling in its lane, two pedestrians, P1 and P2 suddenly cross into the street (both start moving at $t_{simul} = 4s$). Every behavior from other road users are considered to be known; for example, the other vehicle's behavior is assumed to be the will to cruise the entirety of the straight road with 10m/s. For the two pedestrians, before they start moving the AV consider that they will remain stopped. When they start moving, then the AV assumes that they will cross the road.

All MDP parameters and the physical information of road users' are shown in table 3.3.

#### Vehicle control

The obtained policy is used as a one shot fashion. Since the state space has a tree structure, from the current state to all other possible ones, with a fixed number of layers (which is equal to four in this implementation), the policy has the same structure, with an action for each state. Hence, starting from the root, one can determine the sequence of action that should be executed.
<figure><img src="image_24.png" /><figcaption>Figure 3.12 – Initial simulation setup (other road users’ configuration is represented by (x,y,θ,v), not in scale)</figcaption></figure>

<figure><img src="image_25.png" /><figcaption>Figure 3.13 – Simulation environment</figcaption></figure>

It is this sequence of actions that is used to command the AV.

Every action sequence originated from a policy is used during one second, considering that the four transitions can plan the trajectory for two seconds. After this period the MDP is re-initiated, with a different state space, given that the position of the AV changed, and a new policy originates another trajectory. The reason why this two transition buffer is necessary will be made clear in the next chapter, but it can be said that the AV, at the end of the policy execution,
<table><caption>Table 3.3 – Road users’ physical properties</caption><thead><tr><th></th><th>AV</th><th>Pedestrian</th><th>Vehicle</th></tr></thead><tbody><tr><td>Mass (kg)</td><td>2105 + 80</td><td>80</td><td>1065 + 80</td></tr><tr><td>Width, Height (m)</td><td>4.853, 1.65</td><td>0.625, 0.625</td><td>3.475, 1.310</td></tr><tr><td>Wheelbase (m)</td><td>2.933</td><td>—</td><td>2.55</td></tr><tr><td>Acceleration (m/s<sup>2</sup>)</td><td>1</td><td>—</td><td>1</td></tr><tr><td>Deceleration (m/s<sup>2</sup>)</td><td>-7</td><td>—</td><td>-7</td></tr><tr><td>Steering angle limits (°)</td><td>25</td><td>—</td><td>25</td></tr></tbody></table>

should be able to known that no collision is predicted before the policy recalculation. Such justification accounts for the need to keep one transition as buffer. As it will be explained in subsection 4, two actually need to be kept.

Inside the simulation the velocity of car-like objects are controlled by a cruising control, meaning that they decelerate and accelerate using a constant acceleration value. The steering angle has a clear mechanical limit, as has its rate of change. For the pedestrians, a constant velocity is used in its displacement, with the body’s articulation movements being controlled by the simulator’s controller.

### 3.3.3 MDP policy results

The AV should not produce accidents or critical situations on its own. Varying the initial position of the vehicle ($x_{veh}$) and the velocity direction of one of the pedestrians ($\theta_{ped}$) relative to figure 3.12, different AV behaviors can be observed, for this precise road configuration. Each policy predicts two seconds ahead, with one second used for control $((\dot{v}, \dot{\phi}))$ are directly fed into the AV), before the policy being recalculated.

The AV needs at least two transitions to verify if the next action will not cause an accident, and that a state has actions which will not necessarily lead to a dilemma situation. And if it does, this fact needs to be signaled to the entire state space to propagate the high cost connected to a collision to the respective states. It is because of this necessity to look ahead of time that the execution of a policy is limited to $N-2$ ($N$ is given by table 3.1), before the recalculation of the policy. The weights of equations 3.14 and 3.25 were set heuristically to obtain a result representative of the MDP defined in section 3.2.3.

The first of the AV’s behavior plots shown in figure 3.14, for $x_{veh} = 100m$ is acceptable (but not ideal given that it should have stopped and waited the crossing), avoiding the pedestrian and returning to the other lane afterwards. All road user states are considered observable and known, therefore at the beginning of a policy calculation the AV can assert correctly all its states
<figure><img src="image_26.png" /><figcaption>Figure 3.14 – AV’s behavior for $x_{veh} = 100, 80, 40m$</figcaption></figure>

and predict changes throughout the decision horizon. But since the AV only has the capacity to predict two seconds ahead of time, it starts the maneuver without knowing how it will end.

This can be seen more clearly in the second plot, for $x_{veh} = 80$ when after the beginning of the maneuver, it reaches a critical situation and simply collides with the wall beyond the sidewalk (every limit of the environment is defined as a static wall). But if five transitions is used to plan the policy the collision is avoided, as it can be seen in figure 3.15. This is because, according to the Y position graphic at figure 3.16 the vehicle under four transitions do not see clearly the other vehicle approaching and thus places himself ahead of the vehicle in the implementation with five transitions. The moment where collision becomes unavoidable is signaled by point 15, where the orientation for the first case takes a turn to the left, while in the second it turns to the right and accelerates to return to its lane in time.

Adding one mode transition to the policy produces a viable trajectory, but increases the total calculation time from $t = 60.1s$ to $t = 802.4s$, due to the exponential nature of the state space discovery process.

Starting the other vehicle at $x_{veh} = 40m$ (third plot in figure 3.14) creates a situation in which the AV cannot execute the avoidance trajectory. It is perhaps intuitive for a human driver to stop and wait for the pedestrians, but here the AV only reduces its velocity at a certain point and continues to move until the path is clear. Even with five transitions (second plot in figure 3.15)
<figure><img src="image_27.png" /><figcaption>Figure 3.15 – AV’s behavior for $x_{veh} = 80,40$m with 5 transitions</figcaption></figure>

<figure><img src="image_28.png" /><figcaption>Figure 3.16 – AV’s velocity, direction and trajectory for $x_{veh} = 80$m</figcaption></figure>

the behavior is similar, meaning that it needs more transitions to receive the delayed reward from the future and understand that a stop and go behavior is the right one in this context (including in the cases where it can use the opposite lane without ending up in an accident).