Open-ended comments in teaching evaluation surveys offer rich insights into how teaching and learning processes unfold. However, large-scale analyses often rely on superficial labels, limiting their usefulness for designing effective interventions. Current Learning Analytics research has yet to fully leverage this data source to inform teaching development. In this study, we present the design and validation of a coding instrument for labeling effective and malfunctional teaching practices, based on 44 practices systematized from prior research. A panel of five experts from different parts of the world validated the content. For construct validation, two trained annotators applied the refined instrument to label 2,618 open-ended responses, and we used Exploratory Multidimensional Item Response Theory to iteratively prune the practices considered. The resulting instrument retained 21 practices linked to conceptually substantive dimensions of teaching, such as Teaching and assessment consistency, Clear content transmission, Breakdown of constructive alignment, and Lack of pedagogical support, among others. Our work contributes to LA by introducing a novel empirical data source—student-generated open-ended feedback—and a methodological framework for extracting actionable insights to support faculty development and improve teaching quality.

Bi-objective search requires computing a Pareto solution set which contains a set of paths. In real-world applications, Pareto solution sets may contain several tens or even hundreds of solutions. For a human user trying to commit to just one of these paths, navigating through a large solution set may become overwhelming, which motivates the problem of computing small, good-quality subsets of Pareto frontiers. This document presents two main contributions. First, we provide a simple formalization of good-quality subsets of a Pareto solution set. For this, we use measure of richness which has been employed in the study of Population Dynamics. Second, we propose Chebyshev BOA*, a variant of BOA* to compute good-quality subset approximations.

A well-known approach to solving Multi-Agent Path Finding (MAPF) optimally is compilation to Boolean Satisfiability or Answer Set Programming (ASP). Such compilation-based approaches are superior to other approaches on dense, relatively small instances and may invoke the solver multiple times, each with an encoding of the same instance for a different makespan. Critical to their performance is the runtime of the last solver invocation, whose input is the instance encoded with a theoretical upper bound of the makespan of the optimal solution. In this paper, we propose a new theoretical upper bound for such a last invocation. Unlike the previously known bound, when given a MAPF instance P, our bound requires a solution to P_1, a version of P where one of its agents is removed. We prove that our bound is correct and experimentally significantly tighter than the previously known bound. We propose a recursive parallel approach that allows us to exploit our new bound effectively. Our evaluation of warehouses and random MAPF benchmarks of varied sizes shows that our bound is, on average, 21.2% smaller than the previous bound. This allows for generating grounded ASP formulas around 33.45% smaller and solving 4.9% more instances.

In bi-objective search, we are given a graph in which each directed arc is associated with a pair of non-negative weights, and the objective is to find the Pareto-optimal solution set. Unfortunately, in many practical settings, this set is too large, and therefore its computation is very time-consuming. In addition, even though bi-objective search algorithms generate the Pareto set incrementally, they do so exhaustively. This means that early during search the solution set covers is not diverse, being concentrated in a small region of the solution set. To address this issue, we present a new approach to subset approximation of the solution set, that can be used as the basis for an anytime bi-objective search algorithm. Our approach transforms the given task into a target bi-objective search task using two real parameters. For each particular parameter setting, the solutions to the target task is a subset of the solution set of the original task. Depending on the parameters used, the solution set of the target task may be computed very quickly. This allows us to obtain, in challenging road map benchmarks, a rich variety of solutions in times that may be orders of magnitude smaller than the time needed to compute the solution set. We show that by running the algorithm with an appropriate sequence of parameters, we obtain a growing sequence of solutions that converges to the full solution set. We prove that our approach is correct and that Bi-Objective A* prunes at least as many nodes when run over the target task.

In Real-Time Heuristic Search (RTHS) we are given a search graph G, a heuristic, and the objective is to find a path from a given start node to a given goal node in G. As such, one does not impose any trajectory constraints on the path, besides reaching the goal. In this paper we consider a version of RTHS in which temporally extended goals can be defined on the form of the path. Such goals are specified in Linear Temporal Logic over Finite Traces (LTLf), an expressive language that has been considered in many other frameworks, such as Automated Planning, Synthesis, and Reinforcement Learning, but has not yet been studied in the context of RTHS. We propose a general automata-theoretic approach for RTHS, whereby LTLf goals are supported as the result of searching over the cross product of the search graph and the automaton for the LTLf goal; specifically, we describe LTL-LRTA*, a version of LSS-LRTA*. Second, we propose an approach to produce heuristics for LTLf goals, based on existing goal-dependent heuristics. Finally, we propose a greedy strategy for RTHS with LTLf goals, which focuses search to make progress over the structure of the automaton; this yields LTL-LRTA*+A. In our experimental evaluation over standard benchmarks we show LTL-LRTA*+A may outperform LTL-LRTA* substantially for a variety of LTLf goals.

