Browsing by Author "Hernandez, Carlos"

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    Avoiding and Escaping Depressions in Real-Time Heuristic Search
    (AI ACCESS FOUNDATION, 2012) Hernandez, Carlos; Baier, Jorge A.
    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.
  • Thumbnail Image
    Item
    Fast Algorithm for Catching a Prey Quickly in Known and Partially Known Game Maps
    (2015) Baier Aranda, Jorge Andrés; Botea, Adi; Harabor, Daniel; Hernandez, Carlos
  • No Thumbnail Available
    Item
    Reconnection with the Ideal Tree: A New Approach to Real-Time Search
    (2014) Rivera, Nicolas; Illanes, Leon; Baier, Jorge A.; Hernandez, Carlos
    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.
  • Thumbnail Image
    Item
    Respiratory Mites (Orthohalarachne diminuata) and beta-hemolytic Streptococci-Associated Bronchopneumonia Outbreak in South American Fur Seal Pups (Arctocephalus australis)
    (WILDLIFE DISEASE ASSOC, INC, 2018) Seguel, Mauricio; Gutierrez, Josefina; Hernandez, Carlos; Montalva, Felipe; Verdugo, Claudio
    Although mites of the Orthohalarachne genus are common parasites of otariids, their role as agents of disease and in causing population-level mortality is unknown. In the austral summer of 2016, there was an increase in mortality among South American fur seal (Arctocephalus australis) pups at Guafo Island, Northern Chilean Patagonia. Pups found dead or terminally ill had moderate to marked, multifocal, mucopurulent bronchopneumonia associated with large numbers of respiratory mites (Orthohalarachne diminuata) and rare Gram-positive cocci. In lung areas less affected by bronchopneumonia, acute interstitial pneumonia with marked congestion and scant hemorrhage was evident. Bacteria from pups dying of bronchopneumonia were isolated and identified as Streptococcus marimammalium and Streptococcus canis. Respiratory mites obstructed airflow, disrupted airway epithelial lining, and likely facilitated the proliferation of pathogenic b-hemolytic streptococci, leading to severe bronchopneumonia and death of fur seal pups. An abrupt increase in sea surface temperature in Guafo Island corresponded to the timing of the bronchopneumonia outbreak. The potential role of environmental factors in the fur seal pup mortality warrants further study.
  • No Thumbnail Available
    Item
    Simple and efficient bi-objective search algorithms via fast dominance checks
    (2023) Hernandez, Carlos; Yeoh, William; Baier, Jorge A.; Zhang, Han; Suazo, Luis; Koenig, Sven; Salzman, Oren
    Many interesting search problems can be formulated as bi-objective search problems, that is, search problems where two kinds of costs have to be minimized, for example, travel distance and time for transportation problems. Instead of looking for a single optimal path, we compute a Pareto-optimal frontier in bi-objective search, which is a set of paths in which no two paths dominate each other. Bi-objective search algorithms perform dominance checks each time a new path is discovered. Thus, the efficiency of these checks is key to performance. In this article, we propose algorithms for two kinds of bi-objective search problems. First, we consider the problem of computing the Pareto-optimal frontier of the paths that connect a given start state with a given goal state. We propose Bi-Objective A* (BOA*), a heuristic search algorithm based on A*, for this problem. Second, we consider the problem of computing one Pareto-optimal frontier for each state s of the search graph, which contains the paths that connect a given start state with s. We propose Bi-Objective Dijkstra (BOD), which is based on BOA*, for this problem. A common feature of BOA* and BOD is that all dominance checks are performed in constant time, unlike the dominance checks of previous algorithms. We show in our experimental evaluation that both BOA* and BOD are substantially faster than state-of-the-art bi-objective search algorithms. (c) 2022 Published by Elsevier B.V.
  • No Thumbnail Available
    Item
    The 2k Neighborhoods for Grid Path Planning
    (2020) Rivera, Nicolas; Hernandez, Carlos; Hormazabal, Nicolas; Baier, Jorge A.
    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 2(k)-neighborhoods; that is, neighborhoods that admit 2(k) neighbors per state, where k is a parameter. First, we provide a simple recursive definition of the 2(k)-neighborhood in terms of the 2(k-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 2(k)-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 2(k)-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.
  • No Thumbnail Available
    Item
    Time-Bounded Best-First Search for Reversible and Non-reversible Search Graphs
    (2016) Hernandez, Carlos; Baier, Jorge A.; Asin, Roberto
    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-BoundedWeighted 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-BoundedWeighted 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.