Contents [PDF]

Contents Acknowledgments

v

Abstract

vii

Resumen

ix

Resum

xi

Contents

xvii

List of Figures

xxi

List of Tables

xxii

1 Introduction 1.1 Motivation . . . . . 1.2 Objectives . . . . . . 1.3 Contributions . . . . 1.4 Document Structure

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

2 State of the Art 2.1 Introduction . . . . . . . . . . . . . . . . . 2.2 Approaches to Norms . . . . . . . . . . . 2.2.1 Sociological Approach to Norms . 2.2.2 Philosophical Approach to Norms 2.2.3 Legal Approaches . . . . . . . . . . 2.2.4 Artificial Intelligence & Law . . . . 2.3 Norm Definition in Multi-Agent Systems . 2.3.1 Norm Definition . . . . . . . . . . 2.3.2 Normative Multi-Agent Systems . xiii

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

. . . . . . . . .

. . . .

1 2 5 6 7

. . . . . . . . .

9 9 11 11 13 14 14 15 15 18

2.4

2.5

2.6

2.7

2.8

Norm 2.4.1 2.4.2 2.4.3 2.4.4 2.4.5 2.4.6 2.4.7 2.4.8 Norm 2.5.1 2.5.2 2.5.3 2.5.4

Representation . . . . . . . . . . . . . . . . . . . . . . . . Deontic Logic: Logic of Norms . . . . . . . . . . . . . . Input/Output Logic . . . . . . . . . . . . . . . . . . . . Commitments . . . . . . . . . . . . . . . . . . . . . . . . Social Law . . . . . . . . . . . . . . . . . . . . . . . . . Normative Positions . . . . . . . . . . . . . . . . . . . . Power in Normative Systems . . . . . . . . . . . . . . . Norms and Time Considerations . . . . . . . . . . . . . Open Issues for a Logic of Normative Systems . . . . . . Implementation . . . . . . . . . . . . . . . . . . . . . . . Normative Language . . . . . . . . . . . . . . . . . . . . Operational Norms . . . . . . . . . . . . . . . . . . . . . Implementation Mechanisms . . . . . . . . . . . . . . . Open Issues for Implementing Normative Multi-Agent Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . Norm Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6.1 Norm Decision Making Systems . . . . . . . . . . . . . . 2.6.2 Norm Diagnosis Systems . . . . . . . . . . . . . . . . . . 2.6.3 Open Issues for Normative Reasoning . . . . . . . . . . Norm Creation Process . . . . . . . . . . . . . . . . . . . . . . 2.7.1 Top-Down Approach . . . . . . . . . . . . . . . . . . . . 2.7.2 Bottom-Up Approach: Dynamic Emergence . . . . . . . 2.7.3 Open Issues for the Emergence of Norms . . . . . . . . Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8.1 Specification of Normative Systems . . . . . . . . . . . . 2.8.2 Individual Normative Reasoning . . . . . . . . . . . . . 2.8.3 Implementation of Norms . . . . . . . . . . . . . . . . . 2.8.4 Software Tools for Normative Multi-Agent Systems . . .

3 Normative Definitions 3.1 Introduction . . . . . . . . . . . . . . . . 3.2 Deontic Norms . . . . . . . . . . . . . . 3.2.1 Deontic Norm Definition . . . . . 3.2.2 Deontic Instance Definition . . . 3.3 Constitutive Norms . . . . . . . . . . . . 3.3.1 Constitutive Norm Definition . . 3.3.2 Constitutive Instance Definition 3.4 Conclusions . . . . . . . . . . . . . . . . xiv

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

21 21 25 25 26 27 28 29 29 30 30 32 36 42 42 43 49 51 54 55 57 60 61 62 63 63 64 67 68 70 71 72 72 73 74 75

