Structure Of Intelligent Agents 12. Types of agent program 13. Goal based Agents 14. Utility-based agents 15.

Akihiro Kishimoto is a research staff member at IBM Research – Ireland working on a range of projects in artificial intelligence, parallel and distributed computing and search. His interest in these technical fields grew from his passion for board games. And while a student at the University of Tokyo, he and three of his fellow classmates designed ISshogi, a program to play the incredibly complex (and ancient) Japanese board game, Shogi. ISshogi won the World Computer Shogi Championships four times from 1997-2005. While studying AI at the University of Alberta, Akihiro was a member of the GAMES group (Game-playing, Analytical methods, Minimax search and Empirical Studies) in the Department of Computing Science, and worked with Jonathan Schaeffer and others to solve Checkers.

Recent work has raised the challenge of efficient automated troubleshooting in domains where repairing a set of components in a single repair action is cheaper than repairing each of them separately. This corresponds to cases where there is a non-negligible overhead to initiating a repair action and to testing the system after a repair action. The problem can be formalized as a combinatorial search problem, propose a new objective function to optimize, and investigate several search frameworks to solve it. The resulting search space is not monotone, but we are able to devise an admissible heuristic for it that enables solving it optimally in some cases with A*. Empirical evaluation on standard model-based diagnosis benchmark systems compare the A*-based approach with other search algorithms

Bidirectional search algorithms interleave a search forward from the start state (start ) and a search backward (i.e. using reverse operators) from the goal state (goal). We say that the two searches “meet in the middle” if neither search expands a node whose g-value (in the given direction) exceeds C*/2 , where C* is the cost of an optimal solution. The only bidirectional heuristic search algorithm that is guaranteed to meet in the middle under all circumstances is the recently introduced MM algorithm (Holte et al. 2016). The feature of MM that provides this guarantee is its unique priority functions for nodes on its open lists. In this short note we present MMe, which enhances MM’s priority function and is expected to expand fewer nodes than MM under most circumstances. We sketch a proof of MMe’s correctness, describe conditions under which MMe will expand fewer nodes than MM and vice versa, and experimentally compare MMe and MM on the 10-Pancake problem.

Many real-world planning problems are best modeled as infinite search space problems, using numeric fluents. Unfortunately, most planners and planning heuristics do not directly support such fluents. We propose a search space abstraction technique that compiles a planning problem with numeric fluents into a finite state propositional planning problem. To account for the loss of precision resulting from the abstraction, we leverage a policy repair technique used for non-deterministic planning. We evaluate our approach on a set of benchmarks and compare it to state-of-the-art planners that deal with numeric fluents.

Many AI systems, such as robots, must plan under time constraints. The most popular search approach applied in robotics so far is anytime search, in which the algorithm quickly finds a suboptimal plan, and then continues to find better and better plans as time passes, until eventually converging on an optimal plan. However, the time until the first plan is returned is not controllable, so such methods inherently involve idling the system's operation before `real' execution can begin. Real-time search methods provide hard real-time bounds on action selection time, yet to our knowledge, they have not yet been demonstrated for robotic systems. In this work, we compare anytime and real-time heuristic search methods in their ability to allow agents to achieve goals quickly.Our results suggest that real-time search is more broadly applicable and often achieves goals faster than anytime search, while anytime search finds shorter plans and does not suffer from dead-ends.

We observed that Conjunctive Normal Form (CNF) encodings of structured SAT instances often have a set of consecutive clauses defined over a small number of Boolean variables. To exploit the pattern, we propose a transformation of CNF to an alternative representation, Conjunctive Minterm Canonical Form (CMCF). The transformation is a two-step process: CNF clauses are first partitioned into disjoint subsets such that each subset contains CNF clauses with shared Boolean variables. CNF clauses in each subset are then replaced by Minterm Canonical Form (i.e., partial solutions), which is found by enumeration. We show empirically that a simple Stochastic Local Search (SLS) solver based on CMCF can consistently achieve a higher success rate using fewer evaluations than the SLS solver WalkSAT on two representative classes of structured SAT problems.

Heuristic search is a core area of Artificial Intelligence with applications to planning, scheduling and game playing. Real-time heuristic search applies to search problems where plan execution needs to start before a complete solution can be computed. Since the inception of real-time heuristic search in the early 1990s a great number of algorithms have been proposed and evaluated. In this paper we break them down into building blocks and conduct a search in the space of such building blocks. Even simple tabulated and iterative searches find new real-time heuristic search algorithms outperforming manually crafted contemporary algorithms.

Machine teaching (MT) studies the task of designing a training set. Specifically, given a learner (e.g., an artificial neural network or a human) and a target model, a teacher aims to create a training set which results in the target model being learned. MT applications include optimal education design for human learners and computer security where adversaries aim to attack learning-based systems. In this work, we formulate pool-based MT as a state space search problem. We discuss the properties and challenges of the resulting problem and highlight opportunities for novel search techniques. In our preliminary study we use a beam search approach, and find that training and evaluating empirical risk of models dominate the run time of the search. Toward the goal of better search techniques for future work, we develop optimizations ranging from implementation details for specific learners to algorithm changes applicable to general blackbox learners. We conclude with a discussion of open problems and research directions.

The task of determining which LEGO bricks to use to construct a volume is known as the LEGO Construction Problem. This is a challenging problem because even small volumes can be constructed in a tremendously large number of ways. As a result, an exhaustive search is impractical, and more nuanced search strategies must be employed to find a good, though not necessarily optimal, solution. This paper describes a multi-phase search approach to the LEGO Construction Problem. Our first search phase uses heuristics to identify a moderate number of candidates for each layer in the model. This is followed by two different search strategies which identify alternative brick arrangements that reduce the number of connected components, undesirable edges, and bricks in the model. A final highly localized search is applied to bricks at the boundaries between the model's connected components if the previous search processes fail to reduce the model to a single connected component. Applying this four-phase search strategy to a diverse selection of models has demonstrated that it normally finds a result that consists of a single connected component when such a solution exists, and that the models are structurally sound when built.