Arrow Research search

Author name cluster

Yannis Dimopoulos

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

AAAI Conference 2024 Conference Paper

Redefining ABA+ Semantics via Abstract Set-to-Set Attacks

  • Yannis Dimopoulos
  • Wolfgang Dvorak
  • Matthias König
  • Anna Rapberger
  • Markus Ulbricht
  • Stefan Woltran

Assumption-based argumentation (ABA) is a powerful defeasible reasoning formalism which is based on the interplay of assumptions, their contraries, and inference rules. ABA with preferences (ABA+) generalizes the basic model by allowing qualitative comparison between assumptions. The integration of preferences however comes with a cost. In ABA+, the evaluation under two central and well-established semantics---grounded and complete semantics---is not guaranteed to yield an outcome. Moreover, while ABA frameworks without preferences allow for a graph-based representation in Dung-style frameworks, an according instantiation for general ABA+ frameworks has not been established so far. In this work, we tackle both issues: First, we develop a novel abstract argumentation formalism based on set-to-set attacks. We show that our so-called Hyper Argumentation Frameworks (HYPAFs) capture ABA+. Second, we propose relaxed variants of complete and grounded semantics for HYPAFs that yield an extension for all frameworks by design, while still faithfully generalizing the established semantics of Dung-style Argumentation Frameworks. We exploit the newly established correspondence between ABA+ and HYPAFs to obtain variants for grounded and complete ABA+ semantics that are guaranteed to yield an outcome. Finally, we discuss basic properties and provide a complexity analysis. Along the way, we settle the computational complexity of several ABA+ semantics.

PDF Details DOI

NMR Workshop 2023 Conference Paper

Sets Attacking Sets in Abstract Argumentation

  • Yannis Dimopoulos
  • Wolfgang Dvorák
  • Matthias König 0002
  • Anna Rapberger
  • Markus Ulbricht 0001
  • Stefan Woltran

In abstract argumentation, arguments jointly attacking single arguments is a well-understood concept, captured by the established notion of SETAFs—argumentation frameworks with collective attacks. In contrast, the idea of sets attacking other sets of arguments has not received much attention so far. In this work, we contribute to the development of set-to-set defeat in formal argumentation. To this end, we introduce so called hyper argumentation frameworks (HYPAFs), a new formalism that extends SETAFs by allowing for set-to-set attacks. We investigate this notion by interpreting these novel attacks in terms of universal, indeterministic, and collective defeat. We will see that universal defeat can be naturally captured by the already existing SETAFs. While this is not the case for indeterministic defeat, we show a close connection to attack-incomplete argumentation frameworks. To formalize our interpretation of collective defeat, we develop novel semantics yielding a natural generalization of attacks between arguments to set-to-set attacks. We investigate fundamental properties and identify several surprising obstacles; for instance, the well-known fundamental lemma is violated, and the grounded extension might not exist. Finally, we investigate the computational complexity of the thereby arising problems.

Details

JAAMAS Journal 2021 Journal Article

Arguing and negotiating using incomplete negotiators profiles

  • Yannis Dimopoulos
  • Jean-Guy Mailly
  • Pavlos Moraitis

Abstract Computational argumentation has taken a predominant place in the modeling of negotiation dialogues over the last years. A competent agent participating in a negotiation process is expected to decide its next move taking into account an, often incomplete, model of its opponent. This work provides a complete computational account of argumentation-based negotiation under incomplete opponent profiles. After the agent identifies its best option, in any state of a negotiation, it looks for suitable arguments that support this option in the theory of its opponent. As the knowledge on the opponent is uncertain, the challenge is to find arguments that, ideally, support the selected option despite the uncertainty. We present a negotiation framework based on these ideas, along with experimental evidence that highlights the advantages of our approach.

Details DOI

AAMAS Conference 2021 Conference Paper

Probabilistic Control Argumentation Frameworks

  • Fabrice Gaignier
  • Yannis Dimopoulos
  • Jean-Guy Mailly
  • Pavlos Moraitis

In this paper we present Probabilistic Control Argumentation Frameworks (PCAFs) that extend classical Control Argumentation Frameworks (CAFs) to take into account probabilistic information in the reasoning process. We show that probabilities can be used to optimally control CAFs that cannot be controlled otherwise. We introduce the notion of controlling power, that represents the probability that a control configuration reaches its target. A computational method based on Monte Carlo simulations for computing the controlling power of control configurations is defined. We experimentally show that PCAFs outperform w. r. t runtime classical CAFs and in a large number of situations they can reach the target with a high probability while the classical CAFs fail.

PDF

AAMAS Conference 2019 Conference Paper

Argumentation-based Negotiation with Incomplete Opponent Profiles

  • Yannis Dimopoulos
  • Jean-Guy Mailly
  • Pavlos Moraitis

