Multi-Target Search in Euclidean Space with Ray Shooting (Full Version)

Ryan Hechenberger, Daniel Harabor, Muhammad Aamir Cheema, Peter J Stuckey, Pierre Le Bodic
7/6/2022
cs.CGcs.AI

No confident code implementation found for this paper.

Abstract

The Euclidean shortest path problem (ESPP) is a well studied problem with many practical applications. Recently a new efficient online approach to this problem, RayScan, has been developed, based on ray shooting and polygon scanning. In this paper we show how we can improve RayScan by carefully reasoning about polygon scans. We also look into how RayScan could be applied in the single-source multi-target scenario, where logic during scanning is used to reduce the number of rays shots required. This improvement also helps in the single target case. We compare the improved RayScan+ against the state-of-the-art ESPP algorithm, illustrating the situations where it is better.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

ERA*: Enhanced Relaxed A* algorithm for Solving the Shortest Path Problem in Regular Grid Maps

78% match2023

A Mixed-Integer Conic Program for the Moving-Target Traveling Salesman Problem based on a Graph of Convex Sets

77% match2024

Counterfactual Routing Using Integer Programming with Constraint Generation

77% match2026

Evolving A* to Efficiently Solve the k Shortest-Path Problem (Extended Version)

77% match1 repo32024

Tightest Admissible Shortest Path

75% match2023

LLM-Aided A* Search in Non-Geometric Network Graphs

75% match2026

Cite this paper

@article{hechenberger2022multitarget,
  title  = {Multi-Target Search in Euclidean Space with Ray Shooting (Full Version)},
  author = {Ryan Hechenberger and Daniel Harabor and Muhammad Aamir Cheema and Peter J Stuckey and Pierre Le Bodic},
  year   = {2022},
  eprint = {2207.02436},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2207.02436v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2207.02436.svg)](https://codeofpaper.com/paper/2207.02436)

Discussion