Tsz-Chiu Au

ICRA Conference 2025 Conference Paper

Contingency Formation Planning for Interactive Drone Light Shows

• Tsz-Chiu Au

One of the most appealing applications of drone swarms is drone light shows, in which a group of drones displays an animation by showing a sequence of light patterns in the sky. In this paper, we consider using drone swarms as video game platforms and utilize planning techniques to display pixels in animations correctly while providing a fast response to user inputs. We devise a new sampling algorithm to solve a contingency formation planning problem, which aims to find a contingency formation plan such that drones can always move to the correct positions to display every possible future frame regardless of the user inputs in the future. The algorithm provides interactivity by preemptively relocating hidden drones, which move in stealth mode to the locations of all possible future frames. Our experiments show that the size of the frame buffer and the ratio between the number of drones and the number of pixels can greatly affect the performance of our system.

AAAI Conference 2024 Conference Paper

Block-Level Goal Recognition Design

• Tsz-Chiu Au

Existing works on goal recognition design (GRD) consider the underlying domain as a classical planning domain and apply modifications to the domain to minimize the worst case distinctiveness. In this paper, we propose replacing existing modifications with blocks, which group several closely related modifications together such that a block can modify a region in a search space with respect to some design constraints. Moreover, there could be blocks within blocks such that the design space becomes hierarchical for modifications at different levels of granularity. We present 1) a new version of pruned-reduce, a successful pruning rule for GRD, for block-level GRD, and 2) a new pruning rule for pruning some branches in both hierarchical and non-hierarchical design space. Our experiments show that searching in hierarchical design spaces greatly speeds up the redesign process.

ICRA Conference 2024 Conference Paper

Wind Field Modeling for Formation Planning in Multi-Drone Systems

• Minhyuk Park
• Tsz-Chiu Au

In multi-drone systems such as drone light shows, drones move in formation while avoiding collisions. However, few existing formation planning algorithms consider the wind fields of drones during planning. Since the wind field effect is prominent when drones have to fly close to each other, we cannot ignore the effect during planning. In this paper, we extend the reservation system in autonomous intersection management for grid-based formation planning by including a new type of reservation called non-exclusive reservations specifically for handling wind fields. We train a deep learning model to predict the deviation of a drone’s trajectory when the drone enters the wind field of another drone and then use the reservation grid to prevent collision. Based on the reservation system, we develop a new formation planning algorithm that focuses on adjusting the start times of motion plans to avoid collision. Our experimental results show that trajectory prediction can help make better decisions in task assignments for minimizing makespans.

IROS Conference 2023 Conference Paper

A Dynamic Programming Algorithm for Grid-Based Formation Planning of Multiple Vehicles

• Tsz-Chiu Au

A common operation in multirobot systems is to generate a motion plan for multiple robots such that the robots can move in formation to achieve some desired effects. For example, in autonomous parking lots, a group of vehicles can be asked to move to another location when they block another vehicle that needs to leave the parking lot. In this paper, we present a novel grid-based planning approach for motion planning that minimizes the makespan of moving multiple vehicles from one location to another in a safe manner. Unlike most existing multirobot planning algorithms, our algorithm uses dynamic programming to compute a nearly-optimal motion plan for a large group of vehicles in polynomial time with the help of a given set of intermediate vehicle patterns. Our experimental results show that our algorithm is much faster than an exact algorithm but does not increase the minimum makespans tremendously.

ICRA Conference 2022 Conference Paper

Dynamic Robot Chain Networks for Swarm Foraging

• Dohee Lee
• Qi Lu
• Tsz-Chiu Au

The objective of foraging robot swarms is to search for and collect resources in an unknown arena as quickly as possible. To avoid the congestion near the central collection zone, we previously proposed an extension to the multiple-place foraging in which robot chains are deployed dynamically so that foraging robots can deliver to the robot chains instead of the central collection zone. However, a robot chain can only reach one location at a time, and congestion can occur at the end of the robot chain. This paper presents an extension to dynamic robot chains called dynamic robot chain networks, which extends robot chains with branches, each of which reaches different resource clusters. We formulate the problem of finding the smallest dynamic robot chain networks as the Euclidean Steiner tree problem and explain how Steiner trees can be utilized to optimize the efficiency of the foraging operations. We implemented our foraging robot swarms in a simulator called ARGoS. Our experiments showed that dynamic robot chain networks can avoid obstacles and collect more resources when compared with the original robot chain design.

