Problems that require multiple agents to follow non-interfering paths from their current states to their respective goal states are called multi-agent pathfinding problems (MAPFs). In previous work, we presented Independence Detection (ID), an algorithm for breaking a large MAPF problem into smaller problems that can be solved independently. Independence Detection is complete and can be used in combination with both optimal and approximation algorithms. This paper serves as an introduction to Independence Detection and aims to clarify its details.

For the long term co-existence of robots with us in complete harmony, they will be expected to show sociocognitive behaviors. In this paper, taking inspiration from child development research and human behavioral psychology we will identify the basic but key capabilities: perceiving abilities, effort and affordances. Further we will present the concepts, which fuse these components to perform multi-effort ability and affordance analysis. We will show instantiations of these capabilities on real robot and will discuss its potential applications for more complex socio-cognitive behavior.

Crowdsourcing markets, such as Amazon Mechanical Turk, provide a platform for matching prospective workers around the world with tasks. However, they are often plagued by workers who attempt to exert as little effort as possible, and requesters who deny workers payment for their labor. For crowdsourcing markets to succeed, it is essential to discourage such behavior. With this in mind, we propose a framework for the design and analysis of incentive mechanisms based on social norms, which consist of a set of rules that participants are expected to follow, and a mechanism for updating participants’ public reputations based on whether or not they do. We start by considering the most basic version of our model, which contains only homogeneous participants and randomly matches workers with tasks. The optimal social norm in this setting turns out to be a simple, easily comprehensible incentive mechanism in which market participants are encouraged to play a tit-for-tat-like strategy. This simple mechanism is optimal even when the set of market participants changes dynamically over time, or when some fraction of the participants may be irrational. In addition to the basic model, we demonstrate how this framework can be applied to situations in which there are heterogeneous users by giving several illustrating examples. This work is a first step towards a complete theory of incentive design for crowdsourcing systems. We hope to build upon this framework and explore more interesting and practical aspects of real online labor markets in our future work.

This paper presents a dynamic role assignment and formation positioning system used by the 2011 RoboCup 3D simulation league champion UT Austin Villa. This positioning system was a key component in allowing the team to win all 24 games it played at the competition during which the team scored 136 goals and conceded none. The positioning system was designed to allow for decentralized coordination among physically realistic simulated humanoid soccer playing robots in the partially observable, non-deterministic, noisy, dynamic, and limited communication setting of the RoboCup 3D simulation league simulator. Although the positioning system is discussed in the context of the RoboCup 3D simulation environment, it is not domain specific and can readily be employed in other RoboCup leagues as it generalizes well to many realistic and real-world multiagent systems.

We explore the use of an interface to mark pairs of points on two images which are in "correspondence" with one another, as a way of collecting part annotations. The interface allows annotations of visual categories that are structurally diverse, such as chairs and buildings, where it is difficult to define a set of parts, or landmarks, that are consistent, namable or uniquely defined across all instances of the category. It allows flexibility in annotation - the landmarks can be instance specific, are not constrained by language, could be many to one, etc and requires little category specific instructions. We compare our approach to two popular methods of collecting part annotations, (1) drawing bounding boxes for a set of parts, and (2) annotating a set of landmarks, in terms of annotation setup overhead, cost, difficulty, applicability and utility, and identify scenarios where one method is better suited than the others. Preliminary experiments suggest that such annotations between a sparse set of pairs can be used to bootstrap many high level visual recognition tasks such as part discovery and semantic saliency.

Neurules are a type of neuro-symbolic rules integrating neurocomputing and production rules. Each neurule is represented as an adaline unit. Neurules exhibit characteristics such as modularity, naturalness and ability to perform interactive and integrated inferences. One way of producing a neurule base is through conversion of an existing symbolic rule base yielding an equivalent but more compact rule base. The conversion process merges symbolic rules having the same conclusion into one or more neurules. Due to the inability of the adaline unit to handle inseparability, more than one neurule for each conclusion may be produced. In this paper, we define criteria concerning the ability or inability to convert a rule set into a single neurule. Definition of criteria determining whether a set of symbolic rules can (or cannot) be converted into a single, equivalent but more compact rule is of general representational interest. With application of such criteria, the conversion process of symbolic rules into neurules becomes more time- and space-efficient by omitting useless trainings. Experimental results are promising.

We report results from a human computation study that tests the extent to which output agreement games are better than traditional methods in terms of increasing quality of labels and motivation of voluntary workers on a task with a gold standard. We built an output agreement game that let workers recruited from Amazon's Mechanical Turks label the semantic textual similarity of 20 sentence pairs. To compare and test the effects of the major components of the game, we created interfaces that had different combinations of a gaming environment (G), social interaction (S), and feedback (F). Our results show that the main reason that an output agreement game can collect more high-quality labels is the gaming environment (scoring system, leaderboard, etc). On the other hand, a worker is much more motivated to voluntarily do the task if he or she can do it with another worker (i.e., with social interaction). Our analysis provides human computation researchers important insight on understanding how and why the method of Game with a Purpose (GWAP) can generate high-quality outcomes and motivate more voluntary workers.

Smart Cities is a vision driven by the availability of governmental data that fosters many challenging applications. One of them is the management of inconsistent traffic regulations, i.e., the handling of inconsistent traffic signs and measures in urban areas such as wrong sign posting, or errors in data acquisition in traffic sign administration software. We investigate such inconsistent traffic scenarios and formally model traffic regulations. Based on this, we consider relevant reasoning tasks including consistency testing, diagnosis, and repair, and present an implementation of the these tasks using answer set programming. The results of this research may improve existing governmental software maintaining traffic regulations.

Many tasks for autonomous agents or robots are best de- scribed by a specification of the environment and a specifi- cation of the available actions the agent or robot can perform. Combining such a specification with the possibility to imper- atively program a robot or agent is what we call the action- based imperative programming. One of the most successful such approaches is Golog. In this paper, we draft a proposal for a new robot program- ming language YAGI, which is based on the action-based imperative programming paradigm. Our goal is to design a small, portable stand-alone YAGI interpreter. We combine the benefits of a principled domain specification with a clean, small and simple programming language, which does not ex- ploit any side-effects from the implementation language. We discuss general requirements of action-based programming languages and outline YAGI, our action-based language ap- proach which particularly aims at embeddability.

Human-robot interaction poses tight timing requirements on visual as well as natural language processing in order to allow for natural human-robot interaction. In particular, humans expect robots to incrementally resolve spoken references to visually perceivable objects as the referents are verbally described. In this paper, we present an integrated robotic architecture with novel incremental vision and natural language processing and demonstrate that incrementally refining attentional focus using linguistic constraints achieves significantly better performance of the vision system compared to non-incremental visual processing.