In bi-objective search, we are given a graph in which each directed arc is associated with a pair of non-negative weights, and the objective is to find the Pareto-optimal solution set. Unfortunately, in many practical settings, this set is too large, and therefore its computation is very time-consuming. In addition, even though bi-objective search algorithms generate the Pareto set incrementally, they do so exhaustively. This means that early during search the solution set covered is not diverse, being concentrated in a small region. To address this issue, we present a new approach to subset approximation of the solution set, that can be used as the basis for an anytime bi-objective search algorithm. Our approach transforms the given task into a target bi-objective search task using two real parameters. For each particular parameter setting, the solutions to the target task is a subset of the solution set of the original task. Depending on the parameters used, the solution set of the target task may be computed very quickly. This allows us to obtain, in challenging road map benchmarks, a rich variety of solutions in times that may be orders of magnitude smaller than the time needed to compute the solution set. We show that by running the algorithm with an appropriate sequence of parameters, we obtain a growing sequence of solutions that converges to the full solution set. We prove that our approach is correct and that Bi-Objective A* prunes at least as many nodes when run over the target task.

Machine learning allows learning accurate but inadmissible heuristics for hard combinatorial puzzles like the 15-puzzle, the 24-puzzle, and Rubik's cube. In this paper, we investigate how to exploit these learned heuristics in the context of heuristic search with suboptimality guarantees. Specifically, we study how Focal Search (FS), a well-known bounded-suboptimal search algorithm can be modified to better exploit inadmissible learned heuristics. We propose to use Focal Discrepancy Search (FDS) in the context of learned heuristics, which uses a discrepancy function, instead of the learned heuristic, to sort the focal list. In our empirical evaluation, we evaluate FS and FDS using DeepCubeA, an effective learned heuristic for the 15-puzzle. We show that FDS substantially outperforms FS. This suggests that in some domains, when a highly accurate heuristics is available, one should always consider using discrepancies for better search.

Despite being very effective, learned heuristics in bounded-suboptimal search can produce heuristic plateaus or move the search to zones of the state space that do not lead to a solution. In addition, it produces inadmissible cost-to-go estimates; therefore, it cannot be exploited with classical algorithms like WA* to produce w-optimal solutions. In this paper, we present two ways in which Focal Search can be modified to exploit a learned heuristic in a bounded suboptimal search: Focal Discrepancy Search, which, to evaluate each state, uses a discrepancy score based on the best-predicted heuristic value; and K-Focal Search, which expands more than one node from the FOCAL list in each expansion cycle. Both algorithms return w-optimal solutions and explore different zones of the state space than the ones that focal search, using the learned heuristic to sort the FOCAL list, would explore.

Learned heuristics, though inadmissible, can provide very good guidance for bounded-suboptimal search. Given a single search state s and a learned heuristic h, evaluating h(s) is typically very slow relative to expansion time, since state-of-the-art learned heuristics are implemented as neural networks. However, by using a Graphics Processing Unit (GPU), it is possible to compute heuristics using batched computation. Existing approaches to batched heuristic computation are specific to satisficing search and have not studied the problem in the context of bounded-suboptimal search. In this paper, we present K-Focal Search, a bounded suboptimal search algorithm that in each iteration expands K nodes from the FOCAL list and computes the learned heuristic values of the successors using a GPU. We experiment over the Rubik's Cube domain using DeepCubeA, a very effective inadmissible learned heuristic. Our results show that K-Focal Search benefits both from batched computation and from the diversity in the search introduced by its expansion strategy. Over standard FS, it improves runtime by a factor of 6, expansions by up to three orders of magnitude, and finds better solutions, keeping the theoretical guarantees of Focal Search.

Multi-agent pathfinding (MAPF) is an NP-hard problem. As such, dense maps may be very hard to solve optimally. In such scenarios, compilation-based approaches, via Boolean satisfiability (SAT) and answer set programming (ASP), have been shown to outperform heuristic-search-based approaches, such as conflict-based search (CBS). In this paper, we propose a new Boolean encoding for MAPF, and show how to implement it in ASP and MaxSAT. A feature that distinguishes our encoding from existing ones is that swap and follow conflicts are encoded using binary clauses, which can be exploited by current conflict-driven clause learning (CDCL) solvers. In addition, the number of clauses used to encode swap and follow conflicts do not depend on the number of agents, allowing us to scale better. For MaxSAT, we study different ways in which we may combine the MSU3 and LSU algorithms for maximum performance. In our experimental evaluation, we used square grids, ranging from 20 x 20 to 50 x 50 cells, and warehouse maps, with a varying number of agents and obstacles. We compared against representative solvers of the state-of-the-art, including the search-based algorithm CBS, the ASP-based solver ASP-MAPF, and the branch-and-cut-and-price hybrid solver, BCP. We observe that the ASP implementation of our encoding, ASP-MAPF2 outperforms other solvers in most of our experiments. The MaxSAT implementation of our encoding, MtMS shows best performance in relatively small warehouse maps when the number of agents is large, which are the instances with closer resemblance to hard puzzle-like problems.

