A* is the algorithm of finding the shortest path between two nodes in a graph. When the searching problem is constituted of a set of linked graphs, A* searches solution like if it is face of one graph formed by linked graphs. While researchers have developed solutions to reduce the execution time of A* in multiple cases by multiples techniques, we develop a new algorithm: DEC-A* which is a decentralized version of A* composing a solution through a collection of graph. A* uses a distance-plus-cost heuristic function to determine the order in which the search visits nodes in the tree. Our algorithm DEC-A* extends the evaluation of the distance-plus-cost heuristic to be the sum of two functions : local distance, which evaluates the cost to reach the nearest neighbor node s to the goal, and global distance which evaluates the cost from s to the goal through other graphs. DEC-A* reduces the time of finding the shortest path and reduces the complexity, while ensuring the privacy of graphs.

In this paper we present a formal approach to reciprocal collision avoidance for multiple mobile robots sharing a common 2-D or 3-D workspace whose dynamics are subject to linear differential constraints. Our approach defines a protocol for robots to select their control input independently (i.e. without coordination with other robots) while guaranteeing collision-free motion for all robots, assuming the robots can perfectly observe each other's state. To this end, we use the concept of LQR-Obstacles that define sets of forbidden control inputs that lead a robot to collision with obstacles, and extend it for reciprocal collision avoidance among multiple robots. We implemented and tested our approach in 3-D simulation environments for reciprocal collision avoidance of quadrotorhelicopters, which have complex dynamics in 16-D state spaces. Our results suggest that our approach avoids collisions among over a hundred quadrotors in tight workspaces at real-time computation rates.

Homophily is the tendency of individuals in a social system to link to others who are similar to them and understanding homophily can help us build better user models for personalization and recommender systems. Many studies have verified homophily along demographic dimensions, such as age, location, occupation, etc., not only in real-world social networks but also online. However, there is limited research showing that homophily also exists when similarity is judged by topics of expertise or interests. We demonstrate the existence of topical homophily on Twitter using a novel source of evidence provided by Twitter lists. In this paper, we use LDA to extract topics from Twitter lists (a collection of user accounts created by some user that others can follow) and measure similarity between listed users based on the learned topics. We show that topically similar users are more likely to be linked via a follow relationship than less similar users.

A natural, common way of doing this is by crowdsourcing this stage as well, and specifically Human computation is a fast-growing field that seeks to harness letting people vote over different proposals that were the relative strengths of humans to solve problems that submitted by their peers. For example, in EteRNA thousands are difficult for computers to solve alone. The field has recently of designs are submitted each month, but only a small number been gaining traction within the AI community, as k of them can be synthesized in the lab (as of late 2011, increasingly more deep connections between AI and human k 8). To single out k designs to be synthesized, players computation are uncovered (Dai, Mausam, and Weld 2010; vote by reporting their k favorite designs, each of which is Shahaf and Horvitz 2010).

People complete tasks more quickly when they have concrete plans, especially for open-ended, creative tasks. However, people often fail to create such action plans. (How) can systems provide people with these concrete steps automatically? To scalably provide personalized action plans, this paper introduces and evaluates crowdsourcing and peer approaches for creating plans, and NLP techniques for reusing them. We evaluated the effects of action plans on different types of tasks. A between-subjects experiment found that people who received crowd-created plans completed more tasks than people asked to self-create plans and than a control group without action plans. We found that crowd-created action plans are especially effective for lingering and high-level tasks. A second experiment found that peer-provided plans led to more completed tasks than no plans. A third experiment found that participants who received reused action plans also completed more tasks than a control group without action plans. We have incorporated these principles into TaskGenies: a crowd-powered task management system.

