2426741
An analysis and application of distributed constraint satisfaction and optimization algorithms in sensor networks
This research is motivated by a distributed scheduling problem in distributed sensor networks, in which computational resources are scarce. To cope with limited computational resources and restricted real-time requirement, it is imperative to apply distributed algorithms that have low overhead on resource requirement and high anytime performance. In this paper, We study distributed stochastic algorithm (DSA) and distributed breakout algorithm (DBA), two distributed algorithms developed earlier for distributed constraint satisfaction problems. We experimentally investigate their properties and compare their performance using our distributed scheduling problem as a benchmark. We first formulate the scheduling problem as a distributed multi-coloring problem. We then experimentally show that the solution quality and communication cost of DSA exhibit phase-transition or threshold behavior, in that the performance degenerates abruptly and dramatically when the degree of parallel executions of distributed agents increases beyond some critical value. The results show that when controlled properly, DSA is superior to DBA, having better or competitive solution quality and significantly smaller communication cost than DBA. Therefore, DSA is the algorithm of choice for our distributed scan scheduling problem.
76909
Heuristic search in artificial intelligence
In February of this year, Claude E. Shannon and Herbert A. Simon passed away, both at age 84. In his 1950 paper entitled, “Programming a Computer to Play Chess” [3], Shannon laid out the theory of minimax search with bounded lookahead and static heuristic evaluation, the basis of almost all subsequent work on two-player games. Along with Allen Newell, Herbert Simon established the idea of heuristic search in a problem space as one of the fundamental paradigms of problem solving in artificial intelligence [1]. We feel a deep sorrow for the loss of these two giants of our field. Both men are also known for their deep scientific contributions to other fields as well. Shannon was the father of information and communication theory, and Simon was a founding father of organizational behavior and the information processing model of cognitive psychology. Although Simon and Shannon are no longer with us, their work continues as a source of inspiration in virtually every field they touched. We dedicate this special issue on heuristic search in artificial intelligence to Claude Shannon and Herbert Simon. Heuristic search remains as a core area of artificial intelligence (AI). The use of a good search algorithm is often a critical factor in the performance of an intelligent system. As with most areas of AI, there has been steady progress in heuristic search research over the years. This progress can be measured by several different yardsticks, including finding optimal solutions to larger problems, making higher quality decisions in fixedsize problems, handling more complex domains including dynamic environments with incomplete and uncertain information, being able to analyze and predict the performance of heuristic search algorithms, and the increasing deployment of real-world applications of search algorithms. The success of the Deep Blue Chess machine in defeating Gary Kasparov, the human world champion, in an exhibition match in 1997 was a landmark in the field of AI, the achievement of a goal that had been pursued for almost 50 years. By coincidence, this special issue contains the same number of papers as the Artificial Intelligence Journal special issue on Search and Heuristics, published in 1983. What Judea
10248617
Towards flexible teamwork in persistent teams
Teamwork is a critical capability in multi-agent environments. Many such environments mandate that the agents and agent-teams mast be persistent i.e., exist over long periods of time. Agents in such persistent teams are bound together by their long-term common interests and goals. This paper focuses on flexible teamwork in such persistent teams. Unfortunately, while previous work has investigated flexible teamwork, persistent teams remain unexplored. For flexible teamwork, one promising approach that has emerged is model-based, i.e., providing agents with general models of teamwork that explicitly specify their commitments in teamwork. Such models enable agents to autonomously reason about coordination. Unfortunately, for persistent teams, such models may lead to coordination and communication actions that while locally optimal, are highly problematic for the team's long-term goals. We present a decision-theoretic technique to enable persistent teams to overcome such limitations of the model-based approach. In particular, agents reason about expected team utilities of future team states that are projected to result from actions recommended by the teamwork model, as well as lower-cost (or higher-cost) variations on these actions. To accommodate real-time constraints, this reasoning is done in an any-time fashion. Implemented examples from an analytic search tree and some real-world domains are presented.
1196346
An Efficient Hybrid Strategy for Temporal Planning
Temporal planning (TP) is notoriously difficult because it requires to solve a propositional STRIPS planning problem with temporal constraints. In this paper, we propose an efficient strategy for solving TP, which combines, in an innovative way, several well established and studied techniques in AI, OR and constraint programming. Our approach integrates graph planning (a well studied planning paradigm), max-SAT (a constraint optimization technique), and the Program Evaluation and Review Technique (PERT), a well established technique in OR. Our method first separates the logical and temporal constraints of a TP problem and solves it in two phases. In the first phase, we apply our new STRIPS planner to generate a parallel STRIPS plan with a minimum number of parallel steps. Our new STRIPS planner is based on a new max-SAT formulation, which leads to an effective incremental learning scheme and a goal-oriented variable selection heuristic. The new STRIPS planner can generate optimal parallel plans more efficiently than the well-known SATPLAN approach. In the second phase, we apply PERT to schedule the activities in a parallel plan to create a shortest temporal plan given the STRIPS plan. When applied to the first optimal parallel STRIPS plan, this simple strategy produces optimal temporal plans on most benchmarks we have tested. This strategy can also be applied to optimal STRIPS plans of different parallel steps in an anytime fashion to find an optimal temporal plan. Our experimental results show that the new strategy is effective and the resulting algorithm outperforms many existing temporal planners.
205692410
Average-case analysis of best-first search in two representative directed acyclic graphs
Many problems that arise in the real world have search spaces that are graphs rather than trees. Understanding the properties of search algorithms and analyzing their performance have been major objectives of research in AI. But most published work on the analysis of search algorithms has been focused on tree search, and comparatively little has been reported on graph search. One of the major obstacles in analyzing average-case complexity of graph search is that no single graph can serve as a suitable representative of graph search problems. In this paper we propose one possible approach to analyzing graph search. We take two problem domains for which the search graphs are directed acyclic graphs of similar structure, and determine the average case performance of the best-first search algorithm A* on these graphs. The first domain relates to one-machine job sequencing problems in which a set of jobs must be sequenced on a machine in such a way that a penalty function is minimized. The second domain concerns the Traveling Salesman Problem. Our mathematical formulation extends a technique that has been used previously for analyzing tree search. We demonstrate the existence of a gap in computational cost between two classes of problem instances. One class has exponential complexity and the other has polynomial complexity. For the job sequencing domain we provide supporting experimental evidence showing that problems exhibit a huge difference in computational cost under different conditions. For the Traveling Salesman Problem, our theoretical results reflect on the long-standing debate on the expected complexity of branch-and-bound algorithms for solving the problem, indicating that the complexity can be polynomial or exponential, depending on the accuracy of the heuristic function used.
7867358
Phase Transitions and Backbones of the Asymmetric Traveling Salesman Problem
In recent years, there has been much interest in phase transitions of combinatorial problems. Phase transitions have been successfully used to analyze combinatorial optimization problems, characterize their typical-case features and locate the hardest problem instances. In this paper, we study phase transitions of the asymmetric Traveling Salesman Problem (ATSP), an NP-hard combinatorial optimization problem that has many real-world applications. Using random instances of up to 1,500 cities in which intercity distances are uniformly distributed, we empirically show that many properties of the problem, including the optimal tour cost and backbone size, experience sharp transitions as the precision of intercity distances increases across a critical value. Our experimental results on the costs of the ATSP tours and assignment problem agree with the theoretical result that the asymptotic cost of assignment problem is π26 as the number of cities goes to infinity. In addition, we show that the average computational cost of the well-known branch-and-bound subtour elimination algorithm for the problem also exhibits a thrashing behavior, transitioning from easy to difficult as the distance precision increases. These results answer positively an open question regarding the existence of phase transitions in the ATSP, and provide guidance on how difficult ATSP problem instances should be generated.
14422830
Compiler-guided register reliability improvement against soft errors
With the scaling of technology, transient errors caused by external particle strikes have become a critical challenge for microprocessor design. As embedded processors are widely used in reliability-sensitive environments, it becomes increasingly important to develop cost-effective techniques to improve the processor reliability against soft errors. This paper focuses on studying the register file immunity against soft errors since modern processors typically employ a large number of registers, which are accessed very frequently. As a result, soft errors occurred in registers can easily propagate to functional units or the memory system, leading to silent data error (SDC) or system crash.To develop cost-effective techniques to fight soft errors for embedded processors, the first step is to understand the register file susceptibility to soft errors and its impact on the system reliability accurately. Toward this goal, this paper proposes the concept of register vulnerability factor (RVF) to characterize the probability that register transient errors can escape the register file and thus potentially impact the system reliability. Built upon the RVF concept, we then propose two cost-effective compiler-guided techniques to improve the register file reliability by lowering the RVF value. Our experiments indicate that on average, the RVF can be reduced to 9.1% and 9.5% by the hyperblock-based instruction re-scheduling and the reliability-oriented register assignment respectively, which can potentially lower the reliability cost significantly while protecting register files against transient errors.
12895493
Improvement of HITS-based algorithms on web documents
In this paper, we present two ways to improve the precision of HITS-based algorithms on Web documents. First, by analyzing the limitations of current HITS-based algorithms, we propose a new weighted HITS-based method that assigns appropriate weights to in-links of root documents. Then, we combine content analysis with HITS-based algorithms and study the effects of four representative relevance scoring methods, VSM, Okapi, TLS, and CDR, using a set of broad topic queries. Our experimental results show that our weighted HITS-based method performs significantly better than Bharat's improved HITS algorithm. When we combine our weighted HITS-based method or Bharat's HITS algorithm with any of the four relevance scoring methods, the combined methods are only marginally better than our weighted HITS-based method. Between the four relevance-scoring methods, there is no significant quality difference when they are combined with a HITS-based algorithm.
646781
Value iteration working with belief subset
Value iteration is a popular algorithm for solving POMDPs. However, it is inefficient in practice. The primary reason is that it needs to conduct value updates for all the belief states in the (continuous) belief space. In this paper, we study value iteration working with a subset of the belief space, i.e., it conducts value updates only for belief states in the subset. We present a way to select belief subset and describe an algorithm to conduct value iteration over the selected subset. The algorithm is attractive in that it works with belief subset but also retains the quality of the generated values. Given a POMDP, we show how to <i>a priori</i> determine whether the selected subset is a <i>proper</i> subset of belief space. If this is the case, the algorithm carries the advantages of representation in space and efficiency in time.
28591822
Multicast Routing with Minimum Energy Cost and Minimum Delay in Wireless Sensor Networks
In this paper, we consider the multicast routing with minimum energy cost and minimum delay (MEMD) in wireless sensor networks under the access control scheme of Spatial Time Division Multiple Access (STDMA). We formulate and explore both MEMD multicast and ME multicast, and show that the latter is just the Maximum Leaf Spanning Tree (MLST) problem, which is NP-complete. A 2-approximation algorithm is proposed for the MLST problem through improving a known one. Based on this algorithm, an approximation algorithm is obtained for the MEMD multicast problem. To further improve the delay result, we provide another approximation algorithm for our main problem using a different approach. These algorithms are all near linear in the size of the network graph, and also are shown to have good performance by simulation results.
6822470
A Reinforcement Learning Approach to job-shop Scheduling
We apply reinforcement learning methods to learn domain-specific heuristics for job shop scheduling. A repair-based scheduler starts with a critical-path schedule and incrementally repairs constraint violations with the goal of finding a short conflict-free schedule. The temporal difference algorithm TD(λ) is applied to tram a neural network to learn a heuristic evaluation function over states. This evaluation function is used by a one-step lookahead search procedure to find good solutions to new scheduling problems. We evaluate this approach on synthetic problems and on problems from a NASA space shuttle pay load processing task. The evaluation function is trained on problems involving a small number of jobs and then tested on larger problems. The TD scheduler performs better than the best known existing algorithm for this task--Zwehen's iterative repair method based on simulated annealing. The results suggest that reinforcement learning can provide a new method for constructing high-performance scheduling systems.