Multi-agent pathfinding (MAPF) is an NP-hard problem. As such, dense maps may be very hard to solve optimally. In such scenarios, compilation-based approaches, via Boolean satisfiability (SAT) and answer set programming (ASP), have proven to be most effective. In this paper, we propose a new encoding for MAPF, which we implement and solve using both ASP and MaxSAT solvers. Our encoding builds on a recent ASP encoding for MAPF but changes the way agent moves are encoded. This allows to represent swap and follow conflicts with binary clauses, which are known to work well along with conflict-based clause learning. For MaxSAT, we study different ways in which we may combine the MSU3 and LSU algorithms for maximum performance. Our results, over grid and warehouse maps, show that the ASP solver scales better when the number of agents is increased on grids with few obstacles, while the MaxSAT solver performs better in scenarios with more obstacles and fewer agents.

Recent machine-learning approaches to deterministic search and domain-independent planning employ policy learning to speed up search. Unfortunately, when attempting to solve a search problem by successively applying a policy, no guarantees can be given on solution quality. The problem of how to effectively use a learned policy within a bounded-suboptimal search algorithm remains largely as an open question. In this paper, we propose various ways in which such policies can be integrated into Focal Search, assuming that the policy is a neural network classifier. Furthermore, we provide mathematical foundations for some of the resulting algorithms. To evaluate the resulting algorithms over a number of policies with varying accuracy, we use synthetic policies which can be generated for a target accuracy for problems where the search space can be held in memory. We evaluate our focal search variants over three benchmark domains using our synthetic approach, and on the 15-puzzle using a neural network learned using 1.5 million examples. We observe that Discrepancy Focal Search, which we show expands the node which maximizes an approximation of the probability that its corresponding path is a prefix of an optimal path, obtains, in general, the best results in terms of runtime and solution quality.

Solving a Multi-Agent Pathfinding (MAPF) problem involves finding non-conflicting paths that lead a number of agents to their goal location. In the sum-of-costs variant of MAPF, one is also required to minimize the total number of moves performed by agents before stopping at the goal. Not surprisingly, since MAPF is combinatorial, a number of compilations to Satisfiability solving (SAT) and Answer Set Programming (ASP) exist. In this paper, we propose the first family of compilations to ASP that solve sum-of-costs MAPF over 4-connected grids. Unlike existing compilations to ASP that we are aware of, our encoding is the first that, after grounding, produces a number of clauses that is linear on the number of agents. In addition, the representation of the optimization objective is also carefully written, such that its size after grounding does not depend on the size of the grid. In our experimental evaluation, we show that our approach outperforms search- and SAT-based sum-of-costs MAPF solvers when grids are congested with agents.

In order to develop an entrepreneurial mindset in future engineers, entrepreneurial training has become a key aspect of engineering education. Following this trend, a large and prestigious engineering school in Chile designed and implemented a third-year compulsory course on technology-focused entrepreneurship. To understand how course teaching and assessment methods have benefited students in terms of self-efficacy and learning gains, a cross-sectional survey study has been conducted since 2015. Over the last four academic periods, we assessed Pre-Post self-efficacy gains and learning benefits in 1,335 students. These survey results show that students perceived positive benefits from all course teaching and assessment methods. Thus, we discuss how a core engineering course can develop an entrepreneurial mindset in a diverse population of students.

Many interesting search problems can be formulated as bi-objective search problems; for example, transportation problems where both travel distance and time need to be minimized. Multi-objective best-first search algorithms need to maintain the set of undominated paths from the start state to each state to compute a set of paths from a given start state to a given goal state (the Pareto-optimal solutions) such that no path in the set is dominated by another path in the set. Each time they find a new path to a state n, they perform a dominance check to determine whether such a path dominates any of the previously found paths to n. Existing algorithms do not perform these checks efficiently, requiring at least a full iteration over the Open list per check. In this paper, we present the first multi-objective algorithm that performs these checks efficiently. Indeed, Bi-Objective A* (BOA*)—our algorithm—requires constant time to check for dominance. Our experimental evaluation shows that BOA*is orders-of-magnitude faster than state-of-the-art search algorithms, such as NAMOA*, Bi-Objective Dijkstra, and Bidirectional Bi-Objective Dijkstra.

