<p>The Freeze-Tag Problem (FTP) involves activating a set of initially inactive robots as quickly as possible, starting from a single active robot. Once activated, a robot can assist in activating other robots. Each active robot moves at unit speed. The objective is to minimize the makespan, i.e., the time required to activate the last robot. A key performance measure is the wake-up ratio, defined as the maximum time needed to activate all of the robots in any initial configuration. This work focuses on the geometric (Euclidean) version of FTP in <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varvec{\mathbb {R}}^{\varvec{d}}\)</EquationSource> </InlineEquation> under the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\varvec{\ell }_{\varvec{p}}\)</EquationSource> </InlineEquation> norm, where the initial distance between each inactive robot and the single active robot is at most <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\varvec{1}\)</EquationSource> </InlineEquation>. For <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\varvec{(\mathbb {R}}^{\varvec{2}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\)</EquationSource> </InlineEquation>, we improve the previous upper bound of <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(\varvec{4.62}\)</EquationSource> </InlineEquation> (Bonichon et al. [<CitationRef CitationID="CR1">1</CitationRef>], CCCG 2024) to <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(\varvec{4.31}\)</EquationSource> </InlineEquation>. The known lower bound for the wake-up ratio is <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\varvec{3.82}\)</EquationSource> </InlineEquation>. In <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(\varvec{\mathbb {R}}^{\varvec{3}}\)</EquationSource> </InlineEquation>, we propose a new strategy that achieves a wake-up ratio of <InlineEquation ID="IEq9"> <EquationSource Format="TEX">\(\varvec{12}\)</EquationSource> </InlineEquation> for <InlineEquation ID="IEq10"> <EquationSource Format="TEX">\(\varvec{(\mathbb {R}}^{\varvec{3}}\varvec{, \ell }_{\varvec{1}}\varvec{)}\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq11"> <EquationSource Format="TEX">\(\varvec{12.76}\)</EquationSource> </InlineEquation> for <InlineEquation ID="IEq12"> <EquationSource Format="TEX">\(\varvec{(\mathbb {R}}^{\varvec{3}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\)</EquationSource> </InlineEquation>. We also explore the FTP in <InlineEquation ID="IEq13"> <EquationSource Format="TEX">\(\varvec{(\mathbb {R}}^{\varvec{3}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\)</EquationSource> </InlineEquation> for specific instances where robots are positioned on the boundary of a sphere, providing further insights into practical scenarios. Finally, we demonstrate the practical efficiency of our <InlineEquation ID="IEq14"> <EquationSource Format="TEX">\(\varvec{(\mathbb {R}}^{\varvec{2}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\)</EquationSource> </InlineEquation> algorithm through simulations on real-world spatial data.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Geometric freeze-tag problem

  • Sharareh Alipour,
  • Arash Ahadi,
  • Kajal Baghestani,
  • Soroush Sahraei,
  • Mahdis Mirzaei

摘要

The Freeze-Tag Problem (FTP) involves activating a set of initially inactive robots as quickly as possible, starting from a single active robot. Once activated, a robot can assist in activating other robots. Each active robot moves at unit speed. The objective is to minimize the makespan, i.e., the time required to activate the last robot. A key performance measure is the wake-up ratio, defined as the maximum time needed to activate all of the robots in any initial configuration. This work focuses on the geometric (Euclidean) version of FTP in \(\varvec{\mathbb {R}}^{\varvec{d}}\) under the \(\varvec{\ell }_{\varvec{p}}\) norm, where the initial distance between each inactive robot and the single active robot is at most \(\varvec{1}\) . For \(\varvec{(\mathbb {R}}^{\varvec{2}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\) , we improve the previous upper bound of \(\varvec{4.62}\) (Bonichon et al. [1], CCCG 2024) to \(\varvec{4.31}\) . The known lower bound for the wake-up ratio is \(\varvec{3.82}\) . In \(\varvec{\mathbb {R}}^{\varvec{3}}\) , we propose a new strategy that achieves a wake-up ratio of \(\varvec{12}\) for \(\varvec{(\mathbb {R}}^{\varvec{3}}\varvec{, \ell }_{\varvec{1}}\varvec{)}\) and \(\varvec{12.76}\) for \(\varvec{(\mathbb {R}}^{\varvec{3}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\) . We also explore the FTP in \(\varvec{(\mathbb {R}}^{\varvec{3}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\) for specific instances where robots are positioned on the boundary of a sphere, providing further insights into practical scenarios. Finally, we demonstrate the practical efficiency of our \(\varvec{(\mathbb {R}}^{\varvec{2}}\varvec{, \ell }_{\varvec{2}}\varvec{)}\) algorithm through simulations on real-world spatial data.