Will we see autonomous humanoid robots that play (and win) soccer against the human soccer world champion in the year 2050? This question is not easy to answer, and the idea is quite visionary. However, this is the goal of the RoboCup Federation. There are serious research questions that have to be tackled behind the scenes of a soccer game: perception, decision making, action selection, hardware design, materials, energy, and more. RoboCup is also about the nature of intelligence, and playing soccer acts as a performance measure of systems that contain artificial intelligence -- in much the same way chess has been used over the last century. This article outlines the current situation following 10 years of research with reference to the results of the 2006 World Championship in Bremen, Germany, and discusses future challenges.

Customer service is defined as the ability of a company to afford the service requestor with the expressed need. Due to the increasing importance of service offerings as a revenue source and increasing competition among service providers, it is important for companies to optimize both the customer experience as well as the associated cost of providing the service. For more complex interactions with higher value, mixed-initiative systems provide an avenue that gives a good balance between the two goals. This article describes a mixed-initiative system that was created to improve customer support for problems customers encountered with their appliances. The tool helped call takers solve customers' problems by suggesting questions aiding the diagnosis of these problems. The mixed-initiative system improved the correctness of the diagnostic process, the speed of the process, and user satisfaction. The tool has been in use since 1999 and has provided more than $50 million in financial benefits by increasing the percentage of questions that could be answered without sending a field service technician to the customers' homes. Another mixed-initiative tool, for answering e-mail from customers, was created in 2000.

DiamondHelp is a generic collaborative task guidance system motivated by the current usability crisis in high-tech home products. It combines an application-independent conversational interface (adapted from online chat programs) with an application-specific direct-manipulation interface. DiamondHelp is implemented in Java and uses Collagen for representing and using task models.

We describe an intelligent personal assistant that has been developed to aid a busy knowledge worker in managing time commitments and performing tasks. The design of the system was motivated by the complementary objectives of (1) relieving the user of routine tasks, thus allowing her to focus on tasks that critically require human problem-solving skills, and (2) intervening in situations where cognitive overload leads to oversights or mistakes by the user. The system draws on a diverse set of AI technologies that are linked within a Belief-Desire-Intention (BDI) agent system. Although the system provides a number of automated functions, the overall framework is highly user centric in its support for human needs, responsiveness to human inputs, and adaptivity to user working style and preferences.

Mixed-initiative systems are a popular approach to building intelligent systems that can collaborate naturally and effectively with people. But true collaborative behavior requires an agent to possess a number of capabilities, including reasoning, communication, planning, execution, and learning. We describe an integrated approach to the design and implementation of a collaborative problem-solving assistant based on a formal theory of joint activity and a declarative representation of tasks. This approach builds on prior work by us and by others on mixed-initiative dialogue and planning systems.

Mixed-initiative assistants are agents that interact seamlessly with humans to extend their problem-solving capabilities or provide new capabilities. Developing such agents requires the synergistic integration of many areas of AI, including knowledge representation, problem solving and planning, knowledge acquisition and learning, multiagent systems, discourse theory, and human-computer interaction. This paper introduces seven aspects of mixed-initiative reasoning (task, control, awareness, communication, personalization, architecture, and evaluation) and discusses them in the context of several state-of-the-art mixed-initiative assistants. The goal is to provide a framework for understanding and comparing existing mixed-initiative assistants and for developing general design principles and methods.

A major achievement of mechanism design theory is a general method for the construction of truthful mechanisms called VCG (Vickrey, Clarke, Groves). When applying this method to complex problems such as combinatorial auctions, a difficulty arises: VCG mechanisms are required to compute optimal outcomes and are, therefore, computationally infeasible. However, if the optimal outcome is replaced by the results of a sub-optimal algorithm, the resulting mechanism (termed VCG-based) is no longer necessarily truthful. The first part of this paper studies this phenomenon in depth and shows that it is near universal. Specifically, we prove that essentially all reasonable approximations or heuristics for combinatorial auctions as well as a wide class of cost minimization problems yield non-truthful VCG-based mechanisms. We generalize these results for affine maximizers. The second part of this paper proposes a general method for circumventing the above problem. We introduce a modification of VCG-based mechanisms in which the agents are given a chance to improve the output of the underlying algorithm. When the agents behave truthfully, the welfare obtained by the mechanism is at least as good as the one obtained by the algorithm's output. We provide a strong rationale for truth-telling behavior. Our method satisfies individual rationality as well.

The judicious use of abstraction can help planning agents to identify key interactions between actions, and resolve them, without getting bogged down in details. However, ignoring the wrong details can lead agents into building plans that do not work, or into costly backtracking and replanning once overlooked interdependencies come to light. We claim that associating systematically-generated summary information with plans' abstract operators can ensure plan correctness, even for asynchronously-executed plans that must be coordinated across multiple agents, while still achieving valuable efficiency gains. In this paper, we formally characterize hierarchical plans whose actions have temporal extent, and describe a principled method for deriving summarized state and metric resource information for such actions. We provide sound and complete algorithms, along with heuristics, to exploit summary information during hierarchical refinement planning and plan coordination. Our analyses and experiments show that, under clearcut and reasonable conditions, using summary information can speed planning as much as doubly exponentially even for plans involving interacting subproblems.

Though attention to evaluating human-robot interfaces has increased in recent years, there are relatively few reports of using evaluation tools during the development of humanrobot interaction (HRI) systems to improve their designs. Heuristic evaluation is a technique suitable for such applications that has become popular in the humancomputer interaction (HCI) community. However, it requires usability heuristics applicable to the system environment. This work contributes a set of heuristics appropriate for use with HRI systems, derived from a variety of sources both in and out of the HRI field. Evaluators have successfully used the heuristics on an HRI system, demonstrating their utility against standard measures of heuristic effectiveness.

Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering, and min-cost covering problems, outperforming previous algorithms by several orders of magnitude with respect to runtime on some classes of hard, random problem instances. For the bin packing problem, we demonstrate significant improvements compared to most previous results, but show that bin completion is not competitive with current state-of-the-art cutting-stock based approaches.