More Like this

1. A*pex: Efficient Approximate Multi-Objective Search on Graphs

   Zhang, H. ; Salzman, O. ; Kumar, S. ; Felner, A. ; Hernandez, C. ; Koenig, S. ( January 2022 , Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS))

   In multi-objective search, edges are annotated with cost vectors consisting of multiple cost components. A path dominates another path with the same start and goal vertices iff the component-wise sum of the cost vectors of the edges of the former path is 'less than' the component-wise sum of the cost vectors of the edges of the latter path. The Pareto-optimal solution set is the set of all undominated paths from a given start vertex to a given goal vertex. Its size can be exponential in the size of the graph being searched, which makes multi-objective search time-consuming. In this paper, we therefore study how to find an approximate Pareto-optimal solution set for a user-provided vector of approximation factors. The size of such a solution set can be significantly smaller than the size of the Pareto-optimal solution set, which enables the design of approximate multi-objective search algorithms that are efficient and produce small solution sets. We present such an algorithm in this paper, called A*pex. A*pex builds on PPA*, a state-of-the-art approximate bi-objective search algorithm (where there are only two cost components) but (1) makes PPA* more efficient for bi-objective search and (2) generalizes it to multi-objective search for any number of cost components. We first analyze the correctness of A*pex and then experimentally demonstrate its efficiency advantage over existing approximate algorithms for bi- and tri-objective search. 

   more » « less
2. Anytime Approximate Bi-Objective Search

   Zhang, H. ; Salzman, O. ; Kumar, S. ; Felner, A. ; Hernandez, C. ; Koenig, S. ( January 2022 , Proceedings of the Symposium on Combinatorial Search (SoCS))

   The Pareto-optimal frontier for a bi-objective search problem instance consists of all solutions that are not worse than any other solution in both objectives. The size of the Pareto-optimal frontier can be exponential in the size of the input graph, and hence finding it can be hard. Some existing works leverage a user-specified approximation factor ε to compute an approximate Pareto-optimal frontier that can be significantly smaller than the Pareto-optimal frontier. In this paper, we propose an anytime approximate bi-objective search algorithm, called Anytime Bi-Objective A*-ε (A-BOA*ε). A-BOA*ε is useful when deliberation time is limited. It first finds an approximate Pareto-optimal frontier quickly, iteratively improves it while time allows, and eventually finds the Pareto-optimal frontier. It efficiently reuses the search effort from previous iterations and makes use of a novel pruning technique. Our experimental results show that A-BOA*ε substantially outperforms baseline algorithms that do not reuse previous search effort, both in terms of runtime and number of node expansions. In fact, the most advanced variant of A-BOA*ε even slightly outperforms BOA*, a state-of-the-art bi-objective search algorithm, for finding the Pareto-optimal frontier. Moreover, given only a limited amount of deliberation time, A-BOA*ε finds solutions that collectively approximate the Pareto-optimal frontier much better than the solutions found by BOA*. 

   more » « less
3. Enhanced multi-objective A* using balanced binary search trees

   Ren, Zhongqiang ; Zhan, Richard ; Sivakumar, Rathinam ; Likhachev, Maxim ; Choset, Howie ( January 2022 , Proceedings of the International Symposium on Combinatorial Search)

   NA (Ed.)

   This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a graph where the goal is to find a set of Pareto-optimal solutions from a start node to a destination in the graph. A family of approaches based on MOA* have been developed to solve MO-SPP in the literature. Typically, these approaches maintain a “frontier” set at each node during the search process to keep track of the non-dominated, partial paths to reach that node. This search process becomes computationally expensive when the number of objectives increases as the number of Pareto-optimal solutions becomes large. In this work, we introduce a new method to efficiently maintain these frontiers for multiple objectives by incrementally constructing balanced binary search trees within the MOA* search framework. We first show that our approach correctly finds the Pareto-optimal front, and then provide extensive simulation results for problems with three, four and five objectives to show that our method runs faster than existing techniques by up to an order of magnitude. 

   more » « less
