Abstract
This paper addresses two classes of different, yet interrelated optimization problems. The first class of problems involves a robot that must locate a hidden target in an environment that consists of a set of concurrent rays. The second class pertains to the design of interruptible algorithms by means of a schedule of contract algorithms. We study several variants of these families of problems, such as searching and scheduling with probabilistic considerations, redundancy and fault-tolerance issues, randomized strategies, and trade-offs between performance and preemptions. For many of these problems we present the first known results that apply to multi-ray and multi-problem domains. Our objective is to demonstrate that several well-motivated settings can be addressed using a common approach.
Introduction
The relationship between robotic search in physical environments and AI scheduling for "anytime" algorithms reveals a deep mathematical symmetry. This research, originally presented at IJCAI 2015, explores how these two seemingly disparate fields can be treated as two sides of the same coin. By establishing this equivalence, we can derive new strategies for handling uncertainty, fault tolerance, and performance trade-offs in both domains.
The paper focuses on two core optimization challenges:
- Ray-Searching: A robot at a junction of $m$ paths (rays) must find a hidden target of unknown location. The goal is to minimize the competitive ratio—the ratio of the distance traveled to the actual distance of the target.
- Contract-Scheduling: In AI, a "contract algorithm" requires a pre-specified execution time to produce a result. To make such algorithms "interruptible," one must schedule a series of increasingly longer contracts. The goal is to minimize the acceleration ratio—the factor by which a processor must be sped up to match an ideal interruptible system.
Methodology
The study employs competitive analysis and probabilistic modeling to develop optimal strategies. Key approaches include:
- Exponential Strategies: Building on the standard approach of increasing search distances or contract lengths exponentially ($x_i = b^i$).
- Non-Monotone Strategies: For fault tolerance, strategies are introduced that strategically revisit intervals to ensure the target is "hit" $r$ times efficiently.
- Randomization: A randomized scheduling strategy is introduced using a random starting offset and random permutations of tasks to smooth out worst-case scenarios.
- Geometric Round-Robin: A hybrid technique used to analyze the "preemptive model," where algorithms can be paused and resumed rather than restarted.
Key Insights and Results
The fundamental insight is that a robot turning around on a ray is mathematically identical to an algorithm being interrupted and restarted. This allows for cross-pollination of solutions between robotics and software scheduling.
Probabilistic Success and Redundancy
When a target is detected only with probability $p$, the competitive ratio scales by $1/p^2$. The paper proves the existence of an exponential strategy with a competitive ratio of at most $1 + 8m/p^2$. Furthermore, in fault-tolerant settings requiring $r$ successful visits, "non-monotone" strategies (NM-SEARCH) are proven superior to traditional monotone exponential strategies for $r > 2$.
The Power of Randomization
Randomization acts as a "smoothing" tool for worst-case performance. By picking a random starting offset, the worst-case acceleration ratio can be significantly reduced.
As shown in Figure 1, the randomized strategy consistently outperforms the deterministic approach as the number of concurrent problems increases. Theorem 9 provides a new bound for randomized acceleration ratios, $\beta_r(n) \leq n \frac{b^{n+1} \ln b}{(b^n-1)(b-1)}$, which converges to a significantly better value than deterministic limits for large $n$.
Conclusion and Future Work
This work provides a unified framework for multi-ray searching and multi-problem scheduling. However, several avenues for future research remain:
- Heterogeneous Environments: Current models assume identical success probabilities across all rays or problems.
- Optimality Gaps: A theoretical gap remains between the current upper bound of $\Theta(m/p^2)$ and the suspected optimal $\Theta(m/p)$ for probabilistic search.
- Multi-Processor Scaling: Extending these non-cyclic strategies to parallel processors remains an open challenge.
Summary updated