Browsing by Author "Hernández, Carlos"

Now showing 1 - 7 of 7
  • Thumbnail Image
    Item
    A Compact Answer Set Programming Encoding of Multi-Agent Pathfinding
    (IEEE, 2021) Gómez Araya, Rodrigo Nicolás Teófilo; Hernández, Carlos; Baier Aranda, Jorge Andrés
    Multi-agent pathfinding (MAPF) is the problem of finding k non-colliding paths connecting k given initial positions with k given goal positions on a given map. In its sum-of-costs variant, the total number of moves and wait actions performed by agents before they definitely reach the goal is minimized. Not surprisingly, since MAPF is combinatorial, a number of compilations to Boolean Satisfiability (SAT) and Answer Set Programming (ASP) exist. In this article, we describe in detail the first family of compilations to ASP that solve sum-of-costs MAPF over 4-connected grids. Compared to existing ASP compilations, a distinguishing feature of our compilation is that the number of total clauses (after grounding) grow linearly with the number of agents, while existing compilations grow quadratically. In addition, the optimization objective is 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-based sum-of-costs MAPF solvers when grids are congested with agents. We also show that our approach is competitive with a SAT-based approach when follow conflicts are taken into account. We also explore the potential of our solver when finding makespanoptimal solutions, in which makespan is minimized first and then cost is minimized. Our results show that makespan-optimal solutions are slightly suboptimal in most benchmarks. Moreover, our MAPF solver, when run in that mode, is faster and scales better.
  • Thumbnail Image
    Item
    Escaping Heuristic Hollows in Real-Time Search without Learning
    (IEEE, 2010) Hernández, Carlos; Baier Aranda, Jorge Andrés
    Real-time search is a standard approach to solving search problems in which agents have limited sensing capabilities and must act quickly. It is well known that real-time search algorithms like LRTA* and RTA* perform poorly in regions of the search space in which the heuristic function is very imprecise. Approaches that use look ahead or learning are used to overcome this drawback. They perform more computation in the planning phase compared to LRTA* andRTA* . In this paper we propose Path Real-Time A* (PRTA* ), an algorithm that, like LRTA*, performs little computation in the planning phase, but that, unlike LRTA*, terminates even if the problem does not have a solution. We show that our algorithm outperforms LRTA* and RTA* in standard real-time benchmark problems. Furthermore, we show that in some cases, PRTA* may also outperform lookahead-or learning-enabled algorithms but carrying out significantly less computation.
  • Thumbnail Image
    Item
    Heuristic Function to Solve The Generalized Covering TSP with Artificial Intelligence Search
    (IEEE, 2020) Greco Chandía, Matías José Andrés; Hernández, Carlos
    Search is a universal problem-solving method in Artificial Intelligence. Specifically, Heuristic Search algorithms, such as A*, use a heuristic function to guide the search process. The heuristic function allows algorithms to explore only a part of the search space, resulting in an efficient search process. This paper presents a new heuristic function to solve the Generalized Covering Traveling Salesman Problem (GCTSP). The heuristic function is precalculated. The method to obtain the function is pre-calculating optimal solutions consecutively to small sub-problems of the GCTSP of increasing difficulty, using an incremental Best First Search algorithm, which reuses heuristics values previously precalculated. The resultating heuristic function can be used with different heuristic search algorithms. To the best of our knowledge, this problem has not been solved with Heuristic Search. This paper is the first to present a solution to the GCTSP using Heuristic Search algorithms, such as A* and Anytime search algorithms. We evaluated different Heuristic Search algorithms. The experimental evaluation shows results of the same quality, obtained orders-of-magnitude faster than the exact methods traditionally used in Operations Research.
  • Thumbnail Image
    Item
    Prodromal manifestations of Parkinson’s disease in adults with 22q11.2 microdeletion syndrome
    (2022) Juri, Carlos; Chaná-Cuevas, Pedro; Kramer, Vasko; Fritsch, Rosemarie; Ornstein, Claudia; Cuiza, Analía; Hernández, Carlos; Villanueva, Katiuska; Cordova, Teresa; Mauro, Jorge; Ocampo, Adrián; Rebolledo-Jaramillo, Boris; Repetto, Gabriela M.
    22q11.2 microdeletion syndrome (22qDS) was recently identified as a risk factor for development of early-onset Parkinson´s disease (PD). The classical motor manifestations of this disease are preceded by early signs and symptoms of neurodegeneration. The progression of 22qDS-associated PD is unknown. We aimed to evaluate the presence of prodromal PD in a group of adults with 22qDS using the Movement Disorders Society (MDS) Criteria for Prodromal PD. Thirty-eight persons with 22qDS and 13 age-matched controls participated in the study, and their results were compared using the MannWhitney U test. Persons with 22qDS had lower scores on olfaction testing (p=7.42Ex10-5), higher scores on the COMPASS 31 scale for dysautonomia (p=2.28x10-3) and on the motor evaluation using Movement Disorder Society (MDS)-sponsored revision of Unified Parkinson’s Disease Rating Scale motor subscore (UPDRS-III) (p=1.84x10-4), compared with healthy controls. Home polysomnogram did not find participants with REM-sleep behavior disorder. Integrity of nigrostriatal dopaminergic system was evaluated by PET-CT imaging of presynaptic dopamine with 18F-PR04.MZ. Patients showed significantly higher specific binding ratios in the striatum, compared to controls (p=9.57x10-3 at the caudate nuclei). Two patients with 22qDS (5.2%) had decreased uptake in the posterior putamen (less than 60% of controls) and one fulfilled MDS criteria for prodromal PD. These results show that patients with 22qDS manifest some signs and symptoms of prodromal PD such as hyposmia, dysautonomia and mild movement alterations. In the majority, this was associated with elevated dopaminergic signaling, suggesting that loss of dopaminergic neurons may not be the cause. A smaller subgroup did show evidence of a decrease in nigrostriatal dopaminergic signaling, as seen in classical prodromal PD. Longitudinal studies are necessary to understand the progression to and risk of PD in persons with 22qDS.
  • No Thumbnail Available
    Item
    Promoting Self-Reflection of Social Isolation Through Persuasive Mobile Technologies: The Case of Mother Caregivers of Children With Cancer
    (2014) Fuentes Toro, Carolina; Hernández, Carlos; Escobedo, Lizbeth; Herskovic, Valeria; Tentori, Mónica
  • Thumbnail Image
    Item
    Reusing cost-minimal paths for goal-directed navigation in partially known terrains
    (2015) Hernández, Carlos; Uras, Tansel; Koenig, Sven; Baier Aranda, Jorge Andrés; Sun, Xiaoxun; Meseguer, Pedro.
  • Thumbnail Image
    Item
    Time-Bounded Best-First Search for Reversible and Non-reversibleSearch Graphs
    (2016) Hernández, Carlos; Baier Aranda, Jorge Andrés; Asín, Roberto