4 The n-BDI Architecture 4.1 Illustrative Scenario . . . . . . . . . . . . . . . . . 4.2 Normative Multi-context Graded BDI Architecture 4.2.1 Mental Contexts . . . . . . . . . . . . . . . 4.2.2 Functional Contexts . . . . . . . . . . . . . 4.2.3 Normative Contexts . . . . . . . . . . . . . 4.2.4 Reasoning Process in a n-BDI Agent . . . . 4.3 Norm Acquisition Context (NAC) . . . . . . . . . 4.3.1 NAC Language . . . . . . . . . . . . . . . . 4.3.2 Norm Dynamics . . . . . . . . . . . . . . . 4.4 Norm Compliance Context (NCC) . . . . . . . . . 4.4.1 NCC Language . . . . . . . . . . . . . . . . 4.4.2 Instance Dynamics . . . . . . . . . . . . . . 4.5 Acquiring Norms: Evaluation . . . . . . . . . . . . 4.6 Contributions . . . . . . . . . . . . . . . . . . . . . 4.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . 5 Reasoning About Deontic Norms 5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 5.2 Norm-based Expansion for Deontic Norms . . . . . 5.2.1 Obligation Internalization . . . . . . . . . . 5.2.2 Prohibition Internalization . . . . . . . . . 5.2.3 Permission Internalization . . . . . . . . . . 5.3 Determining the Willingness to Norm Compliance 5.3.1 ✓interest . . . . . . . . . . . . . . . . . . . . 5.3.2 ✓expectation . . . . . . . . . . . . . . . . . . . 5.3.3 ✓emotion . . . . . . . . . . . . . . . . . . . . 5.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . 5.4.1 Simulation Description . . . . . . . . . . . . 5.4.2 Results . . . . . . . . . . . . . . . . . . . . 5.4.3 Discussion . . . . . . . . . . . . . . . . . . . 5.5 Contributions . . . . . . . . . . . . . . . . . . . . . 5.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . 6 Reasoning About Constitutive Norms 6.1 Introduction . . . . . . . . . . . . . . . . . . . . 6.2 Norm-based Expansion for Constitutive Norms 6.3 Case Study . . . . . . . . . . . . . . . . . . . . 6.3.1 Initial Situation . . . . . . . . . . . . . . 6.3.2 Normative Reasoning Process . . . . . . xv

. . . . .

. . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . .

77 78 80 81 83 84 85 90 93 95 99 99 101 105 107 111

. . . . . . . . . . . . . . .

113 113 114 115 117 117 118 119 120 122 127 127 132 140 142 143

. . . . .

145 145 147 149 149 149

6.4

6.5 6.6

Evaluation . . . . . . . . . . . 6.4.1 Agent Implementation 6.4.2 Metrics . . . . . . . . 6.4.3 Results . . . . . . . . Contributions . . . . . . . . . Conclusions . . . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

7 Coherence-based Contraction 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.2 Coherence Theory . . . . . . . . . . . . . . . . . . . . . . . . 7.2.1 Deductive Coherence . . . . . . . . . . . . . . . . . . . 7.3 Coherence for Multi-context Graded BDI Agents . . . . . . . 7.3.1 Formalization of Deductive Coherence . . . . . . . . . 7.3.2 Building the Coherence Graph . . . . . . . . . . . . . 7.4 Coherence for n-BDI Agents . . . . . . . . . . . . . . . . . . . 7.4.1 Coherence for the BC: Explanatory Constraints . . . . 7.4.2 Coherence for the NCC: Normative Constraints . . . . 7.4.3 Coherence for the DC: Deliberative Constraints . . . . 7.4.4 Coherence Between Contexts: Normative Bridge Rules 7.4.5 Coherence Maximization . . . . . . . . . . . . . . . . . 7.5 Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.6 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Case Study 8.1 Introduction . . . . . . . . . 8.1.1 Fire-Rescue Scenario 8.2 Non-Normative Fireman . . 8.3 Norm-Constrained Fireman 8.4 n-BDI Fireman . . . . . . . 8.5 Experimental Description . 8.5.1 Metrics . . . . . . . 8.5.2 Experiment Results 8.6 Conclusions . . . . . . . . .

. . . . . . Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 MaNEA: A Distributed Architecture Open MAS 9.1 Introduction . . . . . . . . . . . . . . 9.2 Related Work . . . . . . . . . . . . . 9.2.1 Infrastructural Observability xvi

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . .

