We consider linear search for an escaping target whose speed and/or initial distance from the origin may be unknown to the searcher. The searcher (an autonomous mobile agent) is initially placed at the origin of the real line and can move with maximum speed 1 in either direction along the line. The oblivious mobile target that is moving away from the origin with a constant speed v < 1 is initially placed by an adversary on the infinite line at distance d from the origin in an unknown direction. We consider four cases, depending on whether v and/or d is known to the searcher. The main contributions of this paper are new lower bounds as well as algorithms leading to new upper bounds for search in these settings. We present tight bounds for the cases when v is known. For the cases where v is unknown, we prove an optimal (up to lower order terms in the exponent) competitive ratio in the case where d is known and improved upper and lower bounds for the case where d is unknown. These results solve an open problem proposed in Coleman et al. (2022) [11] .

Scheduling a task graph representing an application over a heterogeneous network of computers is a fundamental problem in distributed computing. It is known to be not only NP-hard but also not polynomial-time approximable within a constant factor. As a result, many heuristic algorithms have been proposed over the past few decades. Yet it remains largely unclear how these algorithms compare to each other in terms of the quality of schedules they produce. We identify gaps in the traditional benchmarking approach to comparing task scheduling algorithms and propose a simulated annealing-based adversarial analysis approach called PISA to address them. We also introduce SAGA, a new open-source library for comparing task scheduling algorithms. We use SAGA to benchmark 15 algorithms on 16 datasets and PISA to compare the algorithms in a pairwise manner. Algorithms that appear to perform similarly on benchmarking datasets are shown to perform very differently on adversarially chosen problem instances. Interestingly, the results indicate that this is true even when the adversarial search is constrained to selecting among well-structured, applicationspecific problem instances. We present the first known lower bounds on the performance of many of the algorithms considered in this paper compared to other popular scheduling algorithms. This work represents an important step towards a more general understanding of the performance boundaries between task scheduling algorithms on different families of problem instances.

Scheduling a given graph of tasks on a processing network has been a topic of interest and has been extensively studied, including for IoT applications. However, scheduling a series of task graphs that arrive at different time instances is still under-explored. We discuss this problem and introduce two approaches for it: Residual and Cumulative. We demonstrate using two subtle examples that both approaches face performance challenges.

Cooperative mobile robot systems have great potential to solve real-world problems but are, in practice, limited by their physical capabilities, the environment in which they operate, and the technology available to them. My research investigates how communication, localization, sensing, mobility, and computation constraints affect the performance of mobile agent systems. In this extended abstract, I focus on two fundamental problems: delivery and dispersed computing, and discuss recent contributions to the literature, as well as our ongoing work.