HOME > Journal Current TOC
Artificial Intelligence
Journal Prestige (SJR): 0.88 Citation Impact (citeScore): 4 Number of Followers: 178 Hybrid journal (It can contain Open Access articles) ISSN (Print) 0004-3702 Published by Elsevier [3163 journals] |
- Encoding implicit relation requirements for relation extraction: A joint
inference approach- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Liwei Chen, Yansong Feng, Songfang Huang, Bingfeng Luo, Dongyan Zhao Relation extraction is the task of identifying predefined relationship between entities, and plays an essential role in information extraction, knowledge base construction, question answering and so on. Most existing relation extractors make predictions for each entity pair locally and individually, while ignoring implicit global clues available across different entity pairs and in the knowledge base, which often leads to conflicts among local predictions from different entity pairs. This paper proposes a joint inference framework that employs such global clues to resolve disagreements among local predictions. We exploit two kinds of clues to generate constraints which can capture the implicit type and cardinality requirements of a relation. Those constraints can be examined in either hard style or soft style, both of which can be effectively explored in an integer linear program formulation. Experimental results on both English and Chinese datasets show that our proposed framework can effectively utilize those two categories of global clues and resolve the disagreements among local predictions, thus improve various relation extractors when such clues are applicable to the datasets. Our experiments also indicate that the clues learnt automatically from existing knowledge bases perform comparably to or better than those refined by human.
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Liwei Chen, Yansong Feng, Songfang Huang, Bingfeng Luo, Dongyan Zhao Relation extraction is the task of identifying predefined relationship between entities, and plays an essential role in information extraction, knowledge base construction, question answering and so on. Most existing relation extractors make predictions for each entity pair locally and individually, while ignoring implicit global clues available across different entity pairs and in the knowledge base, which often leads to conflicts among local predictions from different entity pairs. This paper proposes a joint inference framework that employs such global clues to resolve disagreements among local predictions. We exploit two kinds of clues to generate constraints which can capture the implicit type and cardinality requirements of a relation. Those constraints can be examined in either hard style or soft style, both of which can be effectively explored in an integer linear program formulation. Experimental results on both English and Chinese datasets show that our proposed framework can effectively utilize those two categories of global clues and resolve the disagreements among local predictions, thus improve various relation extractors when such clues are applicable to the datasets. Our experiments also indicate that the clues learnt automatically from existing knowledge bases perform comparably to or better than those refined by human.
- Forgetting in multi-agent modal logics
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Liangda Fang, Yongmei Liu, Hans van Ditmarsch In the past decades, forgetting has been investigated for many logics and has found many applications in knowledge representation and reasoning. In this paper, we study forgetting in multi-agent modal logics. We adopt the semantic definition of existential bisimulation quantifiers as that of forgetting. We resort to canonical formulas of modal logics introduced by Moss. An arbitrary modal formula is equivalent to the disjunction of a unique set of satisfiable canonical formulas. We show that, for the logics of Kn, Dn, Tn, K45n, KD45n and S5n, the result of forgetting an atom from a satisfiable canonical formula can be computed by simply substituting the literals of the atom with ⊤. Thus we show that these logics are closed under forgetting, and hence have uniform interpolation. Finally, we generalize the above results to include common knowledge of propositional formulas.
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Liangda Fang, Yongmei Liu, Hans van Ditmarsch In the past decades, forgetting has been investigated for many logics and has found many applications in knowledge representation and reasoning. In this paper, we study forgetting in multi-agent modal logics. We adopt the semantic definition of existential bisimulation quantifiers as that of forgetting. We resort to canonical formulas of modal logics introduced by Moss. An arbitrary modal formula is equivalent to the disjunction of a unique set of satisfiable canonical formulas. We show that, for the logics of Kn, Dn, Tn, K45n, KD45n and S5n, the result of forgetting an atom from a satisfiable canonical formula can be computed by simply substituting the literals of the atom with ⊤. Thus we show that these logics are closed under forgetting, and hence have uniform interpolation. Finally, we generalize the above results to include common knowledge of propositional formulas.
- Voting on Multi-Issue Domains with Conditionally Lexicographic Preferences
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Jérôme Lang, Jérôme Mengin, Lirong Xia One approach to voting on several interrelated issues consists in using a language for compact preference representation, from which the voters' preferences are elicited and aggregated. Such a language can usually be seen as a domain restriction. We consider a well-known restriction, namely, conditionally lexicographic preferences, where both the relative importance between issues and the preference between the values of an issue may depend on the values taken by more important issues. The naturally associated language consists in describing conditional importance and conditional preference by trees together with conditional preference tables. In this paper, we study the aggregation of conditionally lexicographic preferences for several common voting rules and several classes of lexicographic preferences. We address the computation of the winning alternative for some important rules, both by identifying the computational complexity of the relevant problems and by showing that for several of them, computing the winner reduces in a very natural way to a maxsat problem.
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Jérôme Lang, Jérôme Mengin, Lirong Xia One approach to voting on several interrelated issues consists in using a language for compact preference representation, from which the voters' preferences are elicited and aggregated. Such a language can usually be seen as a domain restriction. We consider a well-known restriction, namely, conditionally lexicographic preferences, where both the relative importance between issues and the preference between the values of an issue may depend on the values taken by more important issues. The naturally associated language consists in describing conditional importance and conditional preference by trees together with conditional preference tables. In this paper, we study the aggregation of conditionally lexicographic preferences for several common voting rules and several classes of lexicographic preferences. We address the computation of the winning alternative for some important rules, both by identifying the computational complexity of the relevant problems and by showing that for several of them, computing the winner reduces in a very natural way to a maxsat problem.
- Memory networks for fine-grained opinion mining
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Wenya Wang, Sinno Jialin Pan, Daniel Dahlmeier Fine-grained opinion mining has attracted increasing attention recently because of its benefits for providing richer information compared with coarse-grained sentiment analysis. Under this problem, there are several existing works focusing on aspect (or opinion) terms extraction which utilize the syntactic relations among the words given by a dependency parser. These approaches, however, require additional information and highly depend on the quality of the parsing results. As a result, they may perform poorly on user-generated texts, such as product reviews, tweets, etc., whose syntactic structure is not precise. In this work, we offer an end-to-end deep learning model without any preprocessing. The model consists of a memory network that automatically learns the complicated interactions among aspect words and opinion words. Moreover, we extend the network with a the multi-task manner to solve a finer-grained opinion mining problem, which is more challenging than the traditional fine-grained opinion mining problem. To be specific, the finer-grained problem involves identification of aspect and opinion terms within each sentence, as well as categorization of the identified terms at the same time. To this end, we develop an end-to-end multi-task memory network, where aspect/opinion terms extraction for a specific category is considered as a task, and all the tasks are learned jointly by exploring commonalities and relationships among them. We demonstrate state-of-the-art performance of our proposed model on several benchmark datasets.
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Wenya Wang, Sinno Jialin Pan, Daniel Dahlmeier Fine-grained opinion mining has attracted increasing attention recently because of its benefits for providing richer information compared with coarse-grained sentiment analysis. Under this problem, there are several existing works focusing on aspect (or opinion) terms extraction which utilize the syntactic relations among the words given by a dependency parser. These approaches, however, require additional information and highly depend on the quality of the parsing results. As a result, they may perform poorly on user-generated texts, such as product reviews, tweets, etc., whose syntactic structure is not precise. In this work, we offer an end-to-end deep learning model without any preprocessing. The model consists of a memory network that automatically learns the complicated interactions among aspect words and opinion words. Moreover, we extend the network with a the multi-task manner to solve a finer-grained opinion mining problem, which is more challenging than the traditional fine-grained opinion mining problem. To be specific, the finer-grained problem involves identification of aspect and opinion terms within each sentence, as well as categorization of the identified terms at the same time. To this end, we develop an end-to-end multi-task memory network, where aspect/opinion terms extraction for a specific category is considered as a task, and all the tasks are learned jointly by exploring commonalities and relationships among them. We demonstrate state-of-the-art performance of our proposed model on several benchmark datasets.
- On Coarser Interval Temporal Logics
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Emilio Muñoz-Velasco, Mercedes Pelegrín, Pietro Sala, Guido Sciavicco, Ionel Eduard Stan The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Given their generally bad computational behavior of interval temporal logics, several techniques exist to produce decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely HS3, not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen's relations are a guarantee of decidability, as we prove that the second variant, namely HS7, remains undecidable in all interesting cases.
- Abstract: Publication date: Available online 17 October 2018Source: Artificial IntelligenceAuthor(s): Emilio Muñoz-Velasco, Mercedes Pelegrín, Pietro Sala, Guido Sciavicco, Ionel Eduard Stan The primary characteristic of interval temporal logic is that intervals, rather than points, are taken as the primitive ontological entities. Given their generally bad computational behavior of interval temporal logics, several techniques exist to produce decidable and computationally affordable temporal logics based on intervals. In this paper we take inspiration from Golumbic and Shamir's coarser interval algebras, which generalize the classical Allen's Interval Algebra, in order to define two previously unknown variants of Halpern and Shoham's logic (HS) based on coarser relations. We prove that, perhaps surprisingly, the satisfiability problem for the coarsest of the two variants, namely HS3, not only is decidable, but PSpace-complete in the finite/discrete case, and PSpace-hard in any other case; besides proving its complexity bounds, we implement a tableau-based satisfiability checker for it and test it against a systematically generated benchmark. Our results are strengthened by showing that not all coarser-than-Allen's relations are a guarantee of decidability, as we prove that the second variant, namely HS7, remains undecidable in all interesting cases.
- Privacy preserving region optimal algorithms for symmetric and asymmetric
DCOPs- Abstract: Publication date: Available online 11 October 2018Source: Artificial IntelligenceAuthor(s): Tal Grinshpoun, Tamir Tassa, Vadim Levit, Roie Zivan Region-optimal algorithms are local search algorithms for solving Distributed Constraint Optimization Problems (DCOPs). In each iteration of the search in such algorithms, every agent selects a group of agents that comply with some selection criteria (each algorithm specifies different criteria). Then, the agent who selected the group, called the mediator, collects assignment information from the group and neighboring agents outside the group, in order to find an optimal set of assignments for its group's agents. A contest between mediators of adjacent groups determines which groups will replace their assignments in that iteration to the found optimal ones. In this work we present a framework called RODA (Region Optimal DCOP Algorithm) that encompasses the algorithms in the region optimality family, and in particular any method for selecting groups. We devise a secure implementation of RODA, called P-RODA, which preserves constraint privacy and partial decision privacy. Our discussion covers both symmetric and asymmetric DCOPs. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. We estimate the computational overhead of P-RODA with respect to RODA and give an upper bound that depends on the group and domain sizes and on the graph topology, but not on the number of agents. The estimations are substantiated with experimental results, including experiments on a simulator, that compare the performance of P-RODA to that of its competing algorithm, P-Max-Sum.
- Abstract: Publication date: Available online 11 October 2018Source: Artificial IntelligenceAuthor(s): Tal Grinshpoun, Tamir Tassa, Vadim Levit, Roie Zivan Region-optimal algorithms are local search algorithms for solving Distributed Constraint Optimization Problems (DCOPs). In each iteration of the search in such algorithms, every agent selects a group of agents that comply with some selection criteria (each algorithm specifies different criteria). Then, the agent who selected the group, called the mediator, collects assignment information from the group and neighboring agents outside the group, in order to find an optimal set of assignments for its group's agents. A contest between mediators of adjacent groups determines which groups will replace their assignments in that iteration to the found optimal ones. In this work we present a framework called RODA (Region Optimal DCOP Algorithm) that encompasses the algorithms in the region optimality family, and in particular any method for selecting groups. We devise a secure implementation of RODA, called P-RODA, which preserves constraint privacy and partial decision privacy. Our discussion covers both symmetric and asymmetric DCOPs. The two main cryptographic means that enable this privacy preservation are secret sharing and homomorphic encryption. We estimate the computational overhead of P-RODA with respect to RODA and give an upper bound that depends on the group and domain sizes and on the graph topology, but not on the number of agents. The estimations are substantiated with experimental results, including experiments on a simulator, that compare the performance of P-RODA to that of its competing algorithm, P-Max-Sum.
- Approximating Optimal Social Choice under Metric Preferences
- Abstract: Publication date: Available online 17 August 2018Source: Artificial IntelligenceAuthor(s): Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, Piotr Skowron We consider voting under metric preferences: both voters and alternatives are associated with points in a metric space, and each voter prefers alternatives that are closer to her to ones that are further away. In this setting, it is often desirable to select an alternative that minimizes the sum of distances to the voters, i.e., the utilitarian social cost, or other similar measures of social cost. However, common voting rules operate on voters' preference rankings and therefore may be unable to identify an optimal alternative. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of an alternative selected by the rule and that of an optimal alternative. Thus, distortion measures how good a voting rule is at approximating an alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that they form a metric space. The goal of our paper is to quantify the distortion of well-known voting rules. We first establish a lower bound on the distortion of any deterministic voting rule. We then show that the distortion of positional scoring rules cannot be bounded by a constant, and for several popular rules in this family distortion is linear in the number of alternatives. On the other hand, for Copeland and similar rules the distortion is bounded by a factor of 5. These results hold both for the sum of voters' cost and the median voter cost. For Single Transferable Vote (STV), we obtain an upper bound of O(lnm) with respect to the sum of voters' costs, where m is the number of alternatives, as well as a lower bound of Ω(lnm); thus, STV is a reasonable, though not a perfect rule from this perspective. Our results for median voter cost extend to more general objective functions.
- Abstract: Publication date: Available online 17 August 2018Source: Artificial IntelligenceAuthor(s): Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, Piotr Skowron We consider voting under metric preferences: both voters and alternatives are associated with points in a metric space, and each voter prefers alternatives that are closer to her to ones that are further away. In this setting, it is often desirable to select an alternative that minimizes the sum of distances to the voters, i.e., the utilitarian social cost, or other similar measures of social cost. However, common voting rules operate on voters' preference rankings and therefore may be unable to identify an optimal alternative. A relevant measure of the quality of a voting rule is then its distortion, defined as the worst-case ratio between the performance of an alternative selected by the rule and that of an optimal alternative. Thus, distortion measures how good a voting rule is at approximating an alternative with minimum social cost, while using only ordinal preference information. The underlying costs can be arbitrary, implicit, and unknown; our only assumption is that they form a metric space. The goal of our paper is to quantify the distortion of well-known voting rules. We first establish a lower bound on the distortion of any deterministic voting rule. We then show that the distortion of positional scoring rules cannot be bounded by a constant, and for several popular rules in this family distortion is linear in the number of alternatives. On the other hand, for Copeland and similar rules the distortion is bounded by a factor of 5. These results hold both for the sum of voters' cost and the median voter cost. For Single Transferable Vote (STV), we obtain an upper bound of O(lnm) with respect to the sum of voters' costs, where m is the number of alternatives, as well as a lower bound of Ω(lnm); thus, STV is a reasonable, though not a perfect rule from this perspective. Our results for median voter cost extend to more general objective functions.
- 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
- 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.