Nicolás Rivera Papers

JMLR Journal 2024 Journal Article

A General Framework for the Analysis of Kernel-based Tests

Tamara Fernández
Nicolás Rivera

Kernel-based tests provide a simple yet effective framework that uses the theory of reproducing kernel Hilbert spaces to design non-parametric testing procedures. In this paper, we propose new theoretical tools that can be used to study the asymptotic behaviour of kernel-based tests in various data scenarios and in different testing problems. Unlike current approaches, our methods avoid working with U and V-statistics expansions that usually lead to lengthy and tedious computations and asymptotic approximations. Instead, we work directly with random functionals on the Hilbert space to analyse kernel-based tests. By harnessing the use of random functionals, our framework leads to much cleaner analyses, involving less tedious computations. Additionally, it offers the advantage of accommodating pre-existing knowledge regarding test-statistics as many of the random functionals considered in applications are known statistics that have been studied comprehensively. To demonstrate the efficacy of our approach, we thoroughly examine two categories of kernel tests, along with three specific examples of kernel tests, including a novel kernel test for conditional independence testing. [abs] [ pdf ][ bib ] &copy JMLR 2024. ( edit, beta )

PDF Details

SoCS Conference 2024 Conference Paper

Finding a Small, Diverse Subset of the Pareto Solution Set in Bi-Objective Search (Extended Abstract)

Pablo Araneda
Carlos Hernández Ulloa
Nicolás Rivera
Jorge A. Baier

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.

Details

AAAI Conference 2022 Conference Paper

Subset Approximation of Pareto Regions with Bi-objective A*

Nicolás Rivera
Jorge A. Baier
Carlos Hernández

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.

PDF Details

SoCS Conference 2022 Conference Paper

Subset Approximation of Pareto Regions with Bi-Objective A* (Extended Abstract)

Jorge A. Baier
Nicolás Rivera
Carlos Hernández Ulloa

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.

Details

ICML Conference 2020 Conference Paper

Kernelized Stein Discrepancy Tests of Goodness-of-fit for Time-to-Event Data

Tamara Fernandez
Nicolás Rivera
Wenkai Xu
Arthur Gretton

Survival Analysis and Reliability Theory are concerned with the analysis of time-to-event data, in which observations correspond to waiting times until an event of interest such as death from a particular disease or failure of a component in a mechanical system. This type of data is unique due to the presence of censoring, a type of missing data that occurs when we do not observe the actual time of the event of interest but, instead, we have access to an approximation for it given by random interval in which the observation is known to belong. Most traditional methods are not designed to deal with censoring, and thus we need to adapt them to censored time-to-event data. In this paper, we focus on non-parametric goodness-of-fit testing procedures based on combining the Stein’s method and kernelized discrepancies. While for uncensored data, there is a natural way of implementing a kernelized Stein discrepancy test, for censored data there are several options, each of them with different advantages and disadvantages. In this paper, we propose a collection of kernelized Stein discrepancy tests for time-to-event data, and we study each of them theoretically and empirically; our experimental results show that our proposed methods perform better than existing tests, including previous tests based on a kernelized maximum mean discrepancy.

Details

JAIR Journal 2020 Journal Article

The 2^k Neighborhoods for Grid Path Planning

Nicolás Rivera
Carlos Hernández
Nicolás Hormazábal
Jorge A Baier

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.

PDF Details DOI

SoCS Conference 2018 Conference Paper

A Suboptimality Bound for 2 k Grid Path Planning

Benjamín Kramm
Nicolás Rivera
Carlos Hernández Ulloa
Jorge A. Baier

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.

Details

AIJ Journal 2015 Journal Article

Incorporating weights into real-time heuristic search

Nicolás Rivera
Jorge A. Baier
Carlos Hernández

Multiplying the heuristic function by a weight greater than one is a well-known technique in heuristic search. When this technique is applied to A* with an admissible heuristic it yields substantial runtime savings, at the expense of sacrificing solution optimality. Its applicability to real-time heuristic search, a search approach that builds upon heuristic search, however, has only been explored by a few studies. In this article we present two new approaches to using weights in real-time heuristic search, applicable to a wide range of algorithms. The first one, weighted lookahead, is a variant of an existing approach by Shimbo and Ishida, and utilizes the weight while the algorithm performs lookahead search. The second one, weighted update, incorporates the weight to the edges of the search graph during the learning phase. We implemented both techniques within LSS-LRTA* and evaluated them in path-planning benchmarks. We show that weighted lookahead outperforms an existing approach by Shimbo and Ishida but that it does not improve over existing approaches that do not use weights. Weighted update, on the other hand, yields performance improvements of up to one order of magnitude both in solution cost and total search time. To illustrate further the generality of weighted update, we incorporate the technique in two other well-known real-time heuristic search algorithms: LRTA*-LS and daLSS-LRTA*, and we empirically show significant improvements for LRTA*-LS and modest but still important improvements for daLSS-LRTA*. We analyze the properties of weighted update in depth, showing, among other things, that it guarantees termination. Convergence behavior of LSS-LRTA*, modified to use weighted update, is also analyzed. In such a setting, we prove solutions are w-optimal, and provide additional bounds on solution quality that in practice are tighter than w-optimality.

Details DOI

SoCS Conference 2013 Conference Paper

Reconnecting with the Ideal Tree: An Alternative to Heuristic Learning in Real-Time Search

Nicolás Rivera
Leon Illanes
Jorge A. Baier
Carlos Hernández Ulloa

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.

Details

Possible papers