Scholarlink

<p>Entities moving with bounded speed, but otherwise unpredictably, encroach upon one another at a fixed time if their separation is less than some specified threshold. Encroachment, of concern in many settings such as collision avoidance, may be unavoidable. However, uncertainty about the true location of entities may cause extra work due to potential, unrealized, encroachment. In our model, entities can be queried for their current location and the region possibly occupied by an entity grows in proportion to the time since its last query. The goal is to maintain low potential congestion, measured in terms of the (dynamic) intersection graph of these uncertainty regions, using limited queries. Previous work, in the same uncertainty model, described query schemes that minimize several measures of congestion potential at all times for <i>point entities</i>, using queries of <i>fixed frequency</i>. These schemes were shown to be <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varvec{O(1)}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="bold-italic">O</mi> <mo mathvariant="bold" stretchy="false">(</mo> <mn mathvariant="bold">1</mn> <mo mathvariant="bold" stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-competitive, in terms of congestion potential, even with clairvoyant query schemes (that know the entities’ trajectories), subject to the same bound on query frequency. Here we describe query schemes that are competitive, even with clairvoyant query schemes, in terms of their query <i>granularity</i> (minimum time between queries), over all sufficiently large time intervals, while guaranteeing a fixed bound on congestion potential <i>of entities with positive extent</i> at all times. This complementary optimization objective necessitates surprisingly different algorithms and analyses from that in previous work. Nevertheless, we also show that the competitive factor of our scheme is best possible, up to a constant factor, in the worst case.</p>

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

Frequency-Competitive Query Strategies to Maintain Low Congestion Potential Among Moving Entities

  • 期刊论文

  • 发表日期：

    2026年2月13日

查看全文
  • William Evans,
  • David Kirkpatrick

摘要

Entities moving with bounded speed, but otherwise unpredictably, encroach upon one another at a fixed time if their separation is less than some specified threshold. Encroachment, of concern in many settings such as collision avoidance, may be unavoidable. However, uncertainty about the true location of entities may cause extra work due to potential, unrealized, encroachment. In our model, entities can be queried for their current location and the region possibly occupied by an entity grows in proportion to the time since its last query. The goal is to maintain low potential congestion, measured in terms of the (dynamic) intersection graph of these uncertainty regions, using limited queries. Previous work, in the same uncertainty model, described query schemes that minimize several measures of congestion potential at all times for point entities, using queries of fixed frequency. These schemes were shown to be \(\varvec{O(1)}\) O ( 1 ) -competitive, in terms of congestion potential, even with clairvoyant query schemes (that know the entities’ trajectories), subject to the same bound on query frequency. Here we describe query schemes that are competitive, even with clairvoyant query schemes, in terms of their query granularity (minimum time between queries), over all sufficiently large time intervals, while guaranteeing a fixed bound on congestion potential of entities with positive extent at all times. This complementary optimization objective necessitates surprisingly different algorithms and analyses from that in previous work. Nevertheless, we also show that the competitive factor of our scheme is best possible, up to a constant factor, in the worst case.