Computational argumentation has taken a predominant place in the modeling of negotiation dialogues over the last years. A competent agent participating in a negotiation process is expected to decide its next move taking into account an, often incomplete, model of its opponent. This work provides a complete computational account of argumentation-based negotiation under incomplete opponent profiles. After the agent identifies its best option, in any state of a negotiation, it looks for suitable arguments that support this option in the theory of its opponent. As the knowledge on the opponent is uncertain, the challenge is to find arguments that, ideally, support the selected option despite the uncertainty. We present a negotiation framework based on these ideas, along with experimental evidence that highlights the advantages of our approach.

PDF

AAAI Conference 2018 Conference Paper

Control Argumentation Frameworks

  • Yannis Dimopoulos
  • Jean-Guy Mailly
  • Pavlos Moraitis

Dynamics of argumentation is the family of techniques concerned with the evolution of an argumentation framework (AF), for instance to guarantee that a given set of arguments is accepted. This work proposes Control Argumentation Frameworks (CAFs), a new approach that generalizes existing techniques, namely normal extension enforcement, by accommodating the possibility of uncertainty in dynamic scenarios. A CAF is able to deal with situations where the exact set of arguments is unknown and subject to evolution, and the existence (or direction) of some attacks is also unknown. It can be used by an agent to ensure that a set of arguments is part of one (or every) extension whatever the actual set of arguments and attacks. A QBF encoding of reasoning with CAFs provides a computational mechanism for determining whether and how this goal can be reached. We also provide some results concerning soundness and completeness of the proposed encoding as well as complexity issues.

PDF Details

EUMAS Conference 2016 Conference Paper

Some Theoretical Results on the Relationship Between Argumentation and Coherence Theory

  • Yannis Dimopoulos
  • Pavlos Moraitis
  • Carles Sierra

Abstract This work provides initial results on the relationship between argumentation and Paul Thagard’s coherence theory. We study the relationship, via appropriate transformations, between different types of coherent graphs (according to the values in the arcs) and different argumentation frameworks such as Dung’s abstract argumentation framework, weighted argument systems or preference-based argumentation. The practical interest of our study is to show that coherence theory and argumentation can be mutually useful.

Details DOI

KR Conference 2014 Short Paper

Heuristic Guided Optimization for Propositional Planning

  • Andreas Sideris
  • Yannis Dimopoulos

the new planning system that is described here, shares with PSP the planning as optimization perspective, but it differs in a number of important ways. The first is the incremental goal achievement which, at a high level, works as follows. PSP-H first generates a sub-plan that, starting from the initial state, achieves a subset, of predefined size, of the problem goals. The state that results after the execution of the actions of this sub-plan, becomes the new initial state, and a new sub-plan that satisfies a larger subset of goals is computed. The procedure iterates and links together the subplans that are generated along the way. Therefore, instead of solving the original planning problem, PSP-H solves a series of smaller subproblems. A downside of this greedy approach is that it focuses on maximizing the number of achieved goals in a limited planning horizon, and it ignores completely goals that cannot be achieved within this horizon. In order to overcome the limitations that this would place on the effectiveness of the system, PSP-H is enhanced by a second technique called heuristic guidance, which imposes an additional requirement on the intermediate states that are computed by the PSP-H algorithm. The property that these states need to satisfy is that there must be a relaxed plan from each such state to the final state. PSP-H employs three different relaxation methods that are all based on ignoring some of the problem constraints, but they differ in their strength. The first relaxation method is the well-known delete lists relaxation, whereas the second method ignores all action mutexes. The last relaxation, which is stronger than the first but weaker than the second, ignores action mutexes and uses a subset of the fact mutexes that are heuristically selected. PSP-H is a incomplete and suboptimal planner implemented on top of the PSP system. Our experimental evaluation on a number of domains taken from planning competitions, demonstrates that PSP-H can solve challenging problems, that require long plans. Moreover, a preliminary comparison with Madagascar shows that the new system can solve more problems in some domains, and generate better quality solutions both in term of plan length and number of actions. Some of the techniques employed in PSP-H are similar to those used in other planning systems. For instance, the local optimization method of PSP-H bares some resemblance to the enforced hill-climbing approach of the Planning as Satisfiability is an important approach to Propositional Planning. A serious drawback of the method is its limited scalability, as the instances that arise from large planning problems are often too hard for modern SAT solvers. This work tackles this problem by combining two powerful techniques that aim at decomposing a planning problem into smaller subproblems, so that the satisfiability instances that need to be solved do not grow prohibitively large. The first technique, incremental goal achievement, turns planning into a series of boolean optimization problems, each seeking to maximize the number of goals that are achieved within a limited planning horizon. This is coupled with a second technique, called heuristic guidance, that directs search towards a state which satisfies all goals.

AAMAS Conference 2012 Conference Paper

