HOME > Journal Current TOC
Artificial Intelligence
Journal Prestige (SJR): 0.88 Citation Impact (citeScore): 4 Number of Followers: 166 Hybrid journal (It can contain Open Access articles) ISSN (Print) 0004-3702 Published by Elsevier [3159 journals] |
- Verification in incomplete argumentation frameworks
- Abstract: Publication date: Available online 10 August 2018Source: Artificial IntelligenceAuthor(s): Dorothea Baumeister, Daniel Neugebauer, Jörg Rothe, Hilmar Schadrack We tackle the problem of expressing incomplete knowledge in abstract argumentation frameworks originally introduced by Dung [26]. In applications, incomplete argumentation frameworks may arise as intermediate states in an elicitation process, or when merging different beliefs about an argumentation framework's state, or in cases where complete information cannot be obtained. We consider two specific models of incomplete argumentation frameworks, one focusing on attack incompleteness and the other on argument incompleteness, and we also provide a general model of incomplete argumentation framework that subsumes both specific models. In these three models, we study the computational complexity of variants of the verification problem with respect to six common semantics of argumentation frameworks: the conflict-free, admissible, stable, complete, grounded, and preferred semantics. We provide a full complexity map covering all three models and these six semantics. Our main result shows that the complexity of verifying the preferred semantics rises from coNP- to Σ2p-completeness when allowing uncertainty about either attacks or arguments, or both.
- Abstract: Publication date: Available online 10 August 2018Source: Artificial IntelligenceAuthor(s): Dorothea Baumeister, Daniel Neugebauer, Jörg Rothe, Hilmar Schadrack We tackle the problem of expressing incomplete knowledge in abstract argumentation frameworks originally introduced by Dung [26]. In applications, incomplete argumentation frameworks may arise as intermediate states in an elicitation process, or when merging different beliefs about an argumentation framework's state, or in cases where complete information cannot be obtained. We consider two specific models of incomplete argumentation frameworks, one focusing on attack incompleteness and the other on argument incompleteness, and we also provide a general model of incomplete argumentation framework that subsumes both specific models. In these three models, we study the computational complexity of variants of the verification problem with respect to six common semantics of argumentation frameworks: the conflict-free, admissible, stable, complete, grounded, and preferred semantics. We provide a full complexity map covering all three models and these six semantics. Our main result shows that the complexity of verifying the preferred semantics rises from coNP- to Σ2p-completeness when allowing uncertainty about either attacks or arguments, or both.
- Corrigendum to “A general account of argumentation with preferences”
[Artif. Intell. 195 (2013) 361–397]- Abstract: Publication date: Available online 6 August 2018Source: Artificial IntelligenceAuthor(s): Sanjay Modgil, Henry Prakken ASPIC+ is a general framework for structured argumentation that allows for a considerable degree of freedom as to the knowledge representation choices made in specifying the premises and rules from which arguments are constructed, and the preferences used to determine which attacks amongst constructed arguments succeed as defeats. On the other hand, the framework provides guidelines for making these choices, such that adherence to these guidelines suffices to guarantee satisfaction of the consistency and closure postulates. In particular, guidelines are given for selecting ways in which to compare the sets of defeasible constituents of arguments in order that the defined preference relations over arguments guarantee satisfaction of the rationality postulates. However, it has recently been noted that the way in which these set comparisons are made, and the guidelines for choosing these comparisons, admit counter-examples to these postulates. This research note proposes simple revisions to the ASPIC+ framework as defined in [3]. In this way, the counter-examples are avoided and rationality is preserved.
- Abstract: Publication date: Available online 6 August 2018Source: Artificial IntelligenceAuthor(s): Sanjay Modgil, Henry Prakken ASPIC+ is a general framework for structured argumentation that allows for a considerable degree of freedom as to the knowledge representation choices made in specifying the premises and rules from which arguments are constructed, and the preferences used to determine which attacks amongst constructed arguments succeed as defeats. On the other hand, the framework provides guidelines for making these choices, such that adherence to these guidelines suffices to guarantee satisfaction of the consistency and closure postulates. In particular, guidelines are given for selecting ways in which to compare the sets of defeasible constituents of arguments in order that the defined preference relations over arguments guarantee satisfaction of the rationality postulates. However, it has recently been noted that the way in which these set comparisons are made, and the guidelines for choosing these comparisons, admit counter-examples to these postulates. This research note proposes simple revisions to the ASPIC+ framework as defined in [3]. In this way, the counter-examples are avoided and rationality is preserved.
- Multi-attribute proportional representation
- Abstract: Publication date: Available online 25 July 2018Source: Artificial IntelligenceAuthor(s): Jérôme Lang, Piotr Skowron We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should have. We look for a set that fits as much as possible the desired distributions on all attributes. An example of application is the choice of members for a representative committee, where candidates are described by attributes such as gender, age and profession, and where we look for a committee that for each attribute offers a certain representation, i.e., a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. Another example of application is the selection of a common set of items to be used by a group of users, where items are labelled by attribute values. With a single attribute the problem collapses to the apportionment problem for party-list proportional representation systems (in such a case the value of the single attribute would be a political affiliation of a candidate). We study the properties of the associated subset selection rules, as well as their computational complexity.
- Abstract: Publication date: Available online 25 July 2018Source: Artificial IntelligenceAuthor(s): Jérôme Lang, Piotr Skowron We consider the following problem in which a given number of items has to be chosen from a predefined set. Each item is described by a vector of attributes and for each attribute there is a desired distribution that the selected set should have. We look for a set that fits as much as possible the desired distributions on all attributes. An example of application is the choice of members for a representative committee, where candidates are described by attributes such as gender, age and profession, and where we look for a committee that for each attribute offers a certain representation, i.e., a single committee that contains a certain number of young and old people, certain number of men and women, certain number of people with different professions, etc. Another example of application is the selection of a common set of items to be used by a group of users, where items are labelled by attribute values. With a single attribute the problem collapses to the apportionment problem for party-list proportional representation systems (in such a case the value of the single attribute would be a political affiliation of a candidate). We study the properties of the associated subset selection rules, as well as their computational complexity.
- Second-order propositional modal logic: Expressiveness and completeness
results- Abstract: Publication date: Available online 18 July 2018Source: Artificial IntelligenceAuthor(s): Francesco Belardinelli, Wiebe van der Hoek, Louwe B. Kuijer In this paper we advance the state-of-the-art on the application of second-order propositional modal logic (SOPML) in the representation of individual and group knowledge, as well as temporal and spatial reasoning. The main theoretical contributions of the paper can be summarized as follows. Firstly, we introduce the language of (multi-modal) SOPML and interpret it on a variety of different classes of Kripke frames according to the features of the accessibility relations and of the algebraic structure of the quantification domain of propositions. We provide axiomatisations for some of these classes, and show that SOPML is unaxiomatisable on the remaining classes. Secondly, we introduce novel notions of (bi)simulations and prove that they indeed preserve the interpretation of formulas in (the universal fragment of) SOPML. Then, we apply this formal machinery to study the expressiveness of Second-order Propositional Epistemic Logic (SOPEL) in representing higher-order knowledge, i.e., the knowledge agents have about other agents' knowledge, as well as graph-theoretic notions (e.g., 3-colorability, Hamiltonian paths, etc.) The final outcome is a rich formalism to represent and reason about relevant concepts in artificial intelligence, while still having a model checking problem that is no more computationally expensive than that of the less expressive quantified boolean logic.
- Abstract: Publication date: Available online 18 July 2018Source: Artificial IntelligenceAuthor(s): Francesco Belardinelli, Wiebe van der Hoek, Louwe B. Kuijer In this paper we advance the state-of-the-art on the application of second-order propositional modal logic (SOPML) in the representation of individual and group knowledge, as well as temporal and spatial reasoning. The main theoretical contributions of the paper can be summarized as follows. Firstly, we introduce the language of (multi-modal) SOPML and interpret it on a variety of different classes of Kripke frames according to the features of the accessibility relations and of the algebraic structure of the quantification domain of propositions. We provide axiomatisations for some of these classes, and show that SOPML is unaxiomatisable on the remaining classes. Secondly, we introduce novel notions of (bi)simulations and prove that they indeed preserve the interpretation of formulas in (the universal fragment of) SOPML. Then, we apply this formal machinery to study the expressiveness of Second-order Propositional Epistemic Logic (SOPEL) in representing higher-order knowledge, i.e., the knowledge agents have about other agents' knowledge, as well as graph-theoretic notions (e.g., 3-colorability, Hamiltonian paths, etc.) The final outcome is a rich formalism to represent and reason about relevant concepts in artificial intelligence, while still having a model checking problem that is no more computationally expensive than that of the less expressive quantified boolean logic.
- Predicting Human Decision-Making, Ariel Rosenfeld, Sarit Kraus. Morgan &
Claypool Publishers (2018)- Abstract: Publication date: Available online 17 July 2018Source: Artificial IntelligenceAuthor(s): Bo An
- Abstract: Publication date: Available online 17 July 2018Source: Artificial IntelligenceAuthor(s): Bo An
- Classical logic, argument and dialectic
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): M. D'Agostino, S. Modgil A well studied instantiation of Dung's abstract theory of argumentation yields argumentation-based characterisations of non-monotonic inference over possibly inconsistent sets of classical formulae. This provides for single-agent reasoning in terms of argument and counter-argument, and distributed non-monotonic reasoning in the form of dialogues between computational and/or human agents. However, features of existing formalisations of classical logic argumentation (Cl-Arg) that ensure satisfaction of rationality postulates, preclude applications of Cl-Arg that account for real-world dialectical uses of arguments by resource-bounded agents. This paper formalises dialectical classical logic argumentation that both satisfies these practical desiderata and is provably rational. In contrast to standard approaches to Cl-Arg we: 1) draw an epistemic distinction between an argument's premises accepted as true, and those assumed true for the sake of argument, so formalising the dialectical move whereby arguments' premises are shown to be inconsistent, and avoiding the foreign commitment problem that arises in dialogical applications; 2) provide an account of Cl-Arg suitable for real-world use by eschewing the need to check that an argument's premises are subset minimal and consistent, and identifying a minimal set of assumptions as to the arguments that must be constructed from a set of formulae in order to ensure that the outcome of evaluation is rational. We then illustrate our approach with a natural deduction proof theory for propositional classical logic that allows measurement of the ‘depth’ of an argument, such that the construction of depth-bounded arguments is a tractable problem, and each increase in depth naturally equates with an increase in the inferential capabilities of real-world agents. We also provide a resource-bounded argumentative characterisation of non-monotonic inference as defined by Brewka's Preferred Subtheories.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): M. D'Agostino, S. Modgil A well studied instantiation of Dung's abstract theory of argumentation yields argumentation-based characterisations of non-monotonic inference over possibly inconsistent sets of classical formulae. This provides for single-agent reasoning in terms of argument and counter-argument, and distributed non-monotonic reasoning in the form of dialogues between computational and/or human agents. However, features of existing formalisations of classical logic argumentation (Cl-Arg) that ensure satisfaction of rationality postulates, preclude applications of Cl-Arg that account for real-world dialectical uses of arguments by resource-bounded agents. This paper formalises dialectical classical logic argumentation that both satisfies these practical desiderata and is provably rational. In contrast to standard approaches to Cl-Arg we: 1) draw an epistemic distinction between an argument's premises accepted as true, and those assumed true for the sake of argument, so formalising the dialectical move whereby arguments' premises are shown to be inconsistent, and avoiding the foreign commitment problem that arises in dialogical applications; 2) provide an account of Cl-Arg suitable for real-world use by eschewing the need to check that an argument's premises are subset minimal and consistent, and identifying a minimal set of assumptions as to the arguments that must be constructed from a set of formulae in order to ensure that the outcome of evaluation is rational. We then illustrate our approach with a natural deduction proof theory for propositional classical logic that allows measurement of the ‘depth’ of an argument, such that the construction of depth-bounded arguments is a tractable problem, and each increase in depth naturally equates with an increase in the inferential capabilities of real-world agents. We also provide a resource-bounded argumentative characterisation of non-monotonic inference as defined by Brewka's Preferred Subtheories.
- Together we know how to achieve: An epistemic logic of know-how
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Pavel Naumov, Jia Tao The existence of a coalition strategy to achieve a goal does not necessarily mean that the coalition has enough information to know how to follow the strategy. Neither does it mean that the coalition knows that such a strategy exists. The article studies an interplay between the distributed knowledge, coalition strategies, and coalition “know-how” strategies. The main technical result is a sound and complete trimodal logical system that describes the properties of this interplay.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Pavel Naumov, Jia Tao The existence of a coalition strategy to achieve a goal does not necessarily mean that the coalition has enough information to know how to follow the strategy. Neither does it mean that the coalition knows that such a strategy exists. The article studies an interplay between the distributed knowledge, coalition strategies, and coalition “know-how” strategies. The main technical result is a sound and complete trimodal logical system that describes the properties of this interplay.
- Dynamics in matching and coalition formation games with structural
constraints- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Martin Hoefer, Daniel Vaz, Lisa Wagner Matching and coalition formation are fundamental aspects in the organization of many multi-agent systems. In large populations, the emergence of coalitions is often restricted by structural constraints under which agents can reorganize, e.g., local visibility or externality constraints among the agents. We study this aspect using a novel framework for dynamics with constraints within the popular domain of hedonic coalition formation games. We analyze the effects of structural constraints on the convergence of matching and coalition formation processes to stable states. Our main result are tight characterizations for the constraint structures based on which dynamic coalition formation can stabilize quickly. We show a variety of convergence results for matching and coalition formation games with different forms of locality and externality constraints. In particular, we propose and analyze a new model of graph-based visibility for coalition formation games and tightly characterize the graph structures that allow polynomial-time convergence – it can be achieved if and only if coalition formation is based on complete or star graphs.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Martin Hoefer, Daniel Vaz, Lisa Wagner Matching and coalition formation are fundamental aspects in the organization of many multi-agent systems. In large populations, the emergence of coalitions is often restricted by structural constraints under which agents can reorganize, e.g., local visibility or externality constraints among the agents. We study this aspect using a novel framework for dynamics with constraints within the popular domain of hedonic coalition formation games. We analyze the effects of structural constraints on the convergence of matching and coalition formation processes to stable states. Our main result are tight characterizations for the constraint structures based on which dynamic coalition formation can stabilize quickly. We show a variety of convergence results for matching and coalition formation games with different forms of locality and externality constraints. In particular, we propose and analyze a new model of graph-based visibility for coalition formation games and tightly characterize the graph structures that allow polynomial-time convergence – it can be achieved if and only if coalition formation is based on complete or star graphs.
- Reasoning about discrete and continuous noisy sensors and effectors in
dynamical systems- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Vaishak Belle, Hector J. Levesque Among the many approaches for reasoning about degrees of belief in the presence of noisy sensing and acting, the logical account proposed by Bacchus, Halpern, and Levesque is perhaps the most expressive. While their formalism is quite general, it is restricted to fluents whose values are drawn from discrete finite domains, as opposed to the continuous domains seen in many robotic applications. In this work, we show how this limitation in that approach can be lifted. By dealing seamlessly with both discrete distributions and continuous densities within a rich theory of action, we provide a very general logical specification of how belief should change after acting and sensing in complex noisy domains.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Vaishak Belle, Hector J. Levesque Among the many approaches for reasoning about degrees of belief in the presence of noisy sensing and acting, the logical account proposed by Bacchus, Halpern, and Levesque is perhaps the most expressive. While their formalism is quite general, it is restricted to fluents whose values are drawn from discrete finite domains, as opposed to the continuous domains seen in many robotic applications. In this work, we show how this limitation in that approach can be lifted. By dealing seamlessly with both discrete distributions and continuous densities within a rich theory of action, we provide a very general logical specification of how belief should change after acting and sensing in complex noisy domains.
- On the adoption of abductive reasoning for time series interpretation
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): T. Teijeiro, P. Félix Time series interpretation aims to provide an explanation of what is observed in terms of its underlying processes. The present work is based on the assumption that the common classification-based approaches to time series interpretation suffer from a set of inherent weaknesses, whose ultimate cause lies in the monotonic nature of the deductive reasoning paradigm. In this document we propose a new approach to this problem, based on the initial hypothesis that abductive reasoning properly accounts for the human ability to identify and characterize the patterns appearing in a time series. The result of this interpretation is a set of conjectures in the form of observations, organized into an abstraction hierarchy and explaining what has been observed. A knowledge-based framework and a set of algorithms for the interpretation task are provided, implementing a hypothesize-and-test cycle guided by an attentional mechanism. As a representative application domain, interpretation of the electrocardiogram allows us to highlight the strengths of the proposed approach in comparison with traditional classification-based approaches.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): T. Teijeiro, P. Félix Time series interpretation aims to provide an explanation of what is observed in terms of its underlying processes. The present work is based on the assumption that the common classification-based approaches to time series interpretation suffer from a set of inherent weaknesses, whose ultimate cause lies in the monotonic nature of the deductive reasoning paradigm. In this document we propose a new approach to this problem, based on the initial hypothesis that abductive reasoning properly accounts for the human ability to identify and characterize the patterns appearing in a time series. The result of this interpretation is a set of conjectures in the form of observations, organized into an abstraction hierarchy and explaining what has been observed. A knowledge-based framework and a set of algorithms for the interpretation task are provided, implementing a hypothesize-and-test cycle guided by an attentional mechanism. As a representative application domain, interpretation of the electrocardiogram allows us to highlight the strengths of the proposed approach in comparison with traditional classification-based approaches.
- Incentive-based search for efficient equilibria of the public goods game
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Vadim Levit, Zohar Komarovsky, Tal Grinshpoun, Amnon Meisels The “best-shot” public goods game is a network game, defined on a social network. The simple version of the public goods game (PGG) has a fixed utility for a player who has at least a single neighbor buying the good. Players in the general version of PGG have additional utility when multiple neighbors purchase the good. The general version of the public goods game is shown to be a potential game, establishing the convergence to a stable state (i.e., a pure Nash equilibrium – PNE) by best-response dynamics. One can think of best-response dynamics as a distributed algorithm that runs in a fixed order of players/agents and is guaranteed to converge to a PNE.A new distributed algorithm is proposed for finding PNEs with improved efficiency by the use of transfer of payoffs among players. For the simple version of PGG, it is shown that the proposed algorithm can stabilize an outcome that maximizes social welfare. For the general version of the game, the proposed procedure transforms any initial outcome into a stable solution at least as efficient as the initial outcome by using transfers. An extensive experimental evaluation on randomly generated PGGs demonstrates that whereas pure best-response dynamics converges on stable states that have lower efficiency than the initial outcome, the proposed procedure finds PNEs of higher efficiency.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Vadim Levit, Zohar Komarovsky, Tal Grinshpoun, Amnon Meisels The “best-shot” public goods game is a network game, defined on a social network. The simple version of the public goods game (PGG) has a fixed utility for a player who has at least a single neighbor buying the good. Players in the general version of PGG have additional utility when multiple neighbors purchase the good. The general version of the public goods game is shown to be a potential game, establishing the convergence to a stable state (i.e., a pure Nash equilibrium – PNE) by best-response dynamics. One can think of best-response dynamics as a distributed algorithm that runs in a fixed order of players/agents and is guaranteed to converge to a PNE.A new distributed algorithm is proposed for finding PNEs with improved efficiency by the use of transfer of payoffs among players. For the simple version of PGG, it is shown that the proposed algorithm can stabilize an outcome that maximizes social welfare. For the general version of the game, the proposed procedure transforms any initial outcome into a stable solution at least as efficient as the initial outcome by using transfers. An extensive experimental evaluation on randomly generated PGGs demonstrates that whereas pure best-response dynamics converges on stable states that have lower efficiency than the initial outcome, the proposed procedure finds PNEs of higher efficiency.
- The complexity of Bayesian networks specified by propositional and
relational languages- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Fabio G. Cozman, Denis D. Mauá We examine the complexity of inference in Bayesian networks specified by logical languages. We consider representations that range from fragments of propositional logic to function-free first-order logic with equality; in doing so we cover a variety of plate models and of probabilistic relational models. We study the complexity of inferences when network, query and domain are the input (the inferential and the combined complexity), when the network is fixed and query and domain are the input (the query/data complexity), and when the network and query are fixed and the domain is the input (the domain complexity). We draw connections with probabilistic databases and liftability results, and obtain complexity classes that range from polynomial to exponential levels; we identify new languages with tractable inference, and we relate our results to languages based on plates and probabilistic relational models.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Fabio G. Cozman, Denis D. Mauá We examine the complexity of inference in Bayesian networks specified by logical languages. We consider representations that range from fragments of propositional logic to function-free first-order logic with equality; in doing so we cover a variety of plate models and of probabilistic relational models. We study the complexity of inferences when network, query and domain are the input (the inferential and the combined complexity), when the network is fixed and query and domain are the input (the query/data complexity), and when the network and query are fixed and the domain is the input (the domain complexity). We draw connections with probabilistic databases and liftability results, and obtain complexity classes that range from polynomial to exponential levels; we identify new languages with tractable inference, and we relate our results to languages based on plates and probabilistic relational models.
- Logical foundations of information disclosure in ontology-based data
integration- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Michael Benedikt, Bernardo Cuenca Grau, Egor V. Kostylev Ontology-based data integration systems allow users to effectively access data sitting in multiple sources by means of queries over a global schema described by an ontology. In practice, data sources often contain sensitive information that the data owners want to keep inaccessible to users. Our aim in this paper is to lay the logical foundations of information disclosure in ontology-based data integration. Our focus is on the semantic requirements that a data integration system should satisfy before it is made available to users for querying, as well as on the computational complexity of checking whether such requirements are fulfilled. In particular, we formalise and study the problem of determining whether a given data integration system discloses a source query to an attacker. We consider disclosure on a particular dataset, and also whether a schema admits a dataset on which disclosure occurs. We provide matching lower and upper complexity bounds on disclosure analysis, in the process introducing a number of techniques for analysing logical privacy issues in ontology-based data integration.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Michael Benedikt, Bernardo Cuenca Grau, Egor V. Kostylev Ontology-based data integration systems allow users to effectively access data sitting in multiple sources by means of queries over a global schema described by an ontology. In practice, data sources often contain sensitive information that the data owners want to keep inaccessible to users. Our aim in this paper is to lay the logical foundations of information disclosure in ontology-based data integration. Our focus is on the semantic requirements that a data integration system should satisfy before it is made available to users for querying, as well as on the computational complexity of checking whether such requirements are fulfilled. In particular, we formalise and study the problem of determining whether a given data integration system discloses a source query to an attacker. We consider disclosure on a particular dataset, and also whether a schema admits a dataset on which disclosure occurs. We provide matching lower and upper complexity bounds on disclosure analysis, in the process introducing a number of techniques for analysing logical privacy issues in ontology-based data integration.
- Algorithms for electric vehicle scheduling in large-scale
mobility-on-demand schemes- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Emmanouil S. Rigas, Sarvapali D. Ramchurn, Nick Bassiliades We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Emmanouil S. Rigas, Sarvapali D. Ramchurn, Nick Bassiliades We study a setting where Electric Vehicles (EVs) can be hired to drive from pick-up to drop-off points in a Mobility-on-Demand (MoD) scheme. The goal of the system is, either to maximize the number of customers that are serviced, or the total EV utilization. To do so, we characterise the optimisation problem as a max-flow problem in order to determine the set of feasible trips given the available EVs at each location. We then model and solve the EV-to-trip scheduling problem offline and optimally using Mixed Integer Programming (MIP) techniques and show that the solution scales up to medium sized problems. Given this, we develop two non-optimal algorithms, namely an incremental-MIP algorithm for medium to large problems and a greedy heuristic algorithm for very large problems. Moreover, we develop a tabu search-based local search technique to further improve upon and compare against the solution of the non-optimal algorithms. We study the performance of these algorithms in settings where either battery swap or battery charge at each station is used to cope with the EVs' limited driving range. Moreover, in settings where EVs need to be scheduled online, we propose a novel algorithm that accounts for the uncertainty in future trip requests. All algorithms are empirically evaluated using real-world data of locations of shared vehicle pick-up and drop-off stations. In our experiments, we observe that when all EVs carry the same battery which is large enough for the longest trips, the greedy algorithm with battery swap with the max-flow solution as a pre-processing step, provides the optimal solution. At the same time, the greedy algorithm with battery charge is close to the optimal (97% on average) and is further improved when local search is used. When some EVs do not have a large enough battery to execute some of the longest trips, the incremental-MIP generates solutions slightly better than the greedy, while the optimal algorithm is the best but scales up to medium sized problems only. Moreover, the online algorithm is shown to be on average at least 90% of the optimal. Finally, the greedy algorithm scales to 10-times more tasks than the incremental-MIP and 1000-times more than the static MIP in reasonable time.
- Fixing balanced knockout and double elimination tournaments
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, Toby Walsh Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner. Finally, we show that our main NP-completeness result extends to a variant of balanced knockout tournaments called double-elimination tournaments.
- Abstract: Publication date: September 2018Source: Artificial Intelligence, Volume 262Author(s): Haris Aziz, Serge Gaspers, Simon Mackenzie, Nicholas Mattei, Paul Stursberg, Toby Walsh Balanced knockout tournaments are one of the most common formats for sports competitions, and are also used in elections and decision-making. We consider the computational problem of finding the optimal draw for a particular player in such a tournament. The problem has generated considerable research within AI in recent years. We prove that checking whether there exists a draw in which a player wins is NP-complete, thereby settling an outstanding open problem. Our main result has a number of interesting implications on related counting and approximation problems. We present a memoization-based algorithm for the problem that is faster than previous approaches. Moreover, we highlight two natural cases that can be solved in polynomial time. All of our results also hold for the more general problem of counting the number of draws in which a given player is the winner. Finally, we show that our main NP-completeness result extends to a variant of balanced knockout tournaments called double-elimination tournaments.
- Multi-robot inverse reinforcement learning under occlusion with estimation
of state transitions- Abstract: Publication date: Available online 9 July 2018Source: Artificial IntelligenceAuthor(s): Kenneth Bogert, Prashant Doshi Inverse reinforcement learning (IRL), analogously to RL, refers to both the problem and associated methods by which an agent passively observing another agent's actions over time, seeks to learn the latter's reward function. The learning agent is typically called the learner while the observed agent is often an expert in popular applications such as in learning from demonstrations. Some of the assumptions that underlie current IRL methods are impractical for many robotic applications. Specifically, they assume that the learner has full observability of the expert as it performs its task; that the learner has full knowledge of the expert's dynamics; and that there is always only one expert agent in the environment. For example, these assumptions are particularly restrictive in our application scenario where a subject robot is tasked with penetrating a perimeter patrol by two other robots after observing them from a vantage point. In our instance of this problem, the learner can observe at most 10% of the patrol.We relax these assumptions and systematically generalize a known IRL method, Maximum Entropy IRL, to enable the subject to learn the preferences of the patrolling robots, subsequently their behaviors, and predict their future positions well enough to plan a route to its goal state without being spotted. Challenged by occlusion, multiple interacting robots, and partially known dynamics we demonstrate empirically that the generalization improves significantly on several baselines in its ability to inversely learn in this application setting. Of note, it leads to significant improvement in the learner's overall success rate of penetrating the patrols. Our methods represent significant steps towards making IRL pragmatic and applicable to real-world contexts.
- Abstract: Publication date: Available online 9 July 2018Source: Artificial IntelligenceAuthor(s): Kenneth Bogert, Prashant Doshi Inverse reinforcement learning (IRL), analogously to RL, refers to both the problem and associated methods by which an agent passively observing another agent's actions over time, seeks to learn the latter's reward function. The learning agent is typically called the learner while the observed agent is often an expert in popular applications such as in learning from demonstrations. Some of the assumptions that underlie current IRL methods are impractical for many robotic applications. Specifically, they assume that the learner has full observability of the expert as it performs its task; that the learner has full knowledge of the expert's dynamics; and that there is always only one expert agent in the environment. For example, these assumptions are particularly restrictive in our application scenario where a subject robot is tasked with penetrating a perimeter patrol by two other robots after observing them from a vantage point. In our instance of this problem, the learner can observe at most 10% of the patrol.We relax these assumptions and systematically generalize a known IRL method, Maximum Entropy IRL, to enable the subject to learn the preferences of the patrolling robots, subsequently their behaviors, and predict their future positions well enough to plan a route to its goal state without being spotted. Challenged by occlusion, multiple interacting robots, and partially known dynamics we demonstrate empirically that the generalization improves significantly on several baselines in its ability to inversely learn in this application setting. Of note, it leads to significant improvement in the learner's overall success rate of penetrating the patrols. Our methods represent significant steps towards making IRL pragmatic and applicable to real-world contexts.
- Characterizing acceptability semantics of argumentation frameworks with
recursive attack and support relations- Abstract: Publication date: Available online 9 July 2018Source: Artificial IntelligenceAuthor(s): Sebastian Gottifredi, Andrea Cohen, Alejandro J. García, Guillermo R. Simari Over the last decade, several extensions of Dung's Argumentation Frameworks (AFs) have been introduced in the literature. Some of these extensions concern the nature of the attack relation, such as the consideration of recursive attacks, whereas others incorporate additional interactions, such as a support relation. Recently, the Attack-Support Argumentation Framework (ASAF) was proposed, which accounts for recursive attacks and supports, attacks to supports and supports to attacks, at any level, where the support relation is interpreted as necessity. Currently, to determine the accepted elements of an ASAF (which may be arguments, attacks, and supports) it is required to translate such an ASAF into a Dung's AF. In this work, we provide a formal characterization of acceptability semantics directly on the ASAF, without requiring such a translation. We prove that our characterization is sound since it satisfies different results from Dung's argumentation theory; moreover, we formally show that the approach proposed here for addressing acceptability is equivalent to the preexisting one, in which the ASAF was translated into an AF. Also, we formalize the relationship between the ASAF and other frameworks on which it is inspired: the Argumentation Framework with Recursive Attacks (AFRA) and the Argumentation Framework with Necessities (AFN).
- Abstract: Publication date: Available online 9 July 2018Source: Artificial IntelligenceAuthor(s): Sebastian Gottifredi, Andrea Cohen, Alejandro J. García, Guillermo R. Simari Over the last decade, several extensions of Dung's Argumentation Frameworks (AFs) have been introduced in the literature. Some of these extensions concern the nature of the attack relation, such as the consideration of recursive attacks, whereas others incorporate additional interactions, such as a support relation. Recently, the Attack-Support Argumentation Framework (ASAF) was proposed, which accounts for recursive attacks and supports, attacks to supports and supports to attacks, at any level, where the support relation is interpreted as necessity. Currently, to determine the accepted elements of an ASAF (which may be arguments, attacks, and supports) it is required to translate such an ASAF into a Dung's AF. In this work, we provide a formal characterization of acceptability semantics directly on the ASAF, without requiring such a translation. We prove that our characterization is sound since it satisfies different results from Dung's argumentation theory; moreover, we formally show that the approach proposed here for addressing acceptability is equivalent to the preexisting one, in which the ASAF was translated into an AF. Also, we formalize the relationship between the ASAF and other frameworks on which it is inspired: the Argumentation Framework with Recursive Attacks (AFRA) and the Argumentation Framework with Necessities (AFN).
- On the Responsibility for Undecisiveness in Preferred and Stable
Labellings in Abstract Argumentation- Abstract: Publication date: Available online 6 July 2018Source: Artificial IntelligenceAuthor(s): Claudia Schulz, Francesca Toni Different semantics of abstract Argumentation Frameworks (AFs) provide different levels of decisiveness for reasoning about the acceptability of conflicting arguments. The stable semantics is useful for applications requiring a high level of decisiveness, as it assigns to each argument the label “accepted” or the label “rejected”. Unfortunately, stable labellings are not guaranteed to exist, thus raising the question as to which parts of AFs are responsible for the non-existence. In this paper, we address this question by investigating a more general question concerning preferred labellings (which may be less decisive than stable labellings but are always guaranteed to exist), namely why a given preferred labelling may not be stable and thus undecided on some arguments. In particular, (1) we give various characterisations of parts of an AF, based on the given preferred labelling, and (2) we show that these parts are indeed responsible for the undecisiveness if the preferred labelling is not stable. We then use these characterisations to explain the non-existence of stable labellings. We present two types of characterisations, based on labellings that are more (or equally) committed than the given preferred labelling on the one hand, and based on the structure of the given AF on the other, and compare the respective AF parts deemed responsible. To prove that our characterisations indeed yield responsible parts, we use a notion of enforcement of labels through structural revision, by means of which the preferred labelling of the given AF can be turned into a stable labelling of the structurally revised AF. Rather than prescribing how this structural revision is carried out, we focus on the enforcement of labels and leave the engineering of the revision open to fulfil differing requirements of applications and information available to users.
- Abstract: Publication date: Available online 6 July 2018Source: Artificial IntelligenceAuthor(s): Claudia Schulz, Francesca Toni Different semantics of abstract Argumentation Frameworks (AFs) provide different levels of decisiveness for reasoning about the acceptability of conflicting arguments. The stable semantics is useful for applications requiring a high level of decisiveness, as it assigns to each argument the label “accepted” or the label “rejected”. Unfortunately, stable labellings are not guaranteed to exist, thus raising the question as to which parts of AFs are responsible for the non-existence. In this paper, we address this question by investigating a more general question concerning preferred labellings (which may be less decisive than stable labellings but are always guaranteed to exist), namely why a given preferred labelling may not be stable and thus undecided on some arguments. In particular, (1) we give various characterisations of parts of an AF, based on the given preferred labelling, and (2) we show that these parts are indeed responsible for the undecisiveness if the preferred labelling is not stable. We then use these characterisations to explain the non-existence of stable labellings. We present two types of characterisations, based on labellings that are more (or equally) committed than the given preferred labelling on the one hand, and based on the structure of the given AF on the other, and compare the respective AF parts deemed responsible. To prove that our characterisations indeed yield responsible parts, we use a notion of enforcement of labels through structural revision, by means of which the preferred labelling of the given AF can be turned into a stable labelling of the structurally revised AF. Rather than prescribing how this structural revision is carried out, we focus on the enforcement of labels and leave the engineering of the revision open to fulfil differing requirements of applications and information available to users.