Grid path planning is an important problem in AI. Its understanding has been key for the development of autonomous navigation systems. An interesting and rather surprising fact about the vast literature on this problem is that only a few neighborhoods have been used when evaluating these algorithms. Indeed, only the 4- and 8-neighborhoods are usually considered, and rarely the 16-neighborhood. This paper describes three contributions that enable the construction of effective grid path planners for extended 2k-neighborhoods; that is, neighborhoods that admit 2k neighbors per state, where k is a parameter. First, we provide a simple recursive definition of the 2k-neighborhood in terms of the 2k-1-neighborhood. Second, we derive distance functions, for any k ≥ 2, which allow us to propose admissible heuristics that are perfect for obstacle-free grids, which generalize the well-known Manhattan and Octile distances. Third, we define the notion of canonical path for the 2k-neighborhood; this allows us to incorporate our neighborhoods into two versions of A*, namely Canonical A* and Jump Point Search (JPS), whose performance, we show, scales well when increasing k. Our empirical evaluation shows that, when increasing k, the cost of the solution found improves substantially. Used with the 2k-neighborhood, Canonical A* and JPS, in many configurations, are also superior to the any-angle path planner Theta* both in terms of solution quality and runtime. Our planner is competitive with one implementation of the any-angle path planner, ANYA in some configurations. Our main practical conclusion is that standard, well-understood grid path planning technology may provide an effective approach to any-angle grid path planning.

Multi-Agent Pathfinding (MAPF) over grids is the problem of finding n non-conflicting paths that lead n agents from a given initial cell to a given goal cell. Cost-optimal MAPF in addition minimizes the total number of actions performed by each agent before stopping at the goal. Being a combinatorial problem in nature, a number of compilations from MAPF to Answer Set Programming (ASP) exist. In this paper we propose a new one, which unlike existing ASP approaches (1) produces cost-optimal solutions, (2) exploits information that can be pre-computed quickly using Dijkstra's algorithm, and (3) when grounded, produces a number of clauses that grows linearly with the number of agents. In our empirical evaluation, in which we use the clasp solver, we show that our approach is superior to heuristic-search-based algorithms in various settings.

Many existing boundedly-suboptimal heuristic search algorithms are variants of best-first search. Due to memory limitations, these algorithms are unable to solve problems with extremely large search spaces. In this paper, we present a framework that allows best-first search algorithms to solve problems with such large search spaces given a (reasonable) memory bound while also preserving optimality guarantees in tree-structured search spaces. In our framework, a given algorithm is run several times. In each search episode, the algorithm expands up to a user-defined number of states. After each episode, unless the goal has been found, the heuristic values of the generated states are updated using a linear-time algorithm that preserves consistency in tree-structured search spaces. In subsequent search episodes, only the heuristic values of the states generated in the previous episode need to be kept in memory. We present experimental results where we plug A*, GBFS, and wA* into our framework to solve traveling salesman problems and compare them against benchmark linear-memory algorithms like DFBnB and wDFBnB.

In this paper, we address the problem of LTL realizability and synthesis. State of the art techniques rely on so-called bounded synthesis methods, which reduce the problem to a safety game. Realizability is determined by solving synthesis in a dual game. We provide a unified view of duality, and introduce novel bounded realizability methods via reductions to reachability games. Further, we introduce algorithms, based on AI automated planning, to solve these safety and reachability games. This is the the first complete approach to LTL realizability and synthesis via automated planning. Experiments illustrate that reductions to reachability games are an alternative to reductions to safety games, and show that planning can be a competitive approach to LTL realizability and synthesis.

Automatic synthesis of software from specification is one of the classic problems in computer science. In the last decade, significant advances have been made in the synthesis of programs from specifications expressed in Linear Temporal Logic (LTL). LTL synthesis technology is central to a myriad of applications from the automated generation of controllers for Internet of Things devices, to the synthesis of control software for robotic applications. Unfortunately, the number of existing tools for LTL synthesis is limited, and using them requires specialized expertise. In this paper we present SynKit, a tool that offers LTL synthesis as a service. SynKit integrates a RESTful API and a web service with an editor, a solver, and a strategy visualizer.

