The functional and the algebraic routing problem are generalizations of the shortest path problem. This paper shows that both problems are equivalent with respect to the concept of profile searches known from time-dependent routing. Because of this, it is possible to apply various shortest path algorithms to these routing problems. This is demonstrated using contraction hierarchies as an example. Furthermore, we show how to use Cousots' concept of abstract interpretation on these routing problems generalizing the idea of routing approximations, which can be used to find approximative solutions and even to improve the performance of exact queries. The focus of this paper lies on vehicle routing while both the functional and algebraic routing models were introduced in the context of internet routing. Due to our formal combination of both fields, new algorithms abound for various specialized vehicle routing problems. We consider two major examples, namely the time-dependent routing problem for public transportation and the energy-efficient routing problem for electric vehicles.

The aim of this paper is to propose a new approach interweaving preference elicitation and search to solve multiobjective optimization problems. We present an interactive search procedure directed by an aggregation function, possibly non-linear (e.g. an additive disutility function, a Choquet integral), defining the overall cost of solutions. This function is parameterized by weights that are initially unknown. Hence, we insert comparison queries in the search process to obtain useful preference information that will progressively reduce the uncertainty attached to weights. The process terminates by recommending a near-optimal solution ensuring that the gap to optimality is below the desired threshold. Our approach is tested on multiobjective state space search problems and appears to be quite efficient both in terms of number of queries and solution times.

We propose a method to guide a Monte Carlo search in the initial moves of the game of Go. Our method matches the current state of a Go board against clusters of board configurations that are derived from a large number of games played by experts. The main advantage of this method is that it does not require an exact match of the current board, and hence is effective for a longer sequence of moves compared to traditional opening books. We apply this method to two different open-source Go-playing programs. Our experiments show that this method, through its filtering or biasing the choice of a next move to a small subset of possible moves, improves play effectively in the initial moves of a game.

Real-time strategy (RTS) games are hard from an AI point of view because they have enormous state spaces, combinatorial branching factors, allow simultaneous and durative actions, and players have very little time to choose actions. For these reasons, standard game tree search methods such as alpha- beta search or Monte Carlo Tree Search (MCTS) are not sufficient by themselves to handle these games. This paper presents an alternative approach called Adversarial Hierarchical Task Network (AHTN) planning that combines ideas from game tree search with HTN planning. We present the basic algorithm, relate it to existing adversarial hierarchical planning methods, and present new extensions for simultaneous and durative actions to handle RTS games. We also present empirical results for the μRTS game, comparing it to other state of the art search algorithms for RTS games.

At each node of the search tree, Branch and Bound solvers for Max-SAT compute the lower bound (LB) by estimating the number of disjoint inconsistent subsets (IS) of the formula. IS are detected thanks to unit propagation (UP) then transformed by max-resolution to ensure that they are counted only once. However, it has been observed experimentally that the max-resolution transformations impact the capability of UP to detect further IS. Consequently, few transformations are learned and the LB computation is redundant. In this paper, we study the effect of the transformations on the UP mechanism. We introduce the notion of UP-resiliency of a transformation, which quantifies its impact on UP. It provides, from a theoretical point of view, an explanation to the empirical efficiency of the learning scheme developed in the last ten years. The experimental results we present give evidences of UP-resiliency relevance and insights on the behavior of the learning mechanism.

In optimal planning as heuristic search, admissible pruning techniques are paramount. One idea is dominance pruning, identifying states "better than" other states. Prior approaches are limited to simple dominance notions, like "more STRIPS facts true" or "higher resource supply". We apply simulation, well-known in model checking, to compute much more general dominance relations based on comparing transition behavior across states. We do so effectively by expressing state-space simulations through the composition of simulations on orthogonal projections. We show how simulation can be made more powerful by intertwining it with a notion of label dominance. Our experiments show substantial improvements across several IPC benchmark domains.

Limited lookahead has been studied for decades in perfect-information games. This paper initiates a new direction via two simultaneous deviation points: generalization to imperfect-information games and a game-theoretic approach. The question of how one should act when facing an opponent whose lookahead is limited is studied along multiple axes: lookahead depth, whether the opponent(s), too, have imperfect information, and how they break ties. We characterize the hardness of finding a Nash equilibrium or an optimal commitment strategy for either player, showing that in some of these variations the problem can be solved in polynomial time while in others it is PPAD-hard or NP-hard. We proceed to design algorithms for computing optimal commitment strategies for when the opponent breaks ties 1) favorably, 2) according to a fixed rule, or 3) adversarially. The impact of limited lookahead is then investigated experimentally. The limited-lookahead player often obtains the value of the game if she knows the expected values of nodes in the game tree for some equilibrium, but we prove this is not sufficient in general. Finally, we study the impact of noise in those estimates and different lookahead depths. This uncovers a lookahead pathology.

Several applications including text-to-speech require some normalized format of non-standard words in various domains such as numbers, dates, and currencies and in various human languages. The traditional approach of manually constructing a program for such a normalization task requires expertise in both programming and target (human) language and further does not scale to a large number of domain, format, and target language combinations. We propose to learn programs for such normalization tasks through examples. We present a domain-specific programming language that offers appropriate abstractions for succinctly describing such normalization tasks, and then present a novel search algorithm that can effectively learn programs in this language from input-output examples. We also briefly describe domain-specific heuristics for guiding users of our system to provide representative examples for normalization tasks related to that domain. Our experiments show that weare able to effectively learn desired programs for a variety of normalization tasks.

Computing the set of optimal solutions for a multi-objective constraint optimisation problem can be computationally very challenging. Also, when solutions are only partially ordered, there can be a number of different natural notions of optimality, one of the most important being the notion of Possibly Optimal, i.e., optimal in at least one scenario compatible with the inter-objective tradeoffs. We develop an AND/OR Branch-and-Bound algorithm for computing the set of Possibly Optimal solutions, and compare variants of the algorithm experimentally.

We consider three important, non-strategyproof assignment mechanisms: Probabilistic Serial and two variants of the Boston mechanism. Under each of these mechanisms, we study the agent’s manipulation problem of determining a best response, i.e., a report that maximizes the agent’s expected utility. In particular, we consider local manipulation strategies, which are simple heuristics based on local, greedy search. We make three main contributions. First, we present results from a behavioral experiment (conducted on Amazon Mechanical Turk) which demonstrate that human manipulation strategies can largely be explained by local manipulation strategies. Second, we prove that local manipulation strategies may fail to solve the manipulation problem optimally. Third, we show via large-scale simulations that despite this non-optimality, these strategies are very effective on average. Our results demonstrate that while the manipulation problem may be hard in general, even cognitively or computationally bounded (human) agents can find near-optimal solutions almost all the time via simple local search strategies.