152 154 155 156 158 160

. . . . . . . . . . . . . . .

161 161 162 164 165 165 166 167 169 170 171 171 176 176 178 180

. . . . . . . . .

181 181 182 183 183 185 188 188 189 194

for Enforcing Norms in 195 . . . . . . . . . . . . . . . 196 . . . . . . . . . . . . . . . 196 . . . . . . . . . . . . . . . 197

9.3

9.4

9.5

9.6 9.7

9.8 9.9

9.2.2 Requirements for Norm Enforcing Architectures . . . . The Magentix2 Platform . . . . . . . . . . . . . . . . . . . . . . 9.3.1 Tracing Service Support . . . . . . . . . . . . . . . . . . 9.3.2 Organization Management System (OMS) . . . . . . . . Norm-Enforcing Architecture: MaNEA . . . . . . . . . . . . . . 9.4.1 Norm Manager . . . . . . . . . . . . . . . . . . . . . . . 9.4.2 Norm Enforcer . . . . . . . . . . . . . . . . . . . . . . . Implementation of the n-BDI Architecture . . . . . . . . . . . . 9.5.1 Jason . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.5.2 Implementing the n-BDI Architecture in Magentix2 using Jason . . . . . . . . . . . . . . . . . . . . . . . . . . Case Study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9.7.1 Theoretical Results . . . . . . . . . . . . . . . . . . . . . 9.7.2 Experimental Results . . . . . . . . . . . . . . . . . . . Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10 Conclusions 10.1 Contributions . . . . . . . . . . . . 10.2 Future Work . . . . . . . . . . . . 10.3 Related Publications . . . . . . . . 10.3.1 Publications in Journals . . 10.3.2 Publications in Conferences 10.3.3 Book Chapters . . . . . . . Bibliography

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

198 199 201 203 208 208 209 216 216 219 226 228 231 238 245 246 247 247 248 250 250 251 253 280

xvii

xviii

List of Figures 2.1 2.2

Operational interpretation of norms . . . . . . . . . . . . . . . Norm emergence . . . . . . . . . . . . . . . . . . . . . . . . . .

4.1 4.2 4.3 4.4

Perception phase in the n-BDI architecture . . . . . . . . . . . 86 Decision-making phase in the n-BDI architecture. . . . . . . . . 89 Representation of norms and instances in the n-BDI architecture 91 Relative error with respect to the agent accuracy . . . . . . . . 108

Norm-based expansion for deontic norms in the n-BDI architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Desire distribution of a randomly generated agent . . . . . . . 5.3 Explanatory relationship graph . . . . . . . . . . . . . . . . . . 5.4 Percentage of instances that belong to each willingness category on average when compliance takes value 0.1 . . . . . . . . . . . . 5.5 Percentage of instances that belong to each willingness category on average when compliance takes value 0.05 . . . . . . . . . . . 5.6 Percentage of instances that belong to each willingness category on average when compliance takes value 0.2 . . . . . . . . . . . . 5.7 Percentage of instances that belong to each willingness category on average when ⇢N AC 2 [0.0, 0.25] . . . . . . . . . . . . . . . . 5.8 Percentage of instances that belong to each willingness category on average when ⇢N AC 2 [0.25, 0.5] . . . . . . . . . . . . . . . . 5.9 Percentage of instances that belong to each willingness category on average when ⇢N AC 2 [0.5, 0.75] . . . . . . . . . . . . . . . . 5.10 Percentage of instances that belong to each willingness category on average when ⇢N AC 2 [0.75, 0.1] . . . . . . . . . . . . . . . . 5.11 Percentage of instances that belong to each willingness category on average when the number of goals is 10 . . . . . . . . . . . . 5.12 Percentage of instances that belong to each willingness category on average when the number of goals is 50 . . . . . . . . . . . .

37 58

5.1

xix

116 129 130 133 135 135 136 137 137 138 139 139

