标题： 螺旋与超越：多速度代理的竞争性平面搜索 显示英文标题

标题： Spirals and Beyond: Competitive Plane Search with Multi-Speed Agents

摘要： 我们考虑在平面上使用多个速度不同的移动代理来最小化隐藏点目标的最坏情况搜索时间的问题。搜索时间通过目标到原点的距离进行归一化，遵循竞争分析中的标准惯例。目标是使所有目标位置的最大归一化时间（搜索成本）最小化。作为基本情况，我们将已知的单个单位速度代理的结果扩展到$n$个单位速度代理，该结果通过对数螺旋线实现了一个大约为$\mathcal{U}_1 = 17.28935$的最优成本。我们提供了一个基于对称螺旋的算法，其中每个代理遵循一个由相等角度相位偏移的对数螺旋线。这使得搜索成本与哪个代理找到目标无关。我们为此情况提供了闭式上界$\mathcal{U}_n$，并在我们的通用结果中使用了该上界。我们的主要贡献是针对具有任意速度的$n$个代理的最坏情况归一化搜索时间的上界。我们提供了一个框架，该框架选择一组代理并分配具有速度相关角度偏移的螺旋型轨迹，再次使搜索成本与哪个代理到达目标无关。 推论表明，当速度的几何平均值超过$\mathcal{U}_n / \mathcal{U}_k$时，$n$个多速代理（最快速度为 1）可以击败$k$个单位速度代理（成本低于$\mathcal{U}_k$）。 这意味着如果慢速代理降低了平均值太多，它们可能会被排除，从而激励非螺旋算法。 我们还给出了使用单个单位速度代理在锥体和锥体补集中的点搜索的新上界。 然后利用这些上界设计混合螺旋-方向策略，在一些代理较慢时，这些策略优于基于螺旋的算法。 这表明在一般的多速设置中，螺旋型轨迹可能不是最优的。 显示英文摘要

摘要： We consider the problem of minimizing the worst-case search time for a hidden point target in the plane using multiple mobile agents of differing speeds, all starting from a common origin. The search time is normalized by the target's distance to the origin, following the standard convention in competitive analysis. The goal is to minimize the maximum such normalized time over all target locations, the search cost. As a base case, we extend the known result for a single unit-speed agent, which achieves an optimal cost of about $\mathcal{U}_1 = 17.28935$ via a logarithmic spiral, to $n$ unit-speed agents. We give a symmetric spiral-based algorithm where each agent follows a logarithmic spiral offset by equal angular phases. This yields a search cost independent of which agent finds the target. We provide a closed-form upper bound $\mathcal{U}_n$ for this setting, which we use in our general result. Our main contribution is an upper bound on the worst-case normalized search time for $n$ agents with arbitrary speeds. We give a framework that selects a subset of agents and assigns spiral-type trajectories with speed-dependent angular offsets, again making the search cost independent of which agent reaches the target. A corollary shows that $n$ multi-speed agents (fastest speed 1) can beat $k$ unit-speed agents (cost below $\mathcal{U}_k$) if the geometric mean of their speeds exceeds $\mathcal{U}_n / \mathcal{U}_k$. This means slow agents may be excluded if they lower the mean too much, motivating non-spiral algorithms. We also give new upper bounds for point search in cones and conic complements using a single unit-speed agent. These are then used to design hybrid spiral-directional strategies, which outperform the spiral-based algorithms when some agents are slow. This suggests that spiral-type trajectories may not be optimal in the general multi-speed setting.