AAAI Conference 2022 Conference Paper

Extended Goal Recognition Design with First-Order Computation Tree Logic

• Tsz-Chiu Au

Goal recognition design (GRD) is the task of modifying environments for aiding observers to recognize the objectives of agents during online observations. The worst case distinctiveness (WCD), a widely used performance measure in GRD research, can fail to provide useful guidance to the redesign process when some goals are too hard to be distinguished. Moreover, the existing WCD-based approaches do not work when an agent aims for a sequence of goals instead of just one goal. The paper presents a new GRD framework called extended goal recognition design (EGRD) for goal recognition that involves multiple goals. The objective of EGRD is to modify an environment to minimize the worst case distinctiveness of a goal condition that describes how an agent can reach a set of goals. A goal condition can be formally expressed in first-order computation tree logic (FO-CTL) that can be evaluated by model checking. We introduce a novel graphical representation of FO-CTL sentences that is suitable for extended goal recognition. Moreover, we present a search algorithm for EGRD with a novel caching mechanism. Our experimental results show that the caching mechanism can greatly speed up our EGRD search algorithm by reusing the previous evaluation of FO-CTL sentences.

IROS Conference 2021 Conference Paper

Gridlock-free Autonomous Parking Lots for Autonomous Vehicles

• Tsz-Chiu Au

Many cities suffer from a shortage of parking spaces. Research in high density parking (HDP) focuses on how to increase the capacity of parking lots by allowing vehicles to block each other but temporarily give way to other vehicles by driving autonomously upon request. Previous works on HDP did not consider mixing different parking strategies and ignored the possibility of gridlock when multiple vehicles move simultaneously. In this paper, we describe the design of autonomous parking lots, which allows the deployment of different parking strategies in different regions in a parking lot. We present algorithms for checking whether adding a vehicle to an autonomous parking lot can lead to gridlock. Our simulation shows that autonomous parking lots can hold 60% more vehicles given the same amount of space.

ICRA Conference 2021 Conference Paper

Multiple-Place Swarm Foraging with Dynamic Robot Chains

• Dohee Lee
• Qi Lu
• Tsz-Chiu Au

The goal of foraging robot swarms is to search and deliver resources to a specific central collection zone quickly. In the previously proposed multiple-place foraging algorithm with dynamic depots, foraging performance decreases as search areas and swarm sizes increase: depots need to travel long distances to deliver resources to the center, and more robots produce more congestion on their journeys. We propose a novel extension to the multiple-place foraging in which multiple robot chains are deployed dynamically. Each robot chain connects a foraging location to the central collection zone. Instead of delivering resources by a single robot, resources are passed on robot chains from foraging locations to the center directly such that congestion near the central collection zone can be avoided. Dynamic robot chains can also relocate themselves to get closer to the resources while avoiding obstacles. We simulate our robot swarms in the robot simulator ARGoS. Our experiments show that robots using the MPFA with dynamic chains outperform the MPFA with dynamic depots and have less congestion.

IROS Conference 2019 Conference Paper

Scheduling of Mobile Workstations for Overlapping Production Time and Delivery Time

• Dohee Lee
• Tsz-Chiu Au

Many existing mobile service robots, including the robots in Robocup@Home, perform their designated tasks only when the robots are stationary. The efficiency of these robots can be improved if they can perform some tasks while moving. In this paper, we propose the concept of mobile workstations, which combine mobile platforms with production machinery to increase efficiency by overlapping production time and delivery time. We present a model of mobile workstations and their jobs and describe the task planning algorithm for a team of mobile workstations. The temporal planning problem for mobile workstations combines both features of job shop scheduling problems (JSP) and traveling salesman problem (TSP), but there is little work in the literature that tackles both JSP and TSP simultaneously. Our first algorithm is a complete search algorithm which returns an optimal temporal plan with minimum makespan, and our second algorithm conducts a local search in the space of task graphs so as to quickly return suboptimal temporal plans. According to our experiments, when the number of jobs is small, our second algorithm can generate near-optimal temporal plans, and when the number of jobs is large, our algorithm can generate much shorter plans than SGPlan 5 and a version of job shop scheduling algorithms.

AAMAS Conference 2017 Conference Paper

Extending the Range of Delivery Drones by Exploratory Learning of Energy Models

• Ty Nguyen
• Tsz-Chiu Au

