We study the computational complexity of optimal bribery and manipulation schemes for sports tournaments with uncertain information: cup; challenge or caterpillar; and round robin. Our results carry over to the equivalent voting rules: sequential pair-wise elections, cup, and Copeland, when the set of candidates is exactly the set of voters. This restriction creates new difficulties for most existing algorithms. The complexity of bribery and manipulation are well studied, almost always assuming deterministic information about votes and results. We assume that for candidates i and j the probability that i beats j and the costs of lowering each probability by fixed increments are known to the manipulators. We provide complexity analyses for cup, challenge, and round robin competitions ranging from polynomial time to NP^PP. This shows that the introduction of uncertainty into the reasoning process drastically increases the complexity of bribery problems in some instances.

Most of preference representation languages developed in the literature are based on comparative preference statements. The latter offer a simple and intuitive way for expressing preferences. They can be interpreted following different semantics. This paper presents a postulate-based analysis of the different semantics describing their behavior w.r.t. three criteria: coherence, syntax independence and inference.

Decision making has proposed multiple methods to help the decision maker in his analysis, by suggesting ways of formalization of the preferences as well as the assessment of the uncertainties. Although these techniques are established and proven to be mathematically sound, experience has shown that in certain situations we tend to avoid the formal approach by acting intuitively. Especially, when the decision involves a large number of attributes and outcomes, and where we need to use pragmatic and heuristic simplifications such as considering only the most important attributes and omitting the others. In this paper, we provide a model for decision making in situations subject to a large predictive uncertainty with a small learning sample. The high predictive uncertainty is concretized by a countably infinite number of prospects, making the preferences assessment more difficult. Our main result is an extension of the Maximum Entropy utility (MEU) principle into an asymptotic maximum entropy utility principle for preferences elicitation. This will allow us to overcome the limits of the existing MEU method to the extend that we focus on utility assessment when the set of the available discrete prospects is countably infinite. Furthermore, our proposed model can be used to analyze situations of high-cognitive load as well as to understand how humans handle these problems under Ceteris Paribus assumption.

Markov logic networks have been successfully applied to many problems in AI. However, the computational complexity of the inference procedures has limited their application. Previous work in lifted inference, lazy inference and cutting plane inference has identified cases where the entire ground network need not be constructed. These approaches are specific to particular inference procedures, and apply well only to certain classes of problems. We introduce a method of focused grounding that can use either general purpose or domain specific heuristics to produce only the most relevant ground formulas. Though a solution to the focused grounding is not, in general, a solution to the complete grounding, we show empirically that the smaller search space of a focused grounding makes it easier to locate a good solution. We evaluate focused grounding on two diverse domains, joint entity resolution and abductive plan recognition. We show improved results and decreased computation cost for the entity resolution domain relative to a complete grounding. Focused grounding in abductive plan recognition produces state of the art results in a domain where complete grounding proved intractable.

While delivering snacks, Snackbot’s need to actively engage in conversation with the customers and other individuals, provides an approach for verbal interaction. This paper addresses the verbal human-robot interaction between humans and robots using a speech recognizer named Sphinx-4. Sphinx-4, written entirely in Java is capable of recognizing predetermined words and sentences. Thereby, allowing robots to actively engage in conversations using spoken language.

Determining the position of a robot in an environment, termed localization, is one of the challenges facing roboticist. Localization is essential to solving more complex problems such as locomotion, path planning and environmental learning. Our lab is developing a multi-agent system to use multiple small robots to accomplish tasks normally completed by larger robots. However, because of the reduced size of these robots, methods previously used to determine the position of the robot, such as GPS, cannot be employed. The problem we are facing is that we need to be able to determine the position of each of the robots in this multi-agent system simultaneously. We have developed a system to help track and identify robots using an overhead camera and LEDs, mounted on the robots, to efficiently solve the localization problem.

Mobile robots are becoming more relevant and an essential part of our everyday lives. They are increasingly taking their place in service-oriented applications including domestic and entertainment roles. They are beginning to open up many potential opportunities, but they still come with challenges in terms of their limited sensing capability and accuracy. In this project, we addressed these fundamental problems with mobile robotics and demonstrate our approach to each of the problems with a mobile robot equipped with low-cost and low-end devices. The r-one swarm robot is a low-cost multi-robot systems platform that is advanced enough for multi-robot research, robust enough for undergraduate and graduate education and cheap enough for K-12 outreach. As robots become more and more useful, multiple robots working together on a single task will become commonplace. Many of the most useful applications of robots are particularly well-suited to this “swarm” approach. Groups of robots can perform these tasks more efficiently, and can perform them in fundamentally different ways than robots working individually. However, swarms of robots are difficult to program and coordinate.

Children with cerebral palsy have difficulty moving their hands and muscles due to developmental issues. One way to assist these children is by having them participate in physical therapy. The best form of physical therapy for children is playing. Playing is a natural activity for children, and it also helps in furthering the developments of muscles. This form of therapy is perhaps a greater choice for children because it keeps the child engaged due to the interest the child holds in the activity. By integrating two projects done by previous students, a Pleo that is controlled by a Wii Nunchuk will be able to teach Pleo how to dance. The child will be engaged in this activity for long durations because there are many variations of dance that the Pleo can learn by moving many body parts. Children using this toy will have continuous movement in their arm muscles by moving the Nunchuk for the duration of the activity. This toy will not only help children with severe disabilities feeling equal to their non-disabled peers by allowing them to use controllers found on many game consoles, but it will also enhance the child’s self-esteem and confidence by allowing them to control the outcome of the Pleo.

In recent years there has been a significant decline in the number of college students choosing majors in computer science or technology related fields. Although this trend is beginning to turn around at the undergraduate level, there remains disparity in the number of under-represented minority students who earn graduate degrees as compared to majority students. Additionally, within the United States, there is an achievement gap between under-represented minority students and majority students at a time when underrepresented groups are becoming an increasing proportion of the national labor force. This reluctance to study Science, Technology, Engineering, and Mathematics (STEM) disciplines must be confronted and changed if the United States is to maintain a competitive position within the global market. Effective use of learning technologies is vital to solving many of our current STEM learning challenges. Robotics is a growing research area in computer science education. We use robotics as a technology tool captivate and engage students in research in robotics.

Calliope is an open source mobile robot designed in the Tekkotsu Lab at Carnegie Mellon University in collaboration with RoPro Design, Inc. The Calliope5SP model features an iRobot Create base, an ASUS netbook, a 5-degree of freedom arm with a gripper with two independently controllable fingers, and a Sony PlayStation Eye camera and Robotis AX-S1 IR rangefinder on a pan/tilt mount. We use chess as a test of Calliope’s abilities. Since Calliope is a mobile platform we consider how problems in vision and localization directly impact the performance of manipulation. Calliope’s arm is too short to reach across the entire chessboard. The robot must therefore navigate to a location that provides the best position to access the pieces it wants to move. The robot proved capable of performing small-scale manipulation tasks that require careful positioning.