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.

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.

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.

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.

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.

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.

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.

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.

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.

A fast algorithm for checking whether an autonomous vehicle can arrive at a position at a given arrival time and velocity is the key to Autonomous Intersection Management (AIM). This paper presents a complete set of closed form equations that fully describes the set of all reachable arrival configurations in longitudinal motion planning if the vehicle's controller is a double integrator with bounded acceleration. This result improves the running time of the algorithm for checking the reachability of an arrival configuration from logarithmic time to constant time. We also apply the result to check the reachability in a segmented road and discuss how the algorithm can be applied to real vehicles.

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.

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.

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.

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.

Looking ahead to the time when autonomous cars will be common, Dresner and Stone proposed a multiagent systems-based 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.

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.

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.

To generate plans for collecting data for data mining, an important problem is information volatility during planning: the information needed by the planning system may change or expire during the planning process, as changes occur in the data being collected. In such situations, the planning system faces two challenges: how to generate plans despite these changes, and how to guarantee that a plan returned by the planner will remain valid for some period of time after the planning ends. The focus of our work is to address both of the above challenges. In particular, we provide: 1) A formalism for reactive query policies, a class of strategies for deciding when to reissue queries for information that has changed during the planning process. This class includes all query management strategies that have yet been developed. 2) A new reactive query policy called the presumptive strategy. In our experiments, the presumptive strategy ran exponentially faster than the lazy strategy, the best previously known query management strategy. In the hardest set of problems we tested, the presumptive strategy took 4.7% as much time and generated 6.9% as many queries as the lazy strategy

The SHOP2 planning system received one of the awards for distinguished performance in the 2002 International Planning Competition. This paper describes the features of SHOP2 which enabled it to excel in the competition, especially those aspects of SHOP2 that deal with temporal and metric planning domains.