Delivery drones have a fairly short range due to their limited battery life. We propose new exploration strategies to generate paths for a drone to reach its destination while learning about the energy consumption on each edge on its path so as to optimize its range in future missions. As the energy consumption mostly depends on the payload, the wind direction, and the wind speed, we developed an energy model to estimate the energy consumption based on these factors. We evaluated our exploration strategies for learning the energy model in order to identify the set of all reachable destinations. We found that adding a small amount of perturbation to encourage exploration can increase the learning rate.

IROS Conference 2017 Conference Paper

Learning of vehicular performance models for longitudinal motion planning to satisfy arrival requirements

• Ty Nguyen
• Dung Nguyen
• Tsz-Chiu Au

Motion planning with predictable timing and velocity will enable a number of interesting applications such as autonomous intersection management (AIM). These planning algorithms depend on an accurate model of the performance of the vehicular controllers, which can be highly non-linear. Au et al. proposed a motion planning algorithm to satisfy the arrival requirements in AIM. However, they assumed that the performance models are given for every road and did not discuss how to learn these models. In this paper, we propose an instance-based learning approach to learn the performance models automatically, and argue that instance-based learning is suitable for this learning task because performance models for different roads can have a high correlation with each other. Moreover, an exploration strategy based on the principle of least effort is given to speed up the learning process. Our experiments showed that the instance-based learning method with distance-based exploration strategy offers a faster learning rate than the artificial neural network methods.

IS Journal 2017 Journal Article

Multirobot Systems

• Tsz-Chiu Au
• Bikramjit Banerjee
• Prithviraj Dasgupta
• Peter Stone

The guest editors describe the six articles appearing in this special issue on multirobot systems.

ICRA Conference 2016 Conference Paper

Automatic configuration of mobile conveyor lines

• Dohee Lee
• Tsz-Chiu Au

A conveyor belt is an efficient mode of transportation and has been widely utilized to move large quantities of objects in assembly lines, airports, etc. We propose a new conveyor system called mobile conveyor lines that can autonomously configure itself to move objects to a given destination. This system is suitable for situations such as disaster areas in which it is difficult to set up a conveyor line manually. We analyze the reachability of a group of mobile conveyor belts and propose an algorithm to check the reachability of a given destination, as well as a method to generate a configuration to guide conveyor belts to connect themselves to reach the destination. Our experimental results show that our algorithms, together with a heuristic that biases the search towards the destination, can quickly generate configurations of conveyor belts for problems that require less than 20 conveyor belts.

IROS Conference 2012 Conference Paper

Evasion planning for autonomous vehicles at intersections

• Tsz-Chiu Au
• Chien-Liang Fok
• Sriram Vishwanath
• Christine Julien 0001
• Peter Stone 0001

Autonomous intersection management (AIM) is a new intersection control protocol that exploits the capabilities of autonomous vehicles to control traffic at intersections in a way better than traffic signals and stop signs. A key assumption of this protocol is that vehicles can always follow their trajectories. But mechanical failures can occur in real life, causing vehicles to deviate from their trajectories. A previous approach for handling mechanical failure was to prevent vehicles from entering the intersection after the failure. However, this approach cannot prevent collisions among vehicles already in the intersection or too close to stop because (1) the lack of coordination among vehicles can cause collisions during the execution of evasive actions; and (2) the intersection may not have enough room for evasive actions. In this paper, we propose a preemptive approach that pre-computes evasion plans for several common types of mechanical failures before vehicles enter an intersection. This preemptive approach is necessary because there are situations in which vehicles cannot evade without pre-allocation of space for evasion. We present a modified AIM protocol and demonstrate the effectiveness of evasion plan execution on a miniature autonomous intersection testbed.

ICRA Conference 2012 Conference Paper

Setpoint scheduling for autonomous vehicle controllers

• Tsz-Chiu Au
• Michael J. Quinlan
• Peter Stone 0001

This paper considers the problem of controlling an autonomous vehicle to arrive at a specific position on a road at a given time and velocity. This ability is particularly useful for a recently introduced autonomous intersection management protocol, called AIM, which has been shown to lead to lower delays than traffic signals and stop signs. Specifically, we introduce a setpoint scheduling algorithm for generating setpoints for the PID controllers for the brake and throttle actuators of an autonomous vehicle. The algorithm constructs a feasible setpoint schedule such that the vehicle arrives at the position at the correct time and velocity. Our experimental results show that the algorithm outperforms a heuristic-based setpoint scheduler that does not provide any guarantee about the arrival time and velocity.

IROS Conference 2011 Conference Paper