The 2k neighborhood has been recently proposed as an alternative to optimal any-angle path planning over grids. Even though it has been observed empirically that the quality of solutions approaches the cost of an optimal any-angle path as k is increased, no theoretical bounds were known. In this paper we study the ratio between the solutions obtained by an any-angle path and the optimal path in the 2kk, that generalizes previously known bounds for the 4- and 8-connected grids. We analyze two cases: when vertices of the search graph are placed (1) at the corners of grid cells, and (2) when they are located at their centers. For case (1) we obtain a suboptimality bound of 1 + 1/8k2 + O(1/k3), which is tight; for (2), however, worst-case suboptimality is a fixed value, for every k ≤ 3. Our results strongly suggests that vertices need to be placed in corners in order to obtain near-optimal solutions. In an empirical analysis, we compare theoretical and experimental suboptimality.

Most real-time heuristic search algorithms solve search problems by executing a series of episodes. During each episode the algorithm decides an action for execution. Such a decision is usually made using information gathered by running a bounded, heuristic-search algorithm. In this paper we report on a real-time search algorithm that does not use a search algorithm to choose the next action to be applied. Rather, it uses a neural network whose input is local information about the search graph, comparable to the information that would be used by a bounded search algorithm. We describe a supervised learning approach to training such a network. Our three types of maps from the Moving AI benchmarks, shows that our algorithm is, in some cases, substantially superior to algorithms that have access to the same information about the graph. One of our most important conclusions is that our extended set of features important: indeed, using features beyond the heuristic seems key to achieving good performance.

Temporally extended goals are critical to the specification of a diversity of real-world planning problems. Here we examine the problem of non-deterministic planning with temporally extended goals specified in linear temporal logic (LTL), interpreted over either finite or infinite traces. Unlike existing LTL planners, we place no restrictions on our LTL formulae beyond those necessary to distinguish finite from infinite interpretations. We generate plans by compiling LTL temporally extended goals into problem instances described in the Planning Domain Definition Language that are solved by a state-of-the-art fully observable non-deterministic planner. We propose several different compilations based on translations of LTL to (Büchi) alternating or (Büchi) non-deterministic finite state automata, and evaluate various properties of the competing approaches. We address a diverse spectrum of LTL planning problems that, to this point, had not been solvable using AI planning techniques, and do so in a manner that demonstrates highly competitive performance.

Real-time search algorithms are relevant to time-sensitive decision-making domains such as video games and robotics. In such settings, the agent is required to decide on each action under a constant time bound, regardless of the search space size. Despite recent progress, poor-quality solutions can be produced mainly due to state re-visitation. Different techniques have been developed to reduce such a re-visitation with state pruning showing promise. In this paper, we propose a novel pruning approach applicable to the wide class of real-time search algorithms. Given a local search space of arbitrary size, our technique aggressively prunes away all states in its interior, possibly adding new edges to maintain the connectivity of the search space frontier. An experimental evaluation shows that our pruning often improves the performance of a base real-time search algorithm by over an order of magnitude. This allows our implemented system to outperform state-of-the-art real-time search algorithms used in the evaluation.

The knowledge representation community has built general-purpose ontologies which contain large amounts of commonsense knowledge over relevant aspects of the world, including useful visual information, e.g.: "a ball is used by a football player", "a tennis player is located at a tennis court". Current state-of-the-art approaches for visual recognition do not exploit these rule-based knowledge sources. Instead, they learn recognition models directly from training examples. In this paper, we study how general-purpose ontologies—specifically, MIT's ConceptNet ontology—can improve the performance of state-of-the-art vision systems. As a testbed, we tackle the problem of sentence-based image retrieval. Our retrieval approach incorporates knowledge from ConceptNet on top of a large pool of object detectors derived from a deep learning technique. In our experiments, we show that ConceptNet can improve performance on a common benchmark dataset. Key to our performance is the use of the ESPGAME dataset to select visually relevant relations from ConceptNet. Consequently, a main conclusion of this work is that general-purpose commonsense ontologies improve performance on visual reasoning tasks when properly filtered to select meaningful visual relations.

Any-angle path finding on grids is an important problem with applications in autonomous robot navigation. In this paper, we show that a well-known pre-processing technique, namely subgoal graphs, originally proposed for (non any-angle) 8-connected grids, can be straightforwardly adapted to the 2k neighborhoods, a family of neighborhoods that allow an increasing number of movements (and angles) as k is increased. This observation yields a pathfinder that computes 2k-optimal paths very quickly. Compared to ANYA, an optimal true any-angle planner, over a variety of benchmarks, our planner is one order of magnitude faster while being less than 0.0005% suboptimal. Important to our planner's performance was the development of an iterative 2k heuristic, linear in k, which is also a contribution of this paper.

Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Known to outperform state-of-the-art real-time search algorithms based on Korf's Learning Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not considered as a ``true'' real-time search algorithm since it fails in non-reversible problems even it the goal is still reachable from the current state. In this paper we propose and study Time-Bounded Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose Restarting Time-Bounded Weighted A* (TB_R(WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating ``backtracking moves'' and incorporating search restarts and heuristic learning. In non-reversible problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned by Time-Bounded Weighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TB_R(WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TB_R(WA*) on the racetrack problem. We compare our algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted heuristic. A general observation is that the performance of both TB(WA*) and TB_R(WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin.

