Related papers: Reducing Redundant Work in Jump Point Search

Reducing Redundant Work in Jump Point Search

URL: http://arxiv.org/abs/2306.15928v1
Date: Wed, 28 Jun 2023 05:21:59 GMT
Title: Reducing Redundant Work in Jump Point Search
Authors: Shizhe Zhao, Daniel Harabor, Peter J. Stuckey
Abstract summary: JPS (Jump Point Search) is a state-of-the-art optimal algorithm for online grid-based pathfinding. We show that JPS can exhibit pathological behaviours which are not well studied. We propose a purely online approach, called Constrained JPS (CJPS), to tackle them efficiently.
Score: 30.45272181563766
License: http://creativecommons.org/licenses/by/4.0/
Abstract: JPS (Jump Point Search) is a state-of-the-art optimal algorithm for online grid-based pathfinding. Widely used in games and other navigation scenarios, JPS nevertheless can exhibit pathological behaviours which are not well studied: (i) it may repeatedly scan the same area of the map to find successors; (ii) it may generate and expand suboptimal search nodes. In this work, we examine the source of these pathological behaviours, show how they can occur in practice, and propose a purely online approach, called Constrained JPS (CJPS), to tackle them efficiently. Experimental results show that CJPS has low overheads and is often faster than JPS in dynamically changing grid environments: by up to 7x in large game maps and up to 14x in pathological scenarios.

Related papers

SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
We present the Search with Learned Optimal Pruning-based Expansion (SLOPE) It learns the distance of a node from a possible optimal path, which in turn reduces the size of the open list. This ensures that the search explores only the region close to optimal paths while lowering memory and computational costs.
arXiv Detail & Related papers (2024-06-07T13:42:15Z)
Path Planning in a dynamic environment using Spherical Particle Swarm Optimization [0.0]
A Dynamic Path Planner (DPP) for UAV using the Spherical Vector-based Particle Swarm optimisation technique is proposed in this study. The path is constructed as a set of way-points that stands as re-planning checkpoints. Path length, Safety, Attitude and Path Smoothness are all taken into account upon deciding how an optimal path should be. Four test scenarios are carried out using real digital elevation models. Each test gives different priorities to path length and safety, in order to show how well the SPSO-DPP is capable of generating a safe yet efficient path segments.
arXiv Detail & Related papers (2024-03-19T13:56:34Z)
Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
We introduce an original variant of Monte-Carlo Tree Search (MCTS) tailored to multi-agent pathfinding. Specifically, we use individual paths to assist the agents with the the goal-reaching behavior. We also use a dedicated decomposition technique to reduce the branching factor of the tree search procedure.
arXiv Detail & Related papers (2023-07-25T12:33:53Z)
Enhanced Methods for the Weight Constrained Shortest Path Problem [18.567812400186092]
The Weight Constrained Shortest Path Problem (WCSPP) is a well-studied, yet challenging, topic in AI. This paper presents two new solution approaches to the WCSPP on the basis of A* search. We empirically evaluate the performance of our algorithms on a set of large and realistic problem instances.
arXiv Detail & Related papers (2022-07-29T15:32:45Z)
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
arXiv Detail & Related papers (2022-03-28T21:34:16Z)
GreedyNASv2: Greedier Search with a Greedy Path Filter [70.64311838369707]
In one-shot NAS methods, the search space is usually considerably huge (eg, $1321$) In this paper, we leverage an explicit path filter to capture the characteristics of paths and directly filter those weak ones. For example, our obtained GreedyNASv2-L achieves $81.1%$ Top-1 accuracy on ImageNet dataset, significantly outperforming the ResNet-50 strong baselines.
arXiv Detail & Related papers (2021-11-24T16:32:29Z)
Waypoint Planning Networks [66.72790309889432]
We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm. We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN) It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
arXiv Detail & Related papers (2021-05-01T18:02:01Z)
Theory-Inspired Path-Regularized Differential Network Architecture Search [206.93821077400733]
We study the impact of skip connections to fast network optimization and its competitive advantage over other types of operations in differential architecture search (DARTS) We propose a theory-inspired path-regularized DARTS that consists of two key modules: (i) a differential group-structured sparse binary gate introduced for each operation to avoid unfair competition among operations, and (ii) a path-depth-wise regularization used to incite search exploration for deep architectures that converge slower than shallow ones.
arXiv Detail & Related papers (2020-06-30T05:28:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.