By expressiveness we mean the ability to encode a desired set of two-valued interpretations over a given propositional vocabulary A using only atoms from A. We also compare ADFs' expressiveness with that of (the two-valued semantics of) abstract argumentation frameworks, normal logic programs and propositional logic. While the computational complexity of the two-valued model existence problem for all these languages is (almost) the same, we show that the languages form a neat hierarchy with respect to their expressiveness. We then demonstrate that this hierarchy collapses once we allow to introduce a linear number of new vocabulary elements. We finally also analyse and compare the representational succinctness of ADFs (for two-valued model semantics), that is, their capability to represent two-valued interpretation sets in a space-efficient manner.

What can a human compute in his/her head that a powerful adversary cannot infer? To answer this question, we define a model of human computation and a measure of security. Then, motivated by the special case of password creation, we propose a collection of well-defined password-generation methods. We show that our password generation methods are humanly computable and, to a well-defined extent, machine uncrackable. For the proof of security, we posit that password generation methods are public, but that the human’s privately chosen seed is not, and that the adversary will have observed only a few input-output pairs. Besides the application to password generation, our proposed Human Usability Model (HUM) will have other applications.

Quality assurance is one the most important challenges in crowdsourcing. Assigning tasks to several workers to increase quality through redundant answers can be expensive if asking homogeneous sources. This limitation has been overlooked by current crowdsourcing platforms resulting therefore in costly solutions. In order to achieve desirable cost-quality tradeoffs it is essential to apply efficient crowd access optimization techniques. Our work argues that optimization needs to be aware of diversity and correlation of information within groups of individuals so that crowdsourcing redundancy can be adequately planned beforehand. Based on this intuitive idea, we introduce the Access Path Model (APM), a novel crowd model that leverages the notion of access paths as an alternative way of retrieving information. APM aggregates answers ensuring high quality and meaningful confidence. Moreover, we devise a greedy optimization algorithm for this model that finds a provably good approximate plan to access the crowd. We evaluate our approach on three crowdsourced datasets that illustrate various aspects of the problem. Our results show that the Access Path Model combined with greedy optimization is cost-efficient and practical to overcome common difficulties in large-scale crowdsourcing like data sparsity and anonymity.

Domain models for sequential decision making typically represent abstract versions of real-world systems. In practice, such representations are compact, easy to maintain, and affort faster solution times. Unfortunately, as we show in this paper, simple ways of abstracting solvable real-world problems may lead to models whose solutions are incorrect with respect to the real-world problem. There is some evidence that such limitations have restricted the applicability of SDM technology in the real world, as is apparent in the case of task and motion planning in robotics. We show that the situation can be ameliorated by a combination of increased expressive power---for example, allowing angelic nondeterminism in action effects---and new kinds of algorithmic approaches designed to produce correct solutions from initially incorrect or non-Markovian abstract models.

Pulp fiction author William Wallace Cook published Plotto: The Master Book of All Plots in 1928, which contains almost 2000 plot fragments and relatively formal instructions on how human authors could combine them to produce plots behind novels. In this paper we show one way that the methods in this book can be used to computationally generate plots from the fragments. We also show sample plots generated by our system called Plotter that uses this method. Finally we use them to discuss idiosyncrasies and limitations of the book.

This paper describes the structure of a web service able to generate simple game levels via constrained evolutionary optimization. The provided web service allows users to generate playable game levels without needing to understand the underlying process and without having to allocate computational resources for doing so; combined with the highly expressive and customizable generator, a broad range of levels for different genres and purposes can meet many user needs.

Video-game designers often tessellate continuous 2-dimensional terrain into a grid of blocked and unblocked square cells. The three main ways to calculate short paths on such a grid are to determine truly shortest paths, shortest vertex paths and shortest grid paths, listed here in decreasing  order of computation time and increasing order of resulting path length. We show that, for both vertex and grid paths on both 4-neighbor and 8-neighbor grids, placing vertices at cell corners rather than at cell centers tends to result in shorter paths. We quantify the advantage of cell corners over cell centers theoretically with tight worst-case bounds on the ratios of path lengths, and empirically on a large set of benchmark test cases. We also quantify the advantage of 8-neighbor grids over 4-neighbor grids.

In interactive storytelling systems and other story-based computer games, a drama manager is a background agent that aims to bring about an enjoyable and coherent experience for the players. In this paper, we present a personalized drama manager that increases a player's expected enjoyment without removing player agency. Our personalized drama manager models a player's preference using data-driven techniques, predicts the probability the player transitioning to different story experiences, selects an objective experience that can maximize the player's expected enjoyment, and guides the player to the selected story experience. Human study results show that our drama manager can significantly increase players' enjoyment ratings in an interactive storytelling testbed, compared to drama managers in previous research.

This abstract is proposing a challenging problem: to infer a human's mental state — intent and belief — from an observed RGBD video for human-robot interaction. The task is to integrate symbolic reasoning, a field well-studied within A.I. domains, with the uncertainty native to computer vision strategies. Traditional A.I. strategies for plan inference typically rely on first-order logic and closed world assumptions which struggle to take into account the inherent uncertainty of noisy observations within a scene. Computer vision relies on pattern-recognition strategies that have difficulty accounting for higher-level reasoning and abstract representation of world knowledge. By combining these two approaches in a principled way under a probabilistic programming framework, we define new computer vision tasks such as actor intent prediction and belief inference from an observed video sequence. Through inferring a human's theory of mind, a robotic agent can automatically determine a human's goals to collaborate with them.

Storytelling can be used by conversational agents in a wide variety of domains to maintain user engagement, both within a single interaction and over dozens or hun- dreds of interactions over time. The majority of agents designed with this ability to date deliver their stories as monologues without user input. However, people rarely tell stories in conversations this way, and instead rely on listener contributions to guide the storytelling process. Corpus-based studies of human-human conversational storytelling have demonstrated greater engagement, in the form of longer stories, when listeners co-construct stories this way. We describe a research framework for the generation and evaluation of co-constructed social stories in the context of task-based conversations, and a study on the effects of degree of user-agent story co-construction on user engagement. We find that users are more en- gaged with storytelling agents that allow them to co- construct stories in a contentful manner by asking ques- tions, compared to co-construction through acknowl- edgments only.