Knowing Each Other in Argumentation-based Negotiation

  • Elise Bonzon
  • Yannis Dimopoulos
  • Pavlos Moraitis

Argumentation-based negotiation has emerged as an important topic in multi-agent systems over the last years. Although there are many studies of frameworks that enable agents to negotiate through the exchange of arguments, there is a lack of reasoning methods that employ the (usually incomplete) knowledge an agent may have about his opponent. This work addresses this issue by providing a reasoning mechanism that allows negotiating agents to take into account information about their counterparts. Thus an agent may support his own decisions by using arguments that are meaningful for his opponent. Experimental results highlight the impact of the proposed approach in the negotiation process.

PDF

ECAI Conference 2012 Conference Paper

Propositional Planning as Optimization

  • Andreas Sideris
  • Yannis Dimopoulos

Planning as Satisfiability is a most successful approach to optimal propositional planning. Although optimality is highly desirable, for large problems it comes at a high, often prohibitive, computational cost. This paper extends planning as propositional satisfiability to planning as pseudo-boolean optimization. The approach has been implemented in a planner called PseudoSATPLAN, that follows the classic solve and expand method of the SATPLAN algorithm, but at each step it seeks to maximize the number of goals that can be achieved. The utilization of the achieved goals at subsequent steps opens up the possibility of implementing various strategies. The method essentially splits a planning problem into smaller subproblems, and employs various techniques for solving them fast. Although PseudoSATPLAN cannot guarantee the optimality of the generated plans, it aims at computing solutions of good quality. Experimental results show that PseudoSATPLAN can generate parallel plans of high quality for problems that are beyond the reach of the existing implementations of the planning as satisfiability framework.

Details

AAMAS Conference 2010 Conference Paper

Argumentative Alternating Offers

  • Nabila Hadidi
  • Yannis Dimopoulos
  • Pavlos Moraitis

This paper presents an argumentative version of the wellknown alternating offers negotiation protocol. The negotiation mechanism is based on an abstract preference basedargumentation framework where both epistemic and practical arguments are taken into consideration in order to decide about different strategic issues. Such issues are the offerthat is proposed at each round, acceptance or refusal of anoffer, concession or withdrawal from the negotiation. The argumentation framework shows clearly how offers are linkedto practical arguments that support them, as well as howthe latter are influenced by epistemic arguments. Moreoverit illustrates how agents' argumentative theories evolution, due to the exchange of arguments, influences the negotiation outcome. Finally, a generic algorithm that implementsa concession based negotiation strategy is presented.

PDF

ICAPS Conference 2010 Conference Paper

Constraint Propagation in Propositional Planning

  • Andreas Sideris
  • Yannis Dimopoulos

Planning as Satisfiability is a most successful approach to optimal propositional planning. It draws its strength from the efficiency of state-of-the-art propositional satisfiability solvers, combined with the utilization of constraints that are inferred from the problem planning graph. One of the recent improvements of the framework is the addition of long-distance mutual exclusion (londex) constraints that relate facts and actions which refer to different time steps. In this paper we compare different encodings of planning as satisfiability wrt the constraint propagation they achieve in a modern SAT solver. This analysis explains some of the differences observed in the performance of different encodings, and leads to some interesting conclusions. For instance, the Blackbox encoding achieves more propagation than the one of Satplan06, and therefore is a stronger formulation of planning as satisfiability. Moreover, our investigation suggests a new more compact and stronger model for the problem. We prove that in this new formulation many of the londex constraints are redundant in the sense that they do not add anything to the constraint propagation achieved by the model. Experimental results suggest that the theoretical results obtained are practically relevant.

Details

IJCAI Conference 2009 Conference Paper

  • Yannis Dimopoulos
  • Loizos Michael
  • Fani Athienitou

CP-networks have been proposed as a simple and intuitive graphical tool for representing conditional ceteris paribus preference statements over the values of a set of variables. While the problem of reasoning with CP-networks has been receiving some attention, there are very few works that address the problem of learning CP-networks. In this work we investigate the task of learning CPnetworks, given access to a set of pairwise comparisons. We first prove that the learning problem is intractable, even under several simplifying assumptions. We then present an algorithm that, under certain assumptions about the observed pairwise comparisons, identifies a CP-network that entails these comparisons. We finally show that the proposed algorithm is a PAC-learner, and, thus, that the CP-networks it induces accurately predict the user’s preferences on previously unseen situations.

PDF Details

KR Conference 2008 Conference Paper

Making Decisions through Preference-Based Argumentation

  • Leila Amgoud
  • Yannis Dimopoulos
  • Pavlos Moraitis