Generalized Adaptive A* (GAA*) is an incremental algorithm that replans using A* when solving goal-directed navigation problems in dynamic terrain. Immediately after each A* search, it runs an efficient procedure that updates the heuristic values of states that were just expanded by A*, making them more informed. Those updates allow GAA* to speed up subsequent A* searches. Being based on A*, it is simple to describe and communicate; however, it is outperformed by other incremental algorithms like the state-of-the-art D*Lite algorithm at goal-directed navigation. In this paper we show how GAA* can be modified to exploit more information from a previous search in addition to the updated heuristic function. Specifically, we show how GAA* can be modified to utilize the paths found by a previous A* search. Our algorithm — Multipath Generalized Adaptive A* (MPGAA*) — has the same theoretical properties of GAA* and differs from it by only a few lines of pseudocode. Arguably, MPGAA* is simpler to understand than D*Lite. We evaluate MPGAA* over various realistic dynamic terrain settings, and observed that it generally outperforms the state-of-the-art algorithm D*Lite in scenarios resembling outdoor and indoor navigation.

In moving target search, the objective is to guide a hunter agent to catch a moving prey. Even though in game applications maps are always available at developing time, current approaches to moving target search do not exploit preprocessing to improve search performance. In this paper, we propose MtsCopa, an algorithm that exploits precomputed information in the form of compressed path databases (CPDs), and that is able to guide a hunter agent in both known and partially known terrain. CPDs have previously been used in standard, fixed-target pathfinding but had not been used in the context of moving target search. We evaluated MtsCopa over standard game maps. Our speed results are orders of magnitude better than current state of the art. The time per individual move is improved, which is important in real-time search scenarios, where the time available to make a move is limited. Compared to state of the art, the number of hunter moves is often better and otherwise comparable, since CPDs provide optimal moves along shortest paths. Compared to previous successful methods, such as I-ARA*, our method is simple to understand and implement. In addition, we prove MtsCopa always guides the agent to catch the prey when possible.

Time-Bounded A* (TBA*) is a single-agent deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Although the idea underlying TBA* can be generalized to other single-agent deterministic search algorithms, little is known about the impact on performance that would result from using algorithms other than A*. In this paper we propose Time-Bounded Best-First Search (TB-BFS) a generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose restarting strategies that allow TB-BFS to solve search problems in dynamic environments. In static environments, we prove that the resulting framework allows agents to always find a solution if such a solution exists, and prove cost bounds for the solutions returned by Time-Bounded Weighted A* (TB-WA*). We evaluate the performance of TB-WA* and Time-Bounded Greedy Best-First Search (TB-GBFS). We show that in pathfinding applications in static domains, TB-WA* and TB-GBFS are not only faster than TBA* but also find significantly better solutions in terms of cost. In the context of videogame pathfinding, TB-WA* and TB-GBFS perform fewer undesired movements than TBA*. Restarting TB-WA* was also evaluated in dynamic pathfinding random maps, where we also observed improved performance compared to restarting TBA*. Our experimental results seem consistent with theoretical bounds.

Depth-First Branch and Bound (DFBnB) is an anytime algorithm for solving combinatorial optimization problems. In this paper we present a weighted version of DFBnB, wDFBnB, which incorporates standard techniques for using weights in heuristic search and offers suboptimality guarantees. Our main contribution drawn from a preliminary evaluation is the observation that wDFBnB, used along with automated or hand-crafted weight schedules, can significantly outperform DFBnB both in terms of anytime behavior and convergence to the optimal. We think this small study calls for more research on the design of automated weight schedules that could provide superior anytime performance across a wider range of domains.

