Lower-bound Solutions to the Touring Regions Problem with Polygonal Obstacles and Disk-shaped Regions

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F25%3A00388322" target="_blank" >RIV/68407700:21230/25:00388322 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1109/ECMR65884.2025.11162978" target="_blank" >https://doi.org/10.1109/ECMR65884.2025.11162978</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/ECMR65884.2025.11162978" target="_blank" >10.1109/ECMR65884.2025.11162978</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Lower-bound Solutions to the Touring Regions Problem with Polygonal Obstacles and Disk-shaped Regions

Popis výsledku v původním jazyce

The paper studies lower bounds on the optimal solution of the shortest path connecting a sequence of regions with the presence of obstacles. For disk-shaped regions, a straightforward bound can be based on relaxing the obstacles and using Euclidean distance between the disks or the Second Order Cone Programming (SOCP). However, such lower bounds would be poor if regions are mutually close but reachable by relatively long detours, avoiding the obstacles. Therefore, we analyze the two-disk shortest path problem with three possible cases and use the path in lower bound estimation called TriCase. We show TriCase is a tighter lower bound than using Euclidean and SOCP-based approaches for specific instances. Based on the evaluation results, we propose to combine TriCase and SOCP approaches to determine the lower bound on the shortest path connecting disk-shaped regions in environments with polygonal obstacles. The lower bound is further employed in assessing the quality of a feasible sampling-based solution to the touring regions problem, supporting the viability of the proposed approach for routing problems with neighborhoods and the presence of polygonal obstacles.

Název v anglickém jazyce

Lower-bound Solutions to the Touring Regions Problem with Polygonal Obstacles and Disk-shaped Regions

Popis výsledku anglicky

The paper studies lower bounds on the optimal solution of the shortest path connecting a sequence of regions with the presence of obstacles. For disk-shaped regions, a straightforward bound can be based on relaxing the obstacles and using Euclidean distance between the disks or the Second Order Cone Programming (SOCP). However, such lower bounds would be poor if regions are mutually close but reachable by relatively long detours, avoiding the obstacles. Therefore, we analyze the two-disk shortest path problem with three possible cases and use the path in lower bound estimation called TriCase. We show TriCase is a tighter lower bound than using Euclidean and SOCP-based approaches for specific instances. Based on the evaluation results, we propose to combine TriCase and SOCP approaches to determine the lower bound on the shortest path connecting disk-shaped regions in environments with polygonal obstacles. The lower bound is further employed in assessing the quality of a feasible sampling-based solution to the touring regions problem, supporting the viability of the proposed approach for routing problems with neighborhoods and the presence of polygonal obstacles.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

20204 - Robotics and automatic control

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2025

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

2025 European Conference on Mobile Robots Conference Proceedings

ISBN

979-8-3315-2705-1

ISSN

2639-7919

e-ISSN

2767-8733

Počet stran výsledku

6

Strana od-do

1-6

Název nakladatele

IEEE

Místo vydání

—

Místo konání akce

Padua

Datum konání akce

2. 9. 2025

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

001592487100008