4. Comparing solution paths of sparse quadratic minimization with a Stieltjes matrix

   https://doi.org/10.1007/s10107-023-01966-0  

   He, Ziyu ; Han, Shaoning ; Gómez, Andrés ; Cui, Ying ; Pang, Jong-Shi ( May 2023 , Mathematical Programming)

   This paper studies several solution paths of sparse quadratic minimization problems as a function of the weighing parameter of the bi-objective of estimation loss versus solution sparsity. Three such paths are considered: the “$$\ell _0$$${\ell }_0$-path” where the discontinuous$$\ell _0$$${\ell }_0$-function provides the exact sparsity count; the “$$\ell _1$$${\ell }_1$-path” where the$$\ell _1$$${\ell }_1$-function provides a convex surrogate of sparsity count; and the “capped$$\ell _1$$${\ell }_1$-path” where the nonconvex nondifferentiable capped$$\ell _1$$${\ell }_1$-function aims to enhance the$$\ell _1$$${\ell }_1$-approximation. Serving different purposes, each of these three formulations is different from each other, both analytically and computationally. Our results deepen the understanding of (old and new) properties of the associated paths, highlight the pros, cons, and tradeoffs of these sparse optimization models, and provide numerical evidence to support the practical superiority of the capped$$\ell _1$$${\ell }_1$-path. Our study of the capped$$\ell _1$$${\ell }_1$-path is interesting in its own right as the path pertains to computable directionally stationary (= strongly locally minimizing in this context, as opposed to globally optimal) solutions of a parametric nonconvex nondifferentiable optimization problem. Motivated by classical parametric quadratic programming theory and reinforced by modern statistical learning studies, both casting an exponential perspective in fully describing such solution paths, we also aim to address the question of whether some of them can be fully traced in strongly polynomial time in the problem dimensions. A major conclusion of this paper is that a path of directional stationary solutions of the capped$$\ell _1$$${\ell }_1$-regularized problem offers interesting theoretical properties and practical compromise between the$$\ell _0$$${\ell }_0$-path and the$$\ell _1$$${\ell }_1$-path. Indeed, while the$$\ell _0$$${\ell }_0$-path is computationally prohibitive and greatly handicapped by the repeated solution of mixed-integer nonlinear programs, the quality of$$\ell _1$$${\ell }_1$-path, in terms of the two criteria—loss and sparsity—in the estimation objective, is inferior to the capped$$\ell _1$$${\ell }_1$-path; the latter can be obtained efficiently by a combination of a parametric pivoting-like scheme supplemented by an algorithm that takes advantage of the Z-matrix structure of the loss function.

    

   more » « less
5. A Lower Bounding Framework for Motion Planning amid Dynamic Obstacles in 2D.

   Ren, Zhongqiang ; Rathinam, Sivakumar ; Choset, Howie ( January 2022 , International Workshop on the Algorithmic Foundations of Robotics)

   This work considers a Motion Planning Problem with Dynamic Obstacles (MPDO) in 2D that requires finding a minimum-arrivaltime collision-free trajectory for a point robot between its start and goal locations amid dynamic obstacles moving along known trajectories. Existing methods, such as continuous Dijkstra paradigm, can find an optimal solution by restricting the shape of the obstacles or the motion of the robot, while this work makes no such assumptions. Other methods, such as search-based planners and sampling-based approaches can compute a feasible solution to this problem but do not provide approximation bounds. Since finding the optimum is challenging for MPDO, this paper develops a framework that can provide tight lower bounds to the optimum. These bounds act as proxies for the optimum which can then be used to bound the deviation of a feasible solution from the optimum. To accomplish this, we develop a framework that consists of (i) a bi-level discretization approach that converts the MPDO to a relaxed path planning problem, and (ii) an algorithm that can solve the relaxed problem to obtain lower bounds. We also present numerical results to corroborate the performance of the proposed framework. These results show that the bounds obtained by our approach for some instances are up to twice tighter than a baseline approach showcasing potential advantages of the proposed approach. 

   more » « less