# Publications

### Abstract

We introduce DARSAN, a decentralized review system designed for Non-Fungible Token (NFT) marketplaces, to address the challenge of verifying the quality of highly resalable products with few verified buyers by incentivizing unbiased reviews. DARSAN works by iteratively selecting a group of reviewers (called ``experts'') who are likely to both accurately predict the objective popularity and assess some subjective quality of the assets uniquely associated with NFTs. The system consists of a two-phased review process: a ``pre-listing'' phase where only experts can review the product, and a ``pre-sale'' phase where any reviewer on the system can review the product. Upon completion of the sale, DARSAN distributes incentives to the participants and selects the next generation of experts based on the performance of both experts and non-expert reviewers. We evaluate DARSAN through simulation and show that, once bootstrapped with an initial set of appropriately chosen experts, DARSAN favors honest reviewers and improves the quality of the expert pool over time without any external intervention even in the presence of potentially malicious participants.

### Abstract

We propose and study a problem inspired by a common task in disaster, military, and other emergency scenarios: search and rescue. Suppose an object (victim, message, target, etc.) is at some unknown location on a path. Given one or more mobile agents, also at initially arbitrary locations on the path, the goal is to find and deliver the object to a predefined destination in as little time as possible. We study the problem for the one- and two-agent cases and consider scenarios where the object and agents are arbitrarily (adversarially, even) placed along a path of either known (and finite) or unknown (and potentially infinite) length. We also consider scenarios where the destination is either at the endpoint or in the middle of the path. We provide both deterministic and randomized online algorithms for each of these scenarios and prove bounds on their (expected) competitive ratios.

### Abstract

Existing solutions for scheduling arbitrarily complex distributed applications on networks of computational nodes are insufficient for scenarios where the network topology is changing rapidly.New Internet of Things (IoT) domains like the Internet of Robotic Things (IoRT) and the Internet of Battlefield Things (IoBT) demand solutions that are robust and efficient in environments that experience constant and/or rapid change.In this paper, we demonstrate how recent advancements in machine learning (in particular, in graph convolutional neural networks) can be leveraged to solve the task scheduling problem with decent performance and in much less time than traditional algorithms.

### Abstract

Two cooperating, autonomous mobile robots with arbitrary nonzero max speeds are placed at arbitrary initial positions in the plane. A remotely detonated bomb is discovered at some source location and must be moved to a safe distance away from its initial location as quickly as possible. In the Bomb Squad problem, the robots cooperate by communicating face-to-face in order to pick up the bomb from the source and carry it away to the boundary of a disk centered at the source in the shortest possible time. The goal is to specify trajectories which define the robots' paths from start to finish and their meeting points which enable face-to-face collaboration by exchanging information and passing the bomb from robot to robot.We design algorithms reflecting the robots' knowledge about orientation and each other's speed and location. In the offline case, we design an optimal algorithm. For the limited knowledge cases, we provide online algorithms which consider robots' level of agreement on orientation as per OneAxis and NoAxis models, and knowledge of the boundary as per Visible, Discoverable, and Invisible. In all cases, we provide upper and lower bounds for the competitive ratios of the online problems.

### Abstract

We propose and study a new perpetual maintenance problem: The Snow Plow Problem. Inspired by snow removal in urban environments, we consider the perpetual maintenance by n mobile agents of a fixed-length interval over which some resource accumulates continuously over time (i.e. snow). In order to maintain the interval, agents must traverse it, collecting accumulated resources by plowing over continuous segments, and then return to some predefined <i>destination</i> point on the interval to dump collected resources. In a sense, our problem can be described as a combination of the well-studied patrolling and delivery problems. The maintenance cost for an agent is some combination of the distance traveled and the volume of resources collected between visits to the destination. We first study the case where the maintenance cost is simply the maximum amount of snow each agent must carry at any point in time and provide an optimal O(n) algorithm for computing optimal trajectories for the mobile agents for scenarios where the destination is at an endpoint and snow falls uniformly across the interval. Then, we generalize the problem for any maintenance cost which can be expressed as the product of a positive, non-decreasing travel cost function f(x) (the cost to travel to a distance x) and a positive resource cost function g(x) such that \int_{y}^{z} g(x) dx represents the volume of snowfall in one unit of time in the sub-interval (y, z] \subseteq (0, 1]. We provide a (1+\epsilon)-approximation algorithm that runs in O(n \log 1/\epsilon ) time and an exact O(n) algorithm for the case where f(x) = ax and g(x) = b for some positive constants a and b. Finally, we generalize further to consider scenarios where the destination is at any point along the interval, providing another (1+ε)-approximation algorithm which runs in O(n log 1/ε) time.

### Abstract

Consider search on an infinite line involving an autonomous robot starting at the origin of the line and an oblivious moving target at initial distance d≥1 from it. The robot can change direction and move anywhere on the line with constant maximum speed 1 while the target is also moving on the line with constant speed v>0 but is unable to change its speed or direction. The goal is for the robot to catch up to the target in as little time as possible.The classic case where v=0 and the target's initial distance d is moving <it>away</it> from the robot with a known speed v<1. In this paper we design and analyze search algorithms for the remaining possible knowledge situations, namely, when d and v are known, when v is known but d is unknown, when d is known but v is unknown, and when both v and d are unknown. Furthermore, for each of these knowledge models we consider separately the case where the target is moving away from the origin and the case where it is moving toward the origin. We design algorithms and analyze competitive ratios for all eight cases above. The resulting competitive ratios are shown to be optimal when the target is moving towards the origin as well as when v is known and the target is moving away from the origin.

### Abstract