Design tasks are notoriously difficult, because success is defined by the perception of the target audience, whose feedback is usually not available during design stages. Commonly, design is performed by professionals who have specific domain knowledge (i.e., an intuitive understanding of the implicit requirements of the task) and do not need the feedback of the perception of the viewers during the process. In this paper, we present a novel design methodology for creating minimal sketches of objects that uses an iterative optimization scheme. We define minimality for a sketch via the minimal number of straight line segments required for correct recognition by 75% of naiive viewers. Crowd-sourcing techniques allow us to directly include the perception of the audience in the design process. By joining designers and crowds, we are able to create a human computation system that can efficiently optimize sketches without requiring high levels of domain knowledge (i.e., design skills) from any worker.

In this paper, we develop some new Captchas belonging to genre – "CAPTCHAs with a purpose". These CAPTCHAs apart from having its applications serve some useful purpose. reCAPTCHA is one such Captcha developed at Carnegie Mellon University. It helps to digitize books. Another such Captcha is Asirra developed at Microsoft which provides homes for homeless animals. In this paper, we present Time based, Sentence based, Human Emotion based CAPTCHAs which have range of other useful purpose such as measuring reaction time of people, promoting news, general knowledge facts, jokes among people while engaging in routine activities such as checking email. Also, one can be used for conducting online polls on a very large scale. We also showcase a New Game with a Purpose called "Identical Emotions" which helps to assign tags describing emotions depicted by the images, to varied images. It can also be used to serve Emotion Based CAPTCHA. We also present a new scheme which renders attack on CAPTCHAs useless and make old CAPTCHAs reusable and help in using CAPTCHAs which might serve some practical purpose which otherwise might be vulnerable to use. This system also enables to use different "CAPTCHAs with a purpose" in conjunction with each other. At present most websites deploy only a single algorithm reCAPTCHA whose practical purpose is to digitize books, thus is limited to one domain. This system can thus, broaden the application domain of CAPTCHAs.

A large number of images with ground truth object bounding boxes are critical for learning object detectors, which is a fundamental task in compute vision. In this paper, we study strategies to crowd-source bounding box annotations. The core challenge of building such a system is to effectively control the data quality with minimal cost. Our key observation is that drawing a bounding box is significantly more difficult and time consuming than giving answers to multiple choice questions. Thus quality control through additional verification tasks is more cost effective than consensus based algorithms. In particular, we present a system that consists of three simple sub-tasks --- a drawing task, a quality verification task and a coverage verification task. Experimental results demonstrate that our system is scalable, accurate, and cost-effective.

To ensure quality results from crowdsourced tasks requesters often aggregate worker responses and use one of a plethora of strategies for the process of inferring the correct answer from the set of noisy responses. However, all current models assume prior knowledge of all possible outcomes of the task. While not an unreasonable assumption for tasks that can be posited as multiple-choice questions (e.g. n-ary classification), we observe that many tasks do not naturally fit this paradigm, but instead demand a free-response, generalized, formulation where the outcome space is of infinite size (e.g. audio transcription). We call these tasks open questions. We model open questions with a novel probabilistic graphical model, and design and implement LazySusan, a decision-theoretic controller that dynamically requests responses as necessary in order to infer answers to these tasks. Live experiments on Amazon Mechanical Turk demonstrate the superiority of LazySusan at solving SAT Math questions, eliminating 83.2% of the error and achieving greater net utility compared to the state-of-the-art strategy, majority voting.

With the advent of the increasingly participatory Internet and the growing power of the crowd, “Serious Games” have proven to be a fertile approach for gathering task-specific natural language data at very low cost. In this paper we outline a game we call Doodling, based on the sketch-and-convey metaphor used in the popular board game Pictionary(R), with the goal of generating useful natural language data. We explore whether such a paradigm can be successfully extended for conveying more complex syntactic and semantic constructs than the words or short phrases typically used in the board game. Through a series of user experiments, we show that this is indeed the case, and that valuable parallel language data may be produced as a byproduct. In addition, we explore extensions to this paradigm along two axes – going online (vs. face-to-face) and going cross-lingual. The results in each of the sets of experiments confirm the potential of Doodling game to generate data in large quantities and across languages, and thus provide a new means of developing data sets and technologies for resource-poor languages.