Autonomous Intersection Management: Multi-intersection optimization

• Matthew J. Hausknecht
• Tsz-Chiu Au
• Peter Stone 0001

Advances in autonomous vehicles and intelligent transportation systems indicate a rapidly approaching future in which intelligent vehicles will automatically handle the process of driving. However, increasing the efficiency of today's transportation infrastructure will require intelligent traffic control mechanisms that work hand in hand with intelligent vehicles. To this end, Dresner and Stone proposed a new intersection control mechanism called Autonomous Intersection Management (AIM) and showed in simulation that by studying the problem from a multiagent perspective, intersection control can be made more efficient than existing control mechanisms such as traffic signals and stop signs. We extend their study beyond the case of an individual intersection and examine the unique implications and abilities afforded by using AIM-based agents to control a network of interconnected intersections. We examine different navigation policies by which autonomous vehicles can dynamically alter their planned paths, observe an instance of Braess' paradox, and explore the new possibility of dynamically reversing the flow of traffic along lanes in response to minute-by-minute traffic conditions. Studying this multiagent system in simulation, we quantify the substantial improvements in efficiency imparted by these agent-based traffic control methods.

AAMAS Conference 2011 Conference Paper

Batch Reservations in Autonomous Intersection Management

• Neda Shahidi
• Tsz-Chiu Au
• Peter Stone

The recent robot car competitions and demonstrations have convincingly shown that fully autonomous vehicles are feasible with current or near-future intelligent vehicle technology. Looking ahead to the time when such autonomous cars will be common, Dresner and Stone proposed a new intersection control protocol called Autonomous Intersection Management (AIM) and showed that by leveraging the capacities of autonomous vehicles we can devise a reservation-based intersection control protocol that is much more efficient than traffic signals and stop signs. Their proposed protocol, however, handles reservation requests one at a time and does not prioritize reservations according to their relative importance and vehicles' waiting times, causing potentially large inequalities in granting reservations. For example, at an intersection between a main street and an alley, vehicles from the alley can take a very long time to get reservations to enter the intersection. In this research, we introduce a prioritization scheme to prevent uneven reservation assignments in unbalanced traffic. Our experimental results show that our prioritizing scheme outperforms previous intersection control protocols in unbalanced traffic.

AAAI Conference 2011 Conference Paper

Enforcing Liveness in Autonomous Traffic Management

• Tsz-Chiu Au
• Neda Shahidi
• Peter Stone

Looking ahead to the time when autonomous cars will be common, Dresner and Stone proposed a multiagent systemsbased intersection control protocol called Autonomous Intersection Management (AIM). They showed that by leveraging the capacities of autonomous vehicles it is possible to dramatically reduce the time wasted in traffic, and therefore also fuel consumption and air pollution. The proposed protocol, however, handles reservation requests one at a time and does not prioritize reservations according to their relative priorities and waiting times, causing potentially large inequalities in granting reservations. For example, at an intersection between a main street and an alley, vehicles from the alley can take an excessively long time to get reservations to enter the intersection, causing a waste of time and fuel. The same is true in a network of intersections, in which gridlock may occur and cause traffic congestion. In this paper, we introduce the batch processing of reservations in AIM to enforce liveness properties in intersections and analyze the conditions under which no vehicle will get stuck in traffic. Our experimental results show that our prioritizing schemes outperform previous intersection control protocols in unbalanced traffic.

IROS Conference 2010 Conference Paper

Bringing simulation to life: A mixed reality autonomous intersection

• Michael J. Quinlan
• Tsz-Chiu Au
• Jesse Zhu
• Nicolae Stiurca
• Peter Stone 0001

Fully autonomous vehicles are technologically feasible with the current generation of hardware, as demonstrated by recent robot car competitions. Dresner and Stone proposed a new intersection control protocol called Autonomous Intersection Management (AIM) and showed that with autonomous vehicles it is possible to make intersection control much more efficient than the traditional control mechanisms such as traffic signals and stop signs. The protocol, however, has only been tested in simulation and has not been evaluated with real autonomous vehicles. To realistically test the protocol, we implemented a mixed reality platform on which an autonomous vehicle can interact with multiple virtual vehicles in a simulation at a real intersection in real time. From this platform we validated realistic parameters for our autonomous vehicle to safely traverse an intersection in AIM. We present several techniques to improve efficiency and show that the AIM protocol can still outperform traffic signals and stop signs even if the cars are not as precisely controllable as has been assumed in previous studies.