Tactical operations like search and rescue or surveillance necessitate the rapid synthesis of physically dispersed assets and mobile compute nodes into a network capable of efficient and reliable information gathering, dissemination, and processing. We formalize this network synthesis problem as selecting one among a set of potentially deployable networks which optimally supports the distributed execution of complex applications. We propose a general framework for studying this type of problem and provide solutions for some well-motivated variants. We discuss how the framework can be extended to support other objectives, parameters, and constraints as well as more scalable solution approaches.

### Abstract

We develop a network synthesis scenario, which is built around a concrete perimeter surveillance application, yet we believe captures a number of the challenges and requirements that are common to other tactical communication and computational network applications. The proposed scenario addresses the problem of binary population identification within a perimeter: our goal is to synthesize a sensing and computing network that classifies people moving within a given perimeter to one of two categories (e.g., friend or foe). We discuss several open challenges that we organize across the following clusters: sensor placement, communication network provisioning and optimization, computational task placement, dynamic resynthesis and resilience under adverserial settings. We also briefly discuss approaches that attempt to address such challenges.

### Links

### Authors

Tzanis AnevlavisJonathan Bunton

Jared Coleman

Mine Dogan

Eugenio Grippo

Abel Souza

Christina Fragouli

Bhaskar Krishnamachari

Matthew Maness

Karl Olson

Prashant Shenoy

Paulo Tabuada

Gunjan Verma

### Abstract

Inspired by robotic applications, we study the problem of sorting a set of items over a physical domain with mobile agents. Given m mobile robots and a grid where each cell contains a single element, the objective is to design algorithms that allow robots to cooperatively sort the elements over the grid in the minimum time. We assume a synchronous model where robots do not communicate, can carry up to c elements, and can move between adjacent cells in one unit of time (grab and release time is negligible). First, we show that any algorithm requires at least \Omega\left(\frac{n^2}{mc}\right)units of time to sort an n-element line (an n \times 1) and present an algorithm that sorts the elements in O \left(\frac{n^2}{mc}\right) time. Then, we show that any n \times 1-grid requires at least \Omega \left( \frac{n^3}{mc} \right) time and present an algorithm that completes in O\left(\frac{n^3 \log n}{mc}\right) time. Our algorithms have an equivalent competitive ratio to Shear Sort [Isaacd et al., Proc ICPP 1986] with only m=n agents (compared to the n^2 processors required by Shear Sort). Finally, we present experimental results that show the capacity has very little impact on the overall runtime and that a simplification of the algorithm leads to better results.

### Abstract

We study a fundamental cooperative message-delivery problem on the plane. Assume n robots which can move in any direction, are placed arbitrarily on the plane. Robots each have their own maximum speed and can communicate with each other face-to-face (i.e., when they are at the same location at the same time). There are also two designated points on the plane, S (the <i>source</i>) and D (the <i>destination</i>). The robots are required to transmit the message from the source to the destination as quickly as possible by face-to-face message passing. We consider both the offline setting where all information (the locations and maximum speeds of the robots) are known in advance and the online setting where each robot knows only its own position and speed along with the positions of S and D.In the offline case, we discover an important connection between the problem for two-robot systems and the well-known Apollonius circle which we employ to design an optimal algorithm. We also propose a \sqrt 2 approximation algorithm for systems with any number of robots. In the online setting, we provide an algorithm with competitive ratio \frac 17 \left( 5+ 4 \sqrt{2} \right) for two-robot systems and show that the same algorithm has a competitive ratio less than 2 for systems with any number of robots. We also show these results are tight for the given algorithm. Finally, we give two lower bounds (employing different arguments) on the competitive ratio of any online algorithm, one of 1.0391 and the other of 1.0405.

### Abstract

We introduce a new problem which we call the Pony Express problem. n robots with differing speeds are situated over some domain. A message is placed at some commonly known point. Robots can acquire the message either by visiting its initial position, or by encountering another robot that has already acquired it. The robots must collaborate to deliver the message to a given destination. The objective is to deliver the message in minimum time. In this paper we study the Pony Express problem on the line where n robots are arbitrarily deployed along a finite segment. The robots have different speeds and can move in both directions. We are interested in both offline centralized and online distributed algorithms. In the online case, we assume the robots have limited knowledge of the initial configuration. In particular, the robots do not know the initial positions and speeds of the other robots nor even their own position and speed. They do, however, know the direction on the line in which to find the message and have the ability to compare speeds when they meet. First, we study the Pony Express problem where the message is initially placed at one endpoint of a segment and must be delivered to the other endpoint. We provide an O(n \log n) running time offline algorithm as well as an optimal online algorithm. Then we study the Half-Broadcast problem where the message is at the center and must be delivered to either one of the endpoints of the segment O(n^2 \log n) time and we provide an online algorithm that attains a competitive ratio of \frac 3 2 which we show is the best possible. Finally, we study the Broadcast problem where the message is at the center and must be delivered to both endpoints of the segment \frac 9 5, which we show is tight.

### Abstract

In the pattern formation problem, robots in a system must self-coordinate to form a given pattern, regardless of translation, rotation, uniform-scaling, and/or reflection. In other words, a valid final configuration of the system is a formation that is similar to the desired pattern. While there has been no shortage of research in the pattern formation problem under a variety of assumptions, models, and contexts, we consider the additional constraint that the maximum distance traveled among all robots in the system is minimum. Existing work in pattern formation and closely related problems are typically application-specific or not concerned with optimality (but rather feasibility). We show the necessary conditions any optimal solution must satisfy and present a solution for systems of three robots. Our work also led to an interesting result that has applications beyond pattern formation. Namely, a metric for comparing two triangles where a distance of 0 indicates the triangles are similar, and 1 indicates they are fully dissimilar.