Profile Picture

Jared Coleman

I'm joining LMU this fall as an Assistant Professor in Computer Science!

Ph.D. Candidate at University of Southern California
Autonomous Networks Research Group

Research Interests

Cooperative multi-agent systems, distributed computing, decentralized computing, online algorithms, distributed ledger technology, internet of things (IoT), and artificial intelligence (AI).

About Me

I am a proud member of the Big Pine Paiute Tribe of the Owens Valley. Besides computer science, I enjoy board games, hiking, and language. I'm especially interested in my tribe's native language, Owens Valley Paiute, which is critically endangered and which I am one of many in our tribe working to learn and revitalize.


Linear Search for an Escaping Target with Unknown Speed

IWOCA 2024 - 35th International Workshop on Combinatorial Algorithms

We consider linear search for an escaping target whose speed and initial position are unknown to the searcher. A 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. An oblivious mobile target that is moving away from the origin with an unknown 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 two cases, depending on whether $d$ is known or unknown. The main contribution of this paper is to prove a new lower bound and give algorithms leading to new upper bounds for search in these settings. This results in 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. Our results solve an open problem proposed in [Coleman et al., Proc. OPODIS 2022]

Online Allocation of Sensing and Computation in Large Graphs

IEEE CIC 2023 - International Conference on Collaboration and Internet Computing

We consider vehicle tracking over a large territory equipped with sensors and computational units, and propose online resource allocation algorithms that decide which sensor nodes to activate, and on which computational units to perform the corresponding tracking tasks. We show through numerical evaluation that our approach can notably outperform state of art algorithms in terms of delay, communication cost, and the number of required sensor measurements.

DARSAN: A Decentralized Review System Suitable for NFT Marketplaces

ICBC 2023 - International Conference on Blockchain

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.

Search and Rescue on the Line

SIROCCO 2023 - 30th International Colloquium on Structural Information and Communication Complexity

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.

Graph Convolutional Network-based Scheduler for Distributing Computation in the Internet of Robotic Things

MILCOM 2023 WS-7 - Workshop On The Internet Of Things For Adversarial Environments

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.

Delivery to Safety with Two Cooperating Robots

SOFSEM 2023 - International Conference on Current Trends in Theory and Practice of Computer Science

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.

The Snow Plow Problem: Perpetual Maintenance by Mobile Agents on the Line

ICDCN 2023 - International Conference on Distributed Computing and Networking

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 destination 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+\epsilon)$-approximation algorithm which runs in $O(n \log 1/\epsilon)$ time.

Line Search for an Oblivious Moving Target

OPODIS 2022 - International Conference on Principles of Distributed Systems

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 \geq 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 away 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.

Multi-Objective Network Synthesis for Dispersed Computing in Tactical Environments

SPIE Defense + Commercial Sensing

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.

Network Synthesis for Tactical Environments: Scenario, Challenges, and Opportunities

SPIE Defense + Commercial Sensing

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.

Robotic Sorting on the Grid

ICDCN 2022 - 23rd International Conference on Distributed Computing and Networking

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.

Message Delivery in the Plane by Robots with Different Speeds

SSS 2021 - 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems

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 source) and $D$ (the destination). 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.

The Pony Express Communication Problem

IWOCA 2021 - 32nd International Workshop on Combinatorial Algorithms

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.

Minimizing The Maximum Distance Traveled To Form Patterns With Systems of Mobile Robots

CCCG 2020, 32nd Canadian Conference on Computational Geometry, August 5-7, 2020

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.


  • Chatlang

    Chatlang ( is a two-threaded LLM-powered chatbot-based role-playing system. Users interact with the system using two chat windows displayed side-by-side in a web interface. The first window is for role-playing, where the user and chatbot are expected to never break character and only use the target language. In the second window, the user can use their native language to ask questions about the conversation or target language and get context-relevant feedback on their mistakes. This design enables uninterrupted roleplaying alongside instant feedback and support.

  • Kubishi Sentences

    Kubishi Sentences ( is an LLM-powered sentence builder/translator for the Owens Valley Paiute Language.

  • GCN-Turtlebot

    GCN-based Scheduler for Distributing Computation in the Internet of Robotic Things

    This project explores how graph convolutional neural networks can be trained to immitate well-known task-graph scheduling algorithms for fast re-scheduling over networks with highly dynamic communication links. First-place winner of The 2nd Student Design Competition on Networked Computing on the Edge at CPS IoT Week 2022.

  • Tendermint Tutorial Demo

    This is a short introductory tutorial on Tendermint consisting of a two-part video series and code to get started. Part 1 is a brief introduction to blockchain, Tendermint consensus, and the ABCI (Application Blockchain Interface). Part 2 is a tutorial demo which viewers can run themselves and follow along. No installation required - just click the 'Open with GitPod' in the GitHub Repo!

  • Kubishi

    Kubishi ( is an online dictionary and encyclopedia for Owens Valley Paiute language and culture. The Owens Valley Paiute language is critically endangered. Kubishi is one resource in the fight (led by Tribes of the Owens Valley) to reverse the damage inflicted by generations of forced assimilation and colonialism. The goal of this project is to help promote and preserve Owens Valley Paiute language and culture, but also to provide an open-source toolset for other tribal nations to do the same.