5.13 Percentage of instances that belong to each willingness category on average when the number of goals is 100 . . . . . . . . . . . 5.14 Percentage of instances that belong to each willingness category on average when the number of explanatory relationships is 10 5.15 Percentage of instances that belong to each willingness category on average when the number of explanatory relationships is 20 5.16 Percentage of instances that belong to each willingness category on average when the number of explanatory relationships is 40 6.1

140 141 141 142

6.2 6.3

Norm-based expansion for constitutive norms in the n-BDI architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 MCC with respect to the internalization threshold . . . . . . . 157 MCC with respect to the observation threshold . . . . . . . . . 157

7.1 7.2

Coherence for normative reasoning . . . . . . . . . . . . . . . . 168 Coherence graph of the case study . . . . . . . . . . . . . . . . 179

8.1

Example of a grid that models a building in flames . . . . . . . 182

9.1 9.2 9.3 9.4 9.5

The Jason reasoning cycle . . . . . . . . . . . . . . . . . . . . . Norm activation . . . . . . . . . . . . . . . . . . . . . . . . . . Observation of behaviours . . . . . . . . . . . . . . . . . . . . . Norm expiration . . . . . . . . . . . . . . . . . . . . . . . . . . Messages exchanged in Cardoso & Oliveira’ approach when one norm is controlled . . . . . . . . . . . . . . . . . . . . . . . . . Messages exchanged in Modgil et al. approach when one norm is controlled . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Messages exchanged in MaNEA when one norm is controlled . Performance of MaNEA, Cardoso & Oliveira and Modgil et al. frameworks with respect to the number of iterations . . . . . . Performance of MaNEA, Cardoso & Oliveira and Modgil et al. frameworks with respect to the number of actions . . . . . . . . Performance of MaNEA, Cardoso & Oliveira and Modgil et al. frameworks with respect to the number of norms . . . . . . . . Performance of MaNEA, Cardoso & Oliveira and Modgil et al. frameworks with respect to the number of instantiations . . . . Performance of MaNEA, Cardoso & Oliveira and Modgil et al. frameworks with respect to the number of agents . . . . . . . . Performance of MaNEA, Cardoso & Oliveira and Modgil et al. frameworks with respect to the number of roles . . . . . . . . .

9.6 9.7 9.8 9.9 9.10 9.11 9.12 9.13

xx

217 227 227 227 232 234 237 240 241 242 243 244 245

List of Tables 2.1 2.2 2.3

Levels in the development of NMAS . . . . . . . . . . . . . . . Comparison among languages for specifying norms . . . . . . . Summary of proposals on norm-autonomous agents . . . . . . .

4.1 4.2 4.3 4.4

Operational rules of the NAC Language . . . . . . . . . . . . Operational rules of the NCC Language . . . . . . . . . . . . Parameters used in the norm recognition experiment . . . . . 95% confidence interval for the relative error made by agents

5.1

Parameters used in the simulations . . . . . . . . . . . . . . . . 128

6.1 6.2

Parameters used in the norm expansion experiment . . . . . . . 153 95% confidence interval for the Sensitivity, the Specificity and the MCC achieved for each type of agent. . . . . . . . . . . . . 158

8.1

95% confidence interval for the victim survival percentage, the fireman survival percentage and the success that each implementation achieves in all the simulations. . . . . . . . . . . . . 95% confidence interval for the victim survival percentage, the fireman survival percentage and the success when riskThreshold and internalizationThreshold vary within the [0, 0.33) interval. . . . . . . . . . . . . . . . . . . . . . . . . . . 95% confidence interval for the victim survival percentage, the fireman survival percentage and the success when riskThreshold and internalizationThreshold vary within the [0.33, 0.66) interval. . . . . . . . . . . . . . . . . . . . . . . . . . 95% confidence interval for the victim survival percentage, the fireman survival percentage and the success when riskThreshold and internalizationThreshold vary within the [0.66, 1] interval. . . . . . . . . . . . . . . . . . . . . . . . . . .

8.2

8.3

8.4

xxi

20 33 53

. 95 . 100 . 106 . 107

190

192

192

193

9.1 9.2

Summary of distributed proposals on infrastructural enforcement200 Parameters used in the experiments . . . . . . . . . . . . . . . 239

xxii