Présentation de l’établissement d’accueil
Présentation de l’Université Paul Sabatier - organisme d’accueil 9
The University of Toulouse III - Paul Sabatier, commonly known as Paul Sabatier University (abbreviated as UPS), is a French university located in Toulouse Established in 1969 following the Faure law, it was formed by the merger of the faculties of science and medical faculties from the former University of Toulouse.
Since 2007, Toulouse-III University has been a founding member of the PRES University of Toulouse, specializing in sciences, technologies, health disciplines, and sports, with over 30,000 students currently enrolled It has been ranked as the top French university for employment prospects, according to a study published by the Ministry of Higher Education and Research on December 18, 2013.
Présentation de l’IRIT - lieu de travail
The Institute for Research in Computer Science of Toulouse (IRIT) is one of the largest Mixed Research Units (UMR) in France, playing a crucial role in the research landscape of the Midi-Pyrénées region, supported by a team of 700 members, both permanent and non-permanent.
The laboratory, characterized by its multi-partnerships with CNRS, INPT, and Toulouse universities, plays a pivotal role in the landscape of computer science and its applications in the digital world, both regionally and nationally Through cutting-edge research and a dynamic approach, it has established a distinct identity and gained significant visibility, positioning itself at the heart of local structural developments such as the University of Toulouse and various initiatives stemming from future investments like LABEX CIMI and IRT Saint-Exupéry Furthermore, the laboratory's influence extends internationally, with collaborations including the European laboratory IREP, the French-Spanish Laboratory for Advanced Studies in Information, REpresentation and Processing (LEA CNRS), and partnerships with the Japanese French Laboratory on Informatics (JFLI, UMI CNRS), as well as active cooperation with countries in the Maghreb, the USA, Japan, and Armenia With a presence in all Toulouse universities and IUTs in Tarbes and Castres, the laboratory ensures comprehensive coverage of local territory and a wide range of computer science themes, contributing significantly to the structuring of regional research.
Contexte du sujet
In recent years, agent-based modeling and simulation have gained significant traction, particularly in crisis management, as organizations like ISCRAM seek to enhance the survival of individuals in public spaces threatened by disasters These disasters range from large-scale road accidents to deadly epidemics and chemical catastrophes, as well as various natural disasters Countries such as Vietnam and the Philippines are particularly concerned, as they frequently face climate-related and seismic events, with their economic constraints limiting the implementation of large-scale protective infrastructure, unlike Japan's earthquake-resistant constructions Current agent models are inadequate, failing to effectively understand or explain agent behavior in emergencies Our goal is to enhance these models by integrating concepts from Artificial Intelligence, such as group dynamics, individual and collective actions, social connections, and emotions Preliminary research in collaboration with IFI researchers and students has already yielded some publications However, a key challenge remains in collective decision-making during evacuation processes when a group's safety is at stake.
Research indicates that when individuals have clearly defined institutional roles, such as security personnel or firefighters, groups tend to follow their lead effectively However, in the absence of such roles, groups often spend significantly more time deliberating, which can result in random decision-making.
To make informed decisions during emergencies, it is crucial to understand how agents reason in such situations Although the circumstances may be universally recognized, individual conclusions can vary significantly among agents Argumentation graph-based reasoning models have been proposed to address this issue Various semantics for argument acceptability have been defined, which determine which arguments are deemed acceptable within a given argumentation graph Notably, different semantics can yield differing acceptability outcomes.
Effective tools are available for calculating acceptability across various semantics (http://argumentationcompetition.org/) These tools require an input that encodes the graph and semantics within a specific logic framework The semantics are grounded in different principles, and a systematic coding of these principles and semantics has been proposed in [4].
The internship aims to develop a software tool that takes a combination of principles as input and returns the corresponding coding This coding can then be utilized as input for other tools to calculate acceptability.
New semantics may emerge from combinations of principles that have not yet been considered More broadly, this work will facilitate a tailored definition of the reasoning model for agents The internship will also provide an opportunity to instantiate several argumentative systems focused on dialogues aimed at decision-making within a group during emergency evacuation situations.
Argumentation is a key component of artificial intelligence, crucial for humans to address new challenges, enhance scientific reasoning, express themselves, and share opinions in daily life It involves utilizing arguments to derive conclusions based on their interactions Numerous argumentation theories have been proposed, including Dung's argumentation frameworks, which aim to provide a formal approach to this principle Dung's theory is centered around the concept of an argumentation system that takes a set of arguments (such as an agent's beliefs) and a binary relation expressing a notion of conflict (particularly attack) between arguments, ultimately returning sets of "acceptable" arguments known as extensions This section will introduce the foundational concepts of Dung's argumentation theory.
Système d’argumentation
Définition 1 Les systèmes d’argumentation, aussi appelés graphes d’argumentation à la Dung, sont définis formellement comme un couple composé de :
1 un ensemble d’éléments abstraits appelés arguments, qu’on notera A
2 une relation binaire sur A, appelée relation d’attaque, qu’on notera R
Puisque R est la relation d’attaque, pour deux arguments a, b ∈ A, on dira que l’argument a attaque l’argument b si on a(a, b)∈R
Exemple 1 Le système d’argumentation G = hA,Ri avec A = {a, b, c, d} et R {(b, a),(b, c),(c, d)} est composé de quatre arguments (a, b, c et d) et de trois attaques (b attaque a , b attaque c et c attaque d) :
Figure 2.1 – Le graphe d’argumentation(A,R) de l’Exemple 1
The graph in Figure 2.1 allows for the identification of acceptable arguments In this graph, with (b, c) ∈ Ret(c, d) ∈ R, arguments d and b are accepted, as b is not attacked and d, although attacked by c, becomes acceptable due to b's attack on c Conversely, argument c is rejected The absence of attacks within a set of arguments is a noteworthy property, as it ensures the coherence of that set.
Définition 2 (Sans conflit) Un ensemble S d’arguments est sans conflit s’il n’y a aucun argument a, b∈S tels que (a, b)∈R.
Afin de définir les notions d’acceptabilité et d’admissibilité, il est important de sa- voir quand un ensemble d’arguments (et non plus un unique argument) attaque un argument :
Définition 3 (Ensemble attaquant un argument) Un ensemble d’arguments
S ⊆ A attaque un argument b ∈ A si et seulement si b est attaqué par un des arguments de S:∃a∈S,(a, b)∈R.
A rational agent accepts an argument if it remains unchallenged or if any challenges directed at it can be effectively countered This concept of acceptability is encapsulated in the following definition.
Définition 4 (Acceptable) Un argument a ∈ A est acceptable pour un ensemble d’arguments S si et seulement si pour chaque argument b ∈ A, si (b, a)∈ R, alors b est attaqué par S.
Lorsqu’un argument aest acceptable pour un ensemble S, on dit queS défend a, ou que a est défendu parS.
Définition 5 (Admissible) Un ensemble d’arguments S est admissible si et seule- ment si S est sans conflit et si tout argument a ∈S est acceptable pour S.
En d’autres termes, on peut dire qu’un ensemble d’arguments est admissible si cet ensemble est cohérent et est capable de se défendre lui-même.
Extensions
Extensions préférées
The principle of a preferred extension for an agent is that it accepts all defensible arguments, ensuring that this set of arguments is maximal for inclusion Consequently, a preferred extension is defined as an admissible set that is maximal for inclusion.
Définition 6 (Extensions préférées) S ⊆ A est une extension préférée d’un sys- tème d’argumentation G = hA,Ri si et seulement si S est un ensemble admissible maximal pour l’inclusion.
It is important to note that every argumentation system has at least one preferred extension The collection of preferred extensions for an argumentation system G is denoted as ξ pref (G) In some cases, the only preferred extension of an argumentation system may be the empty set, in which case the system is termed trivial.
Extensions stables
Le principe d’une extension stable pour un agent est le fait qu’elle attaque tous les arguments qu’elle n’a pas acceptés.
Définition 7 (Extensions stables) S ⊆ A est une extension stable d’un système d’argumentation G = hA,Ri si et seulement si S est admissible et attaque tous les arguments qui n’appartiennent pas à S.
L’ensemble des extensions stables pour un système d’argumentationG=hA,Risera noté ξ sta (G).
Extensions complètes
Dung a montré que la notion de point fixe permet de caractériser les extensions complètes Pour cela, il introduit la fonction caractéristique d’un système d’argumen- tation.
Définition 8 (Fonction caractéristique) La fonction caractéristique, notée F G , d’un systốme d’argumentation G = hA,Ri est dộfinie de la faỗon suivante : F G :
To refer to a specific fixed argumentation system, we denote it as F instead of F G By employing the characteristic function, Dung demonstrates that a set of arguments S is admissible if and only if S is a subset of F(S).
Définition 9 (Extension complète) Un ensemble d’arguments admissible S est une extension complète si et seulement si chaque argument, qui est acceptable pour
S, appartient àS Un ensembleS est une extension complète si et seulement si S est sans conflit et S =F(S).
L’ensemble des extensions complètes pour un système d’argumentationG=hA,Ri sera noté ξcomp(G).
The semantic frameworks discussed thus far allow for multiple extensions based on a system of argumentation, leading to the possibility that an argument may be accepted by one extension while rejected by another To address this inconsistency, Dung proposed an alternative semantic approach that assigns a unique status to each argument.
Extensions de base
Dung va ainsi introduire une sémantique qui affine la sémantique complète, en insistant sur un aspect d’incontestabilité dans le choix de l’ensemble d’arguments.
The principle of a foundational extension for an agent involves initially retaining all unchallenged arguments, after which the agent accepts all arguments supported by these retained ones This process continues until no new arguments can be accepted Unlike other types of extensions, there can only be one foundational extension.
Définition 10 (Extension de base) L’extension de base d’un système d’argumen- tation G=hA,Ri est le plus petit point fixe de F G
The set containing the grounded extension of an argumentation system G is denoted as ξgr(G) It is important to note that every argumentation system has at least one grounded extension, which can be the empty set, represented as ξgr(G) = {∅}.
Exemple 2 (Calcul d’extensions) Soit le système d’argumentation G = hA,Ri avecA={a, b, c, d, e, f, g}etR={(a, b),(b, c),(c, d),(d, c),(d, e),(e, f),(f, g),(g, e)}. Déterminons les extensions, pour chaque sémantique, de ce système d’argumentation représenté par la figure 2.2 :
Figure 2.2 – Le système d’argumentationG= (A,R) de l’Exemple 2
Un certain nombre de résultats de complexité ont été établis pour des problèmes de décision dans les systèmes d’argumentation abstrait [5] Deux de ces problèmes sont les suivants :
Vérification VERσ Étant donné une sémantiqueσ, un système d’argumentation
G = (A,R) et un ensemble S ⊆ A, est-ce que l’ensemble S est une σ-extension de
Existence EXσ Étant donné une sémantique σ et un système d’argumentation
G= (A,R), est-ce que le système Ga au moins une σ-extension ?
Codage en logique
Méthode de codage
Maintenant, nous fournissons une méthode pour coder les σ-extensions d’un sys- tème d’argumentation dans une logique donnée, selon l’approche de satisfiabilité in- troduite précédemment.
Au niveau abstrait, étant donné un ensemble d’arguments A ={a 1 , a 2 , } et un graphe d’argumentation G = (A,R), afin de construire θ σ,S , il faut répondre aux questions suivantes :
1 Comment représenter un sous-ensemble S de l’ensemble des arguments A? Par exemple, ce pourrait être : χ S = ^ a i ∈S a i ∧ ^ a j ∈S / ơa j
2 Comment exprimer que S est uneσ-extension de G? Par exemple, si σ est la sémantique stable alors nous pourrions avoir :
1 Dans le cas ó M od(θ σ ) est isomorphe à ξ σ (G) alors la conséquence suivante est : θ σ ` ϕ si et seulement si ϕ code une propriété σ-définissable de G.
S est une extension stable deG ssi χ S |= ^ a∈A
Dans [2], il a été montré que V a∈A(a ↔V b∈A:bRaơb) = θ stable Plus gộnộrale- ment, nous visons la construction de θ σ,S vérifiant l’équivalence suivante : S est une σ-extension de Gssi χ S |=θ σ , c’est-à-dire θ σ,S est satisfiable ssi χ S |=θ σ
3 Lorsqu’une sémantique implique une notion de maximalité ou minimalité, com- ment capturer les ensembles correspondants ?
Les ingrédients
La méthodologie ci-dessus de codages systématiquesθ σ,S óSest le sous-ensemble à tester pour être uneσ-extension repose sur plusieurs briques de construction et une règle comme suit.
Règle Un codage est de la forme θ σ,S def = ϕ S ∧ϕ S ∧Ψ S óΨ S est une combinaison booléenne sur des briques de construction de base (intui- tivement,Ψ S exprime queS vérifie σ).
Briques de construction de base 2 L’appartenance à un sous-ensemble des argu- ments : a est un argument de X ⊆ A est codé comme : ϕa∈X
2 Rappelons qu’une conjonction vide, à savoir, une conjonction V
C(x) γ [x] telle que C(x) n’est vrai pour aucun x, équivaut à > Une disjonction vide, à savoir, une disjonction W
C(x) γ [x] telle queC(x) n’est vrai pour aucun x, équivaut à ⊥. ó pour chaque a ∈ A, nous supposons une formule générique 3 ϕa∈S exprimant que ôa est dans l’ensemble des arguments S ằ.
— Complément de X dans l’ensemble des arguments : ϕ X = ^ a / ∈X ơϕa∈X
Intuitivement, ϕ S exprime que S contient tous les éléments de S, et ϕ S exprime queS ne contient que des éléments de S.
2 X est maximal pour ψ Cela revient à ψ X et ∀Y ⊇X (ψ Y →Y ⊆X) qui est capturé par : ψ X ∧ ^
3 X est minimal pourψ Cela revient à ψ X et ∀Y ⊆ X (ψ Y →X ⊆ Y) qui est capturé par : ψ X ∧ ^
Il faut garder à l’esprit que, comme une conséquence de la première brique de construction, ce qui suit est valide : Dans toutes les clauses ci-dessus, chaque fois que
X 6=S (et de même pourY etZ),ϕ a∈X doit être codé comme W a=x∈X> sinon il est codé comme ϕa∈S.
3 Par formule générique, nous entendons une formule qui est construite d’une manière systéma- tique, contrairement aux formules ponctuelles sans forme commune Par exemple, ϕ a∈S peut être a (à condition que, pour tout argument a, il y a un atome unique du langage) Ceci est générique parce que toutes ces formules ont la même forme : un atome nommant un argument
Comme illustration, voici les détails pour les deux cas de maximalité Ψ S =ψ S ∧ ^
Assuming that set E satisfies the condition ψ (i.e., ψ E is true), it follows that for any subset S of E, the expression θ σ,S defined as ϕ S ∧ ϕ S ∧ Ψ S is not satisfiable This is due to the contradiction arising from the conjunction ϕ S, which conflicts with ψ Y → V a∈A(ϕa∈Y → ϕa∈E) when Y is equal to E For elements a in E\S, it is established that ϕ S implies ơϕa∈S, while ψ E → V a∈A(ϕa∈E → ϕa∈S) confirms ϕa∈S, given that both ψ E and ϕa∈S are true Similarly, if E satisfies ψ (meaning ψ E is true), then for any superset S of E, the expression θ σ,S is also not satisfiable, as for elements a in S\E, ψ S leads to ϕ a∈S, while ψ E holds.
Principes d’encodage des sémantiques
Baroni and Giacomin demonstrated that existing argumentation semantics adhere to several principles They provided an extensive list of these principles, which can be utilized to characterize the existing semantics This section aims to encode these principles into formal expressions based on a general characterization of a given semantics.
Cela nécessite deux choses La première est que nous devons nous préparer, à partir des briques de construction énumérés à la section 2.3.2, au codages d’énoncés (et leurs dénégations) tels que :
— ôa attaque bằ (en symboles, aRb)
— ôS est maximal tel que ằ
— ôS est minimal tel que ằ
L’autre chose est de fournir une liste concrète de ces principes P Nous en rappe- lons ci-dessous quelques-uns issus de la liste dans [7].
Le principe de sans conflit (Conflict-free) Une sémantiqueσ satisfait le prin- cipe de sans conflit si et seulement si ∀G,∀E ∈ξσ(G), E est sans conflit.
Avec les briques de construction de la section2.3.2, le principe de sans conflit peut être codé comme ceci 4 :
Le principe d’inclusion-maximalité (Inclusion-maximality) Une sémantique σ satisfait le principe d’inclusion-maximalité si et seulement si ∀G,∀E ∈ ξ σ (G),
Ici, un codage a été déjà donné explicitement à la section 2.3.2.
Le codage de la notion de dộfense (ô pour tout b tel que bRa, il existe c ∈S tel quecRbằ) est rộalisộ par :
_ cRb ϕ (c∈S) qui peut être utilisé dans le codage des trois principes suivants qui sont basés sur la défense, comme suit.
Le principe d’admissibilité (Admissibility) Une sémantiqueσsatisfait le prin- cipe d’admissibilité si et seulement si ∀G,∀E ∈ ξ σ (G), si a ∈ E, alors a est défendu par E.
Le principle d’admissibilité peut être capturé par : ϕa∈S → ^ bRa
Le principe de réintégration (Reinstatement) Une sémantique σ satisfait le principe de réintégration si et seulement si ∀G,∀E ∈ ξ σ (G), si a est défendu par E, alors a∈E.
By noting that S appears instead of E in the formula specification, we construct a formula parameterized by S, which is satisfiable if and only if S is a σ-extension.
Le principe de réintégration peut être capturé au moyen de :
Le principe de réintégration sans conflit (Conflict-free reinstatement). Une sémantique σ satisfait le principe de réintégration sans conflit si et seulement si
∀G,∀E ∈ξ σ (G), E, sia est défendu par E etE∪ {a} est sans conflit, alors a∈E.
The principle of conflict-free reintegration can be understood as the principle of reintegration, with the addition of the term "conflict-free" in the antecedent This highlights the importance of achieving reintegration without any conflicts.
En plus des principes énumérés dans [7], on peut proposer la suivante :
The principle of complement attack (Complement attack) states that a semantics σ satisfies this principle if and only if for all G and E in ξ σ (G), and for all b in A, if b is not in E, then there exists an a in E such that aRb This principle can be effectively captured through specific formulations.
Codage en logique propositionnelle
In a given semantics σ(A,R), S represents a class of formulas derived from σ(A,R), S by examining a specific argumentation graph (A,R) where S is a subset of A It is essential to unfold σ(A,R), S based on the actual values taken by A, R, and S.
Exemple 3 Pour σ=stable, pour A = {d, e, f} avec {eRf, fRd, fRf} (voir la Fi- gure 2.3), pour le cas S = {d, e} qui est une extension stable, l’instanciation de σ(A,R),S donne la formule satisfiable :
V {ơa | a ∈ A\S} z }| { ơf ó > (resp ⊥) résulte de la conjonction vide V b∈R − (e) ơb (resp la disjonction vide
W b∈R − (e) b) car aucun argument de A n’attaque e.
Figure 2.3 – Le graphe d’argumentation(A,R) de l’Exemple3
In the context of σ(A,R), S, all atomic formulas represent statements of the form "the argument is in the set X," where A is an argument variable and X denotes a subset of A These primitive statements can appear in user-specified semantics Within the σ semantics, these declarations can be combined, negated, and the arguments can be quantified, allowing for maximization of argument sets, among other operations.
Plus important encore, S désigne un ensemble distingué : S dénote le sous- ensemble de A à tester pour être une σ-extension.
Ce chapitre présente le système sesame, développé dans le cadre du stage.
Introduction
A natural semantics is displayed in a text box within the program's interface This formula utilizes English words to create expressions that closely resemble natural language.
Les formules standards sont construites à partir d’opérateurs et d’opérandes On utilise la notation polonaise pour cette construction.
Infix, prefix (also known as Polish), and postfix notations are distinct methods for writing algebraic expressions, characterized by the relative positioning of operators and their operands.
1 Formule-infix-standard : dans la formule-infix-standard, un opérateur est écrit entre ses opérandes en notation infixée. hformulei : := hformulei opérateur-deux-paramètreshformulei
2 Formule-préfix-standard : dans la formule-préfix-standard, un opérateur est écrit avant ses opérandes en notation préfixée. hformulei : := opérateur-deux-paramètreshformulei hformulei
Généralités
Principe de base
Le principe de sesame est que l’utilisateur soumette une expression en langage naturel, expression décrivant une sémantique argumentative qui intéresse l’utilisateur.
Un exemple d’une telle expression est :
For all b