Further Connections Between Contract-Scheduling and Ray-Searching Problems
This work addresses optimization challenges in robotics and algorithm design, but it appears incremental as it builds on existing connections between these problem classes.
The paper tackles the problem of connecting contract-scheduling and ray-searching optimization problems, including variants with probabilistic considerations and fault-tolerance, and presents the first known results for multi-ray and multi-problem domains.
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 the same underlying approach.