Many applications, ranging from video games to dynamic robotics, require solving single-agent, deterministic search problems in partially known environments under very tight time constraints. Real-Time Heuristic Search (RTHS) algorithms are specifically designed for those applications. As a subroutine, most of them invoke a standard, but bounded, search algorithm that searches for the goal. In this paper we present FRIT, a simple approach for single-agent deterministic search problems under tight constraints and partially known environments that unlike traditional RTHS does not search for the goal but rather searches for a path that connects the current state with a so-called ideal tree T . When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and then carries out a reconnection search whose objective is to find a path between the current state and any node in T . The reconnection search is done using an algorithm that is passed as a parameter to FRIT. If such a parameter is an RTHS algorithm, then the resulting algorithm can be an RTHS algorithm. We show, in addition, that FRIT may be fed with a (bounded) complete blind-search algorithm. We evaluate our approach over grid pathfinding benchmarks including game maps and mazes. Our results show that FRIT, used with RTAA*, a standard RTHS algorithm, outperforms RTAA* significantly; by one order of magnitude under tight time constraints. In addition, FRIT(daRTAA*) substantially outperforms daRTAA*, a state-of-the-art RTHS algorithm, usually obtaining solutions 50% cheaper on average when performing the same search effort. Finally, FRIT(BFS), i.e., FRIT using breadth-first-search, obtains best-quality solutions when time is limited compared to Adaptive A* and Repeated A*. Finally we show that Bug2, a pathfinding-specific navigation algorithm, outperforms FRIT(BFS) when planning time is extremely limited, but when given more time, the situation reverses.

Many practical planning problems necessitate the generation of a plan under incomplete information about the state of the world. In this paper we propose the notion of Assumption-Based Planning. Unlike conformant planning, which attempts to find a plan under all possible completions of the initial state, an assumption-based plan supports the assertion of additional assumptions about the state of the world, often resulting in high quality plans where no conformant plan exists. We are interested in this paradigm of planning for two reasons: 1) it captures a compelling form of \emph{commonsense planning}, and 2) it is of great utility in the generation of explanations, diagnoses, and counter-examples -- tasks which share a computational core with We formalize the notion of assumption-based planning, establishing a relationship between assumption-based and conformant planning, and prove properties of such plans. We further provide for the scenario where some assumptions are more preferred than others. Exploiting the correspondence with conformant planning, we propose a means of computing assumption-based plans via a translation to classical planning. Our translation is an extension of the popular approach proposed by Palacios and Geffner and realized in their T0 planner. We have implemented our planner, A0, as a variant of T0 and tested it on a number of expository domains drawn from the International Planning Competition. Our results illustrate the utility of this new planning paradigm.

In this paper, we present a conceptually simple, easy-to-implement real-time search algorithm suitable for a priori partially known environments. Instead of performing a series of searches towards the goal, like most Real-Time Heuristic Search Algorithms do, our algorithm follows the arcs of a tree T rooted in the goal state that is built initially using the heuristic h. When the agent observes that an arc in the tree cannot be traversed in the actual environment, it removes such an arc from T and our algorithm carries out a reconnection search whose objective is to find a path between the current state and any node in T. The reconnection search need not be guided by $h$, since the search objective is not to encounter the goal. Furthermore, h need not be updated. We implemented versions of our algorithm that utilize various blind search algorithms for reconnection. We show experimentally that these implementations significantly outperform state-of-the-art real-time heuristic search algorithms for the task of pathfinding in grids. In grids, our algorithms, which do not incorporate any geometrical knowledge, naturally behaves similarly to a bug algorithm, moving around obstacles, and never returning to areas that have been visited in the past. In addition, we prove theoretical properties of the algorithm.

Incremental search algorithms, such as D* Lite, reuse information from previous searches to speed up the current search and can thus solve sequences of similar search problems faster than Repeated A*, which performs repeated A* searches. In this position paper, we study goal-directed navigation in initially unknown terrain and point out that it is currently not well understood when D* Lite runs faster than Repeated A*. In general, it appears that Repeated A* runs faster than D* Lite for easy navigation problems (where the agent reaches the goal with only a small number of searches), which means that it runs faster than D* Lite quite often in practice. We draw two conclusions, namely that incremental search algorithms need to be evaluated in more diverse testbeds to improve our understanding of their properties and that they can be improved to be more competitive for easy navigation problems.

This paper summarizes our AAMAS 2012 paper on "Time-Bounded Adaptive A*," which introduces the game time model to evaluate search algorithms in real-time settings, such as video games. It then extends the existing real-time search algorithm TBA* to path planning with the freespace assumption in initially partially or completely unknown terrain, resulting in Time-Bounded Adaptive A* (TBAA*). TBAA* needs fewer time intervals in the game time model than several state-of-the-art complete and real-time search algorithms and about the same number of time intervals as the best compared complete search algorithm, even though it has the advantage over complete search algorithms that the agent starts to move right away.

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is inaccurate compared to the actual cost to reach a solution. Early real-time search algorithms, like LRTA*, easily become trapped in those regions since the heuristic values of their states may need to be updated multiple times, which results in costly solutions. State-of-the-art real-time search algorithms, like LSS-LRTA* or LRTA*(k), improve LRTA*'s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We propose two ways in which depression avoidance can be implemented: mark-and-avoid and move-to-border. We implement these strategies on top of LSS-LRTA* and RTAA*, producing 4 new real-time heuristic search algorithms: aLSS-LRTA*, daLSS-LRTA*, aRTAA*, and daRTAA*. When the objective is to find a single solution by running the real-time search algorithm once, we show that daLSS-LRTA* and daRTAA* outperform their predecessors sometimes by one order of magnitude. Of the four new algorithms, daRTAA* produces the best solutions given a fixed deadline on the average time allowed per planning episode. We prove all our algorithms have good theoretical properties: in finite search spaces, they find a solution if one exists, and converge to an optimal after a number of trials.

