Incremental search techniques find optimal solutions to series of similar search tasks much faster than is possible by solving each search task from scratch. While researchers have developed incremental versions of uninformed search methods, we develop an incremental version of A*. The first search of Lifelong Planning A* is the same as that of A* but all subsequent searches are much faster because it reuses those parts of the previous search tree that are identical to the new search tree. We then present experimental results that demonstrate the advantages of Lifelong Planning A* for simple route planning tasks.

If the promise of computational modeling is to be fully realized in higherlevel cognitivedomains such as language processing, principled methods must be developed to construct the semantic representations used in such models. In this paper, we propose the use of an established formalism from mathematical psychology, additive clustering, as a means of automatically constructingbinary representations for objects using only pairwise similarity data. However, existing methods for the unsupervised learning of additive clustering models do not scale well to large problems. Wepresent a new algorithm for additive clustering, based on a novel heuristic technique for combinatorial optimization. The algorithm is simpler than previous formulations and makes fewer independence assumptions. Extensiveempirical tests on both human and synthetic data suggest that it is more effective than previous methods and that it also scales better to larger problems. By making additive clustering practical, we take a significant step toward scaling connectionist models beyond hand-coded examples.

The problem of searching for information in networks like the World Wide Web can be approached in a variety of ways, ranging from centralized indexing schemes to decentralized mechanisms that navigate the underlying network without knowledge of its global structure. The decentralized approach appears in a variety of settings: in the behavior of users browsing the Web by following hyperlinks; in the design of focused crawlers [4, 5, 8] and other agents that explore the Web's links to gather information; and in the search protocols underlying decentralized peer-to-peer systems suchas Gnutella [10], Freenet [7], and recent research prototypes [21, 22, 23], through which users can share resources without a central server. In recent work, we have been investigating the problem of decentralized search in large information networks [14, 15]. Our initial motivation was an experiment that dealt directly with the search problem in a decidedly pre-Internet context: Stanley Milgram's famous study of the small-world phenomenon [16, 17]. Milgram was seeking to determine whether most pairs of people in society were linked by short chains of acquaintances, and for this purpose he recruited individuals to try forwarding a letter to a designated "target" through people they knew on a firstname basis.The starting individuals were given basic information about the target -- his name, address, occupation, and a few other personal details -- and had to choose a single acquaintance to send the letter to, with goal of reaching the target as quickly as possible; subsequent recipients followed the same procedure, and the chain closed in on its destination. Of the chains that completed, the median number of steps required was six -- a result that has since entered popular culture as the "six degrees of separation" principle [11]. Milgram's experiment contains two striking discoveries -- that short chains are pervasive, and that people are able to find them. This latter point is concerned precisely with a type of decentralized navigation in a social network, consisting of people as nodes and links joining pairs of people who know each other. From an algorithmic perspective, it is an interesting question to understand the structure of networks in which this phenomenon emerges -- in which message-passing with purely local information can be efficient.

The staff scheduling problem is a critical problem in the call center (or, more generally, customer contact center) industry. This article describes DIRECTOR, a staff scheduling system for contact centers. DIRECTOR is a constraint-based system that uses AI search techniques to generate schedules that satisfy and optimize a wide range of constraints and service-quality metrics. DIRECTOR has successfully been deployed at more than 800 contact centers, with significant measurable benefits, some of which are documented in case studies included in this article.

This paper presents an approach to expert-guided subgroup discovery. The main step of the subgroup discovery process, the induction of subgroup descriptions, is performed by a heuristic beam search algorithm, using a novel parametrized definition of rule quality which is analyzed in detail. The other important steps of the proposed subgroup discovery process are the detection of statistically significant properties of selected subgroups and subgroup visualization: statistically significant properties are used to enrich the descriptions of induced subgroups, while the visualization shows subgroup properties in the form of distributions of the numbers of examples in the subgroups. The approach is illustrated by the results obtained for a medical problem of early detection of patient risk groups.

This allows for the representation and exact solution of a wide range of problems in which transitions or rewards vary over time. We examine problems based on route planning with public transportation andtelescope observation scheduling. 1 Introduction Imagine trying to plan a route from home to work that minimizes expected time. One approach is to use a tool such as "Mapquest", which annotates maps with information about estimated driving time, then applies a standard graph-search algorithm to produce a shortest route. Even if driving times are stochastic, the annotations canbe expected times, so this presents no additional challenge. However, consider what happens if we would like to include public transportation in our route planning. Buses, trains, and subways vary in their expected travel time according to the time of day: buses and subways come more frequently during rush hour; trains leave on or close to scheduled departure times. In fact, even highway driving times vary with time of day, with heavier traffic and longer travel times during rush hour.

In this article, I describe agent-centered search (also called real-time search or local search) and illustrate this planning paradigm with examples. Agent-centered search methods interleave planning and plan execution and restrict planning to the part of the domain around the current state of the agent, for example, the current location of a mobile robot or the current board position of a game. These methods can execute actions in the presence of time constraints and often have a small sum of planning and execution cost, both because they trade off planning and execution cost and because they allow agents to gather information early in nondeterministic domains, which reduces the amount of planning they have to perform for unencountered situations. Agent-centered search methods have been applied to a variety of domains, including traditional search, strips-type planning, moving-target search, planning with totally and partially observable Markov decision process models, reinforcement learning, constraint satisfaction, and robot navigation.

In this article, I describe agent-centered search (also called real-time search or local search) and illustrate this planning paradigm with examples. Agent-centered search methods interleave planning and plan execution and restrict planning to the part of the domain around the current state of the agent, for example, the current location of a mobile robot or the current board position of a game. These methods can execute actions in the presence of time constraints and often have a small sum of planning and execution cost, both because they trade off planning and execution cost and because they allow agents to gather information early in nondeterministic domains, which reduces the amount of planning they have to perform for unencountered situations. These advantages become important as more intelligent systems are interfaced with the world and have to operate autonomously in complex environments. Agent-centered search methods have been applied to a variety of domains, including traditional search, strips-type planning, moving-target search, planning with totally and partially observable Markov decision process models, reinforcement learning, constraint satisfaction, and robot navigation. I discuss the design and properties of several agent-centered search methods, focusing on robot exploration and localization.

This general planner implements a scheduler that tries different variants concurrently with different (time) resource bounds. We also describe how hsp2.0 can be used as an optimal (and near-optimal) planning algorithm and compare its performance with two other optimal planners, stan and blackbox.

In Shannon's time, it would have seemed Around this time, Arthur Samuel began work the capabilities of computational intelligence. By 1958, Alan Newell and Herb Simon the game world with the real world--the game had begun their investigations into chess, of life--where the rules often change, the which eventually led to fundamental results scope of the problem is almost limitless, and for AI and cognitive science (Newell, Shaw, and the participants interact in an infinite number Simon 1958). An impressive lineup to say the of ways. Games can be a microcosm of the real least! Indeed, one of the early goals of AI was to and chess programs could play at a build a program capable of defeating the level comparable to the human world champion. This These remarkable accomplishments are the challenge proved to be more difficult than was result of a better understanding of the anticipated; the AI literature is replete with problems being solved, major algorithmic optimistic predictions. It eventually took insights, and tremendous advances in hardware almost 50 years to complete the task--a technology. The work on computer remarkably short time when one considers the games has been one of the most successful and software and hardware advances needed to visible results of AI research. The results are truly of the progress in building a world-class amazing. Even though there is an exponential program for the game is given, along with a difference between the best case and the brief description of the strongest program. The histories are necessarily case (Plaat et al. 1996). Games reports the past successes where computers realizing the lineage of the ideas.