Decision making is usually based on the comparative evaluation of different alternatives by means of a decision criterion. The whole decision process is compacted into a criterion formula on the basis of which alternatives are compared. It is thus, impossible for an end user to understand why an alternative is good, or better than another. Recently, some decision criteria were articulated in terms of a two-steps argumentation process: i) an inference step in which arguments in favor/against each option are built and evaluated, and ii) a comparison step in which pairs of alternatives are compared on the basis of ``accepted'' arguments. Thus, not only the best alternative is provided to the user but also the reasons justifying this recommendation. % However, a two steps approach is not in accordance with the principle of an argumentation system, whose accepted arguments are intended to support the ``good'' options. Moreover, with such an approach it is difficult to define proof procedures for testing directly whether a given option may be the best one without computing the whole ordering. Finally, it is difficult to analyze how an ordering is revised in light of a new argument. This paper proposes a novel approach for argumentation-based decision making. We propose a Dung style system that takes as input different arguments and a defeat relation among them, and returns as outputs a status for each option, and a total preordering on a set of options. The status is defined on the basis of different inference mechanisms. The total preordering privileges the option that is supported by the strongest argument, provided that this argument survives to the attacks. The properties of the system are investigated.

ECAI Conference 2008 Conference Paper

Theoretical and Computational Properties of Preference-based Argumentation

  • Yannis Dimopoulos
  • Pavlos Moraitis
  • Leila Amgoud

During the last years, argumentation has been gaining increasing interest in modeling different reasoning tasks of an agent. Many recent works have acknowledged the importance of incorporating preferences or priorities in argumentation. However, relatively little is known about the theoretical and computational implications of preferences in argumentation.

Details

AAMAS Conference 2007 Conference Paper

A Unified and General Framework for Argumentation-based Negotiation

  • Leila Amgoud
  • Yannis Dimopoulos
  • Pavlos Moraitis

This paper proposes a unified and general framework for argumentation-based negotiation, in which the role of argumentation is formally analyzed. The framework makes it possible to study the outcomes of an argumentation-based negotiation. It shows what an agreement is, how it is related to the theories of the agents, when it is possible, and how this can be attained by the negotiating agents in this case. It defines also the notion of concession, and shows in which situation an agent will make one, as well as how it influences the evolution of the dialogue.

PDF

IJCAI Conference 2003 Conference Paper

A New Look at the Semantics and Optimization Methods of CP-Networks

  • Ronen I. Brafman
  • Yannis Dimopoulos

Preference elicitation is a serious bottleneck in many decision support applications and agent specification tasks. CP-nets were designed to make the preference elicitation process simpler and more intuitive for lay users by graphically structuring a set of Ceteris Paribus (CP) preference statements preference statements most people find natural and intuitive. In various contexts, CP-nets with an underlying cyclic structure emerge naturally. Often, they are inconsistent according to the current semantics, and the user is required to revise them. In this paper we show how optimization queries can be meaningfully answered in many "inconsistent" networks without troubling the user with requests for revisions. We also describe a method for focusing users' revision process when revisions are truly needed. In the process, we provide a formal semantics that justifies our approach and we introduce new techniques for computing optimal outcomes.

PDF

IJCAI Conference 1999 Conference Paper

Preferred Arguments are Harder to Compute than Stable Extensions

  • Yannis Dimopoulos
  • Bernhard Nebel
  • Francesca Toni

Based on an abstract framework for nonmonotonic reasoning, Bondarenko et at. have extended the logic programming semantics of admissible and preferred arguments to other nonmonotonic formalisms such as circumscription, autoepisternic logic and default logic. Although the new semantics have been tacitly assumed to mitigate the computational problems of nonmonotonic reasoning under the standard semantics of stable extensions, it seems questionable whether they improve the worst-case behaviour. As a matter of fact, we show that credulous reasoning under the new semantics in propositional logic programming and prepositional default logic has the same computational complexity as under the standard semantics. Furthermore, sceptical reasoning under the admissibility semantics is easier ~ since it is trivialised to monotonic reasoning. Finally, sceptical reasoning under the preferability semantics is harder than under the standard semantics.

PDF

IJCAI Conference 1997 Conference Paper

Integrating Explanatory and Descriptive Learning in ILP

  • Yannis Dimopoulos
  • Saso Dzeroski
  • Antonis Kakas

A learning framework that combines the two frameworks of explanatory and descriptive In­ ductive Logic Programming (ILP) is presented. The induced hypotheses in this framework are pairs of the form (T, IC) where T is a defi­ nite clausal theory and IC is a set of integrity constraints. The two components allow us to combine complementary information from the same data by applying both explanatory and descriptive learning methods. This non-trivial integration is achieved using a nonmonotonic entailment relation for the basic notion of cov­ erage in the combined language of rules and constraints where the constraints can restrict the conclusions derivable by the rules. We present a semantics for the new framework and then discuss different cases where combin­ ing information from explanatory and descrip­ tive ILP could be useful. We present some basic algorithmic frameworks for learning in the new framework, and report on some preliminary ex­ periments with encouraging results.

PDF