AAMAS Conference 2008 Conference Paper

Synthesis of Strategies from Interaction Traces

• Tsz-Chiu Au
• Dana Nau
• Sarit Kraus

We describe how to take a set of interaction traces produced by different pairs of players in a two-player repeated game, and combine them into a composite strategy. We provide an algorithm that, in polynomial time, can generate the best such composite strategy. We describe how to incorporate the composite strategy into an existing agent, as an enhancement of the agent’s original strategy. We provide experimental results using interaction traces from 126 agents (most of them written by students as class projects) for the Iterated Prisoner’s Dilemma, Iterated Chicken Game, and Iterated Battle of the Sexes. We compared each agent with the enhanced version of that agent produced by our algorithm. The enhancements improved the agents’ scores by about 5% in the IPD, 11% in the ICG, and 26% in the IBS, and improved their rank by about 12% in the IPD, 38% in the ICG, and 33% in the IBS.

AAMAS Conference 2006 Conference Paper

Accident or Intention: That Is the Question (in the Noisy Iterated Prisoner's Dilemma)

• Tsz-Chiu Au
• Dana Nau

AAAI Conference 2006 Conference Paper

Maintaining Cooperation in Noisy Environments

• Tsz-Chiu Au

To prevent or alleviate conflicts in multi-agent environments, it is important to distinguish between situations where another agent has misbehaved intentionally and situations where the misbehavior was accidental. One situation where this problem arises is the Noisy Iterated Prisoner’s Dilemma, a version of the Iterated Prisoner’s Dilemma (IPD) in which there is a nonzero probability that a “cooperate” action will accidentally be changed into a “defect” action and vice versa. Tit-For-Tat and other strategies that do quite well in the ordinary (non-noisy) IPD can do quite badly in the Noisy IPD. This paper presents a technique called symbolic noise detection, for detecting whether anomalies in player’s behavior are deliberate or accidental. This idea to use player’s deterministic behavior to tell whether an action has been affected by noise. We also present DBS, an algorithm that uses symbolic noise detection in the Noisy IPD. DBS constructs a model of the other agent’s deterministic behavior, and watches for any deviation from this model. If the other agent’s next action is inconsistent with this model, the inconsistency can be due either to noise or to a genuine change in their behavior; and DBS can often distinguish between two cases by waiting to see whether this inconsistency persists in next few moves. This technique is effective because many IPD players often have clear deterministic patterns of behavior. We entered several different implementations of DBS in the 2005 Iterated Prisoner’s Dilemma competition, in Category 2 (noisy environments). Out of the 165 contestants in this category, most of DBS implementations ranked among top ten. The best one ranked third, and it was beaten only by two “master-and-slaves strategy” programs that each had a large number of “slave” programs feeding points to them.

ECAI Conference 2006 Conference Paper

The Incompleteness of Planning with Volatile External Information

• Tsz-Chiu Au
• Dana S. Nau

In many real-world planning environments, some of the information about the world is both external (the planner must request it from external information sources) and volatile (it changes before the planning process completes). In such environments, a planner faces two challenges: how to generate plans despite changes in the external information during planning, and how to guarantee that a plan returned by the planner will remain valid for some period of time after the planning ends. Previous works on planning with volatile information have addressed the first challenge, but not the second one. This paper provides a general model for planning with volatile external information in which the planner offers a guarantee of how long the solution will remain valid after it is returned, and an incompleteness theorem showing that there is no planner that can succeed in solving all solvable planning problems in which there is volatile external information.

IS Journal 2005 Journal Article

Applications of SHOP and SHOP2

• D. Nau
• Tsz-Chiu Au
• O. Ilghami
• U. Kuter
• H. Munoz-Avila
• J.W. Murdock
• D. Wu
• F. Yaman

We design the simple hierarchical ordered planner (SHOP) and its successor, SHOP2, with two goals in mind: to investigate research issues in automated planning and to provide some simple, practical planning tools. SHOP and SHOP2 are based on a planning formalism called hierarchical task network planning. SHOP and SHOP2 use a search-control strategy called ordered task decomposition, which breaks tasks into subtasks and generates the plan's actions in the same order that the plan executor executes them. So, throughout the planning process, the planner can tell what the state of the world at each step of the plan.

ECAI Conference 2004 Conference Paper

Utilizing Volatile External Information During Planning

• Tsz-Chiu Au
• Dana S. Nau
• V. S. Subrahmanian