S$^*$: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding
We combine ideas from uni-directional and bi-directional heuristic search, and approximation algorithms for the Traveling Salesman Problem, to develop a novel framework for a Multi-Goal Path Finding (MGPF) problem that provides a 2-approximation guarantee. MGPF aims to find a least-cost path from an origin to a destination such that each node in a given set of goals is visited at least once along the path. We present numerical results to illustrate the advantages of our framework over conventional alternates in terms of the number of expanded nodes and run time.
Code (1)
Tasks
Heuristic SearchTraveling Salesman ProblemSimilar Papers 제목 키워드 기반
Faster Approximation Algorithms for Parameterized Graph Clustering and Edge Labeling
Graph clustering is a fundamental task in network analysis where the goal is to detect sets of nodes that are well-connected to each other but sparsely connected to the rest of the graph. We present faster approximation …
ClusteringGraph ClusteringMultiple Node Immunisation for Preventing Epidemics on Networks by Exact Multiobjective Optimisation of Cost and Shield-Value
The general problem in this paper is vertex (node) subset selection with the goal to contain an infection that spreads in a network. Instead of selecting the single most important node, this paper deals with the problem …
Simple Heuristics Yield Provable Algorithms for Masked Low-Rank Approximation
In $masked\ low-rank\ approximation$, one is given $A \in \mathbb{R}^{n \times n}$ and binary mask matrix $W \in \{0,1\}^{n \times n}$. The goal is to find a rank-$k$ matrix $L$ for which: $$cost(L) = \sum_{i=1}^{n} \sum…
Low-Rank Matrix CompletionMatrix CompletionTensor DecompositionHeuristics for Partially Observable Stochastic Contingent Planning
Acting to complete tasks in stochastic partially observable domains is an important problem in artificial intelligence, and is often formulated as a goal-based POMDP. Goal-based POMDPs can be solved using the RTDP-BEL al…
Next-Future: Sample-Efficient Policy Learning for Robotic-Arm Tasks
Hindsight Experience Replay (HER) is widely regarded as the state-of-the-art algorithm for achieving sample-efficient multi-goal reinforcement learning (RL) in robotic manipulation tasks with binary rewards. HER facilita…
Multi-Goal Reinforcement LearningReinforcement Learning (RL)