In this paper we examine the general problem of generating preferred explanations for observed behavior with respect to a model of the behavior of a dynamical system. This problem arises in a diversity of applications including diagnosis of dynamical systems and activity recognition. We provide a logical characterization of the notion of an explanation. To generate explanations we identify and exploit a correspondence between explanation generation and planning. The determination of good explanations requires additional domain-specific knowledge which we represent as preferences over explanations. The nature of explanations requires us to formulate preferences in a somewhat retrodictive fashion by utilizing Past Linear Temporal Logic. We propose methods for exploiting these somewhat unique preferences effectively within state-of-the-art planners and illustrate the feasibility of generating (preferred) explanations via planning.

Heuristics used for solving hard real-time search problems have regions with depressions. Such regions are bounded areas of the search space in which the heuristic function is exceedingly low compared to the actual cost to reach a solution. Real-time search algorithms easily become trapped in those regions since the heuristic values of states in them may need to be updated multiple times, which results in costly solutions. State-of-theart real-time search algorithms like LSS-LRTA∗, LRTA∗ (k), etc., improve LRTA∗’s mechanism to update the heuristic, resulting in improved performance. Those algorithms, however, do not guide search towards avoiding or escaping depressed regions. This paper presents depression avoidance, a simple real-time search principle to guide search towards avoiding states that have been marked as part of a heuristic depression. We apply the principle to LSS-LRTA ∗ producing aLSS-LRTA∗, a new real-time search algorithm whose search is guided towards exiting regions with heuristic depressions. We show our algorithm outperforms LSS-LRTA∗ in standard real-time benchmarks. In addition we prove aLSS-LRTA∗ has most of the good theoretical properties of LSS-LRTA∗.

Real-time search is a well known approach to solving search problems under tight time constraints. Recently, it has been shown that LSS-LRTA∗ , a well-known real-time search algorithm, can be improved when search is actively guided away of depressions. In this paper we investigate whether or not RTAA∗ can be improved in the same manner. We propose aRTAA∗ and daRTAA∗ , two algorithms based on RTAA∗ that avoid heuristic depressions. Both algorithms outperform RTAA∗ on standard path-finding tasks, obtaining better-quality solutions when the same time deadline is imposed on the duration of the planning episode. We prove, in addition, that both algorithms have good theoretical properties.

A number of logical languages have been proposed to represent the dynamics of the world. Among these languages, the Situation Calculus (McCarthy and Hayes 1969 McCarthy J. Hayes P. J. 1969 Some philosophical problems from the standpoint of artificial intelligence In B. Meltzer and D. Michie (eds) Machine Intelligence 4 Edinburgh Edinburgh University Press pp. 463–502 [Google Scholar]) has gained great popularity. The GOLOG programming language (Levesque et al. 1997 Levesque, H. J., Reiter, R., Lespérance, Y., Lin, F. and Scherl, R. B. 1997. Golog: logic programming languge for dynamic domains. The Journal of Logic Programming, 31: 59–84. [Crossref], [Web of Science ®] , [Google Scholar], Giacomo et al. 2000 Giacomo G. D. Lespérance Y. Levesque H. 2000 ConGolog, a concurrent programming language based on the situation calculus: foundations Artificial Intelligence 121 1–2 109 169 Available online: http://www.cs.toronto.edu/cogrobo/Papers/ConGologLang.ps.gz [Crossref] , [Google Scholar]) has been proposed as a high-level agent programming language whose semantics is based on the Situation Calculus. For efficiency reasons, high-level agent programming privileges programs over plans; therefore, GOLOG programs do not consider planning. This article presents algorithms that generate conditional GOLOG programs in a Situation Calculus extended with uncertainty of the effects of actions and complete observability of the world. Planning for contingencies is accomplished through two kinds of plan refinement techniques. The refinement process successively increments the probability of achievement of candidate plans. Plans with loops are generated under certain conditions.