Michal Čáp, MSc., Ph.D.

GPS receivers embedded in cell phones and connected vehicles generate series of location measurements that can be used for various analytical purposes. A common preprocessing step of this data is the so-called map matching. The goal of map matching is to infer the trajectory that the device followed in a road network from a potentially sparse series of noisy location measurements. Although accurate and robust map matching algorithms based on probabilistic models exist, they are computationally heavy and thus impractical for processing large datasets. In this paper, we present a scalable map matching algorithm based on Dijkstra's shortest path method, that is both accurate and applicable to large datasets. Our experiments on a publicly available dataset showed that the proposed method achieves accuracy that is comparable to that of the existing map matching methods using only a fraction of computational resources. As a result, our algorithm can be used to efficiently process large datasets of noisy and potentially sparse location data that would be unexploitable using existing techniques due to their high computational requirements.

In large-scale automated mobility-on-demand systems, the fleet manager is able to assign routes to individual automated vehicles in a way that minimizes formation of congestion. We formalize the problem of on-demand fleet routing in capacitated networks with time-varying demand. We demonstrate the limits of application of the steady-state flows approach in systems with time-varying demand and formulate a linear program to compute congestion-free routes for the vehicles in capacitated networks under time-varying demand. We evaluate the proposed approach in the simulation of a simplified, but characteristic illustrative example. The experiment reveals that the proposed routing approach can route 42% more traffic in congestion-free regime than the steady-state flow approach through the same network.

A station-based vehicle sharing system consists of a fleet of vehicles (usually bikes or cars) that can be rented at one station and returned at another station. We study how to achieve guaranteed service availability in such systems. Specifically, we are interested in determining a) the fleet size and b) a vehicle rebalancing policy that guarantees that a) every customer will find an available vehicle at the origin station and b) the customer will find a free parking spot at the destination station. We model the evolution of the number of vehicles at each station as a stochastic process. The proposed rebalancing strategy iteratively solves a chance-constrained optimization problem to find a rebalancing schedule that ensures that no service failures will occur in the future with a given level of confidence. We show that such a chance-constrained optimization problem can be converted into a linear program and efficiently solved. As a case study, we apply the proposed method to control a simulated bike-sharing system in Boston using real-world historical demand. Our results demonstrate that our method can indeed ensure the desired level of service availability even when the demand does not fully conform to the assumptions of the underlying stochastic model. Moreover, compared with a state-of-the art rebalancing method, the proposed method can achieve nearly full service availability while making less than half of the rebalancing trips.

Routing of a fleet of automated unit-occupancy vehicles in a capacitated transportation network is an emerging problem that needs to be addressed to realize large-scale automated transportation systems. We adopt an existing network-flow-based model for the problem and present a new reformulation based on Dantzig-Wolfe decomposition. This reformulation allows us to apply the column generation solution technique which, in turn, enables us to solve large-scale problem instances with tens of thousands of requests on networks with thousands of links. We empirically compare our method to the state-of-the-art approach on several standard benchmark instances and find that the computational time of our solution approach scales qualitatively better in all tested problem instance parameters: namely, in the size of the transportation network, in the magnitude of demand intensity, and in the number of demand flows.

Vehicle sharing system consists of a fleet of vehicles (usually bikes or cars) that can be rented at one station and returned at another station. We study how to achieve guaranteed service availability in such systems. Specifically, we are interested in determining a) the fleet size and initial allocation of vehicles to stations and b) the minimum capacity of each station needed to guarantee that a) every customer will find an available vehicle at the origin station and b) the customer will find a free parking spot at the destination station. We model the evolution of number of vehicles at each station as a stochastic process and prove that the relevant probabilities in the system can be approximated from above using a computationally-tractable decoupled model. This property can be exploited to efficiently determine the size of fleet, initial distribution of vehicles to stations, and station capacities that are sufficient to achieve the desired service level. The applicability of the method is demonstrated by computing the initial vehicle stock and the capacity of each station that would be needed to avoid service failures in Boston's bike sharing system “The Hubway”. Our simulation shows that the proposed method is able to find more efficient design parameters than the naive approach and consequently it can achieve the equivalent quality-of-service level with half of the vehicle fleet and half of the parking capacity.

We study the problem of reliable motion coordination strategies for teams of mobile robots when any of the robots can be temporarily stopped by an exogenous disturbance at any time. We assume that an arbitrary multi-robot planner initially provides coordinated trajectories computed without considering such disturbances. We are interested in designing a control strategy that handles delaying disturbance such that collisions and deadlocks are provably avoided, and the travel time is minimized. The problem is analyzed in a coordination space framework, in which each dimension represents the position of a single robot along its planned trajectory. We demonstrate that to avoid deadlocks, the trajectory of the system in the coordination space must be homotopic to the trajectory corresponding to the planned solution. We propose a controller that abides this homotopy constraint while minimizing the travel time. Besides being provably deadlock-free, our experiments show that travel time is significantly smaller with our method than than with a reactive method.

In densely populated-cities, the use of private cars for personal transportation is unsustainable, due to high parking and road capacity requirements. The mobility-ondemand systems have been proposed as an alternative to a private car. Such systems consist of a fleet of vehicles that the user of the system can hail for one-way point-to-point trips. These systems employ large-scale vehicle sharing, i.e., one vehicle can be used by several people during one day and consequently, the fleet size and the parking space requirements can be reduced, but, at the cost of a non-negligible increase in vehicles miles driven in the system. The miles driven in the system can be reduced by ridesharing, where several people traveling in a similar direction are matched and travel in one vehicle. We quantify the potential of ridesharing in a hypothetical mobility-on-demand system designed to serve all trips that are currently realized by private car in the city of Prague. Our results show that by employing a ridesharing strategy that guarantees travel time prolongation of no more than 10 minutes, the average occupancy of a vehicle will increase to 2.7 passengers. Consequently, the number of vehicle miles traveled will decrease to 35 % of the amount in the MoD system without ridesharing and to 60% of the amount in the present state.

Intelligent cars represent a promising technology expected to drastically improve safety and efficiency of automobile transportation. In this paper, we introduce an agent-based simulation platform AgentDrive and argue that it can be used to speed up the development and evaluation of new coordination algorithms for intelligent cars. We present the high-level architecture of the simulator and characterize the class of tasks for which is the tool best suited. In addition, we present a case study of AgentDrive being used for development of a lane-changing assistant technology. We describe the developed solution in detail and present the benchmark result, which were obtained using AgentDrive simulator, that demonstrate that coordinated lane changing enables safer and swifter lane changing then the traditional non-coordinated approach.

The increasing use of private vehicles for transportation in cities results in a growing demand for parking space and road network capacity. In many densely populated urban areas, however, the capacity of existing infrastructure is insufficient and extremely difficult to expand. Mobility-on-demand systems have been proposed as a remedy to the problem of limited parking space because they are able to satisfy the existing transportation demand with fewer shared vehicles and consequently require less parking space. Yet, the impact of large-scale vehicle sharing on traffic patterns is not well understood. In this work, we perform a simulation-based analysis of consequences of a hypothetical deployment of a large-scale station-based mobility-on-demand system in Prague and measure the traffic intensity generated by the system and its effects on the formation of congestion. We find that such a mobility-on-demand system would lead to significantly increased total driven distance and it would also increase levels of congestion due to extra trips without passengers. In fact, 38% kilometers traveled in such an MoD system would be driven empty.

Self-driving vehicles are a maturing technology with the potential to reshape mobility by enhancing the safety, accessibility, efficiency, and convenience of automotive transportation. Safety-critical tasks that must be executed by a self-driving vehicle include planning of motions through a dynamic environment shared with other vehicles and pedestrians, and their robust executions via feedback control. The objective of this paper is to survey the current state of the art on planning and control algorithms with particular regard to the urban setting. A selection of proposed techniques is reviewed along with a discussion of their effectiveness. The surveyed approaches differ in the vehicle mobility model used, in assumptions on the structure of the environment, and in computational requirements. The side by side comparison presented in this survey helps to gain insight into the strengths and limitations of the reviewed approaches and assists with system level design choices.

One of the standing challenges in multi-robot systems is the ability to reliably coordinate motions of multiple robots in environments where the robots are subject to disturbances. We consider disturbances that force the robot to temporarily stop and delay its advancement along its planned trajectory which can be used to model, e.g., passing-by humans for whom the robots have to yield. Although reactive collision-avoidance methods are often used in this context, they may lead to deadlocks between robots. We design a multi-robot control strategy for executing coordinated trajectories computed by a multi-robot trajectory planner and give a proof that the strategy is safe and deadlock-free even when robots are subject to delaying disturbances. Our simulations show that the proposed strategy scales significantly better with the intensity of disturbances than the naive liveness-preserving approach. The empirical results further confirm that the proposed approach is more reliable and also more efficient than state-of-the-art reactive techniques.

We consider a system consisting of multiple mobile robots in which the user can at any time issue relocation tasks ordering one of the robots to move from its current location to a given destination location. In this paper, we deal with the problem of finding a trajectory for each such relocation task that avoids collisions with other robots. The chosen robot plans its trajectory so as to avoid collision with other robots executing tasks that were issued earlier. We prove that if all possible destinations of the relocation tasks satisfy so-called valid infrastructure property, then this mechanism is guaranteed to always succeed and provide a trajectory for the robot that reaches the destination without colliding with any other robot. The time-complexity of the approach on a fixed space-time discretization is only quadratic in the number of robots. We demonstrate the applicability of the presented method on several real-world maps and compare its performance against a popular reactive approach that attempts to solve the collisions locally. Besides being dead-lock free, the presented approach generates trajectories that are significantly faster (up to 48% improvement) than the trajectories resulting from local collision avoidance.

In autonomous multirobot systems one of the concerns is how to prevent collisions between the individual robots. One approach to this problem involves finding coordinated trajectories from start to destination for all the robots and then letting the robots follow the preplanned coordinated trajectories. A widely used practical method for finding such coordinated trajectories is “classical” prioritized planning, where robots plan sequentially one after another. This method has been shown to be effective in practice, but it is incomplete (i.e., there are solvable problem instances that the algorithm fails to solve) and it has not yet been formally analyzed under what circumstances is the method guaranteed to succeed. Further, prioritized planning is a centralized algorithm, which makes the method unsuitable for decentralized multirobot systems. The contributions of this paper are: a) an adapted version of classical prioritized planning called revised prioritized planning with a formal characterization of a class of instances that are provably solvable by this algorithm and b) an asynchronous decentralized variant of both classical and revised prioritized planning together with a formal analysis showing that the algorithm terminates and inherits completeness properties from its centralized counterpart. The experimental evaluation performed in simulation on realworld indoor maps shows that: a) the revised version of prioritized planning reliably solves a wide class of instances on which both classical prioritized planning and popular reactive technique ORCA fail and b) the asynchronous decentralized implementation of classical and revised prioritized planning finds solution in large multirobot teams up to 2x-faster than the previously proposed synchronized decentralized approach.

Avoiding collisions is one of the vital tasks for systems of au- tonomous mobile agents. We focus on the problem of find- ing continuous coordinated paths for multiple mobile disc agents in a 2-d environment with polygonal obstacles. The problem is PSPACE-hard, with the state space growing ex- ponentially in the number of agents. Therefore, the state of the art methods include mainly reactive techniques and sampling-based iterative algorithms. We compare the performance of a widely-used reactive method ORCA with three variants of a popular planning algorithm RRT* applied to multi-agent path planning and find that an algorithm combining reactive collision avoid- ance and RRT* planning, which we call ORCA-RRT* can be used to solve instances that are out of the reach of ei- ther of the techniques. We experimentally show that: 1) the reactive part of the algorithm can efficiently solve many multi-agent path finding problems involving large number of agents, for which RRT* algorithm is often unable to find a solution in limited time and 2) the planning component of the algorithm is able to solve many instances containing local minima, where reactive techniques typically fail.

In this paper, the multi-robot motion coordination planning problem is addressed. Although a centralized prioritized planning strategy can be used to solve the problem, we rather consider a decentralized variant, which is a more suitable for a robotic system of cooperating unmanned aerial vehicles (UAVs) due to communication limitations, privacy concerns, and a better exploitation of computational resources distributed among the individual robots. However, the existing decentralized prioritized planning algorithm contains synchronization points that all the agents must be able to pass synchronously, which is impractical and inefficient for a real-world deployment of the robotic systems. Therefore, we introduce a new asynchronous decentralized prioritized planning algorithm and show that the method can converge faster than both the synchronous decentralized and centralized algorithms. Further, we demonstrate the applicability of the proposed method as a coordination mechanism within a complex mission planning for a real robotic system consisting of several autonomous UAVs.

Small Unmanned Aerial Vehicles (UAVs) are becoming increasingly popular for tasks such as surveillance or target tracking in various types of tactical missions. Traditionally, each UAV in a mission is controlled by one or more operators. In our previous work we have developed a collection of distributed algorithms that allow one operator to control a whole team of small UAVs. Here, we report on our successful effort to deploy the developed multi-agent control algorithms to a team of hardware UAVs. To reduce costs and risk, we first developed the multi-agent control algorithms using simulated approximation of the target environment. Then, we gradually refined the model of the target environment by adding higher-fidelity models of the assets and hardware-in-the loop assets. In the final step, the algorithms were deployed and field tested in a full hardware setting and in a mixed-reality setting, where hardware UAVs are accompanied by a a number of simulated UAVs.

The development process and simulation architecture presented here help narrow the gap between how theoretical AI algorithms are traditionally designed and validated and how practical algorithms for controlling robotic assets in simulated tactical missions are developed.

Cooperative pathfinding is a problem of finding a set of non-conflicting trajectories for a number of mobile agents. Its applications include planning for teams of mobile robots, such as autonomous aircrafts, cars, or underwater vehicles. The state-of-the-art algorithms for cooperative pathfinding typically rely on some heuristic forward-search pathfinding technique, where A* is often the algorithm of choice. Here, we propose MA-RRT*, a novel algorithm for multi-agent path planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm for finding single-agent shortest path called RRT*. We experimentally evaluate the performance of the algorithm and show that the sampling-based approach offers better scalability than the classical forward-search approach in relatively large, but sparse environments, which are typical in real-world applications such as multi-aircraft collision avoidance.

Cooperative pathfinding is a problem of finding a set of non-conflicting trajectories for a number of mobile agents. Its applications include planning for teams of mobile robots, such as autonomous aircrafts, cars, or underwater ve- hicles. The state-of-the-art algorithms for cooperative pathfinding for embod- ied robots typically rely on some heuristic forward-search pathfinding technique, where A* is often the algorithm of choice. Here, we propose MA-RRT*, a novel algorithm for multi-agent motion planning that builds upon a recently proposed asymptotically-optimal sampling-based algorithm called RRT*. In this paper, we focus on the case where the agents’ mobility model is a discrete graph. We eval- uate the performance of the proposed algorithm and its scalability with respect to the number of agents and the size of the environment. Our results show that the sampling-based approach offers better scalability than the classical forward- search approach in relatively sparse environments, which are typical in real-world applications such as multi-aircraft collision avoidance.

Since late 90’s of the last century, rapid advances in technology, mechanical engineering, miniaturization, telecommunications and informatics enabled development and routine deployment of sophisticated robots in many real world domains. Besides many applications in assembly industry, e.g., in car, or electronics assembly lines, defense organizations, together with space exploration and mining industries belong to the most demanding and optimistic users of robotic technology [25]. Especially in the military domain we nowadays witness a routine deployment of robotic assets in the field.

Cooperative pathfinding is a multi-agent path planning problem where a group of vehicles searches for a corresponding set of non-conflicting space-time trajectories. Many of the practi- cal methods for centralized solving of cooperative pathfinding prob- lems are based on the prioritized planning strategy. However, in some domains (e.g., multi-robot teams of unmanned aerial vehicles, au- tonomous underwater vehicles, or unmanned ground vehicles) a de- centralized approach may be more desirable than a centralized one due to communication limitations imposed by the domain and/or pri- vacy concerns. In this paper we present an asynchronous decentralized variant of prioritized planning ADPP and its interruptible version IADPP. The algorithm exploits the inherent parallelism of distributed systems and allows for a speed up of the computation process. Unlike the synchro- nized planning approaches, the algorithm allows an agent to react to updates about other agents' paths immediately and invoke its local spatio-temporal path planner to find the best trajectory, as response to the other agents' choices. We provide a proof of correctness of the algorithms and experimentally evaluate them on synthetic domains.

An incremental process for developing human-agent-robot applications uses mixed-reality testbeds of varying fidelity and size.

The development of control algorithms for tactical missions is being impeded by the significant gap between the way the artificial intelligence (A.I.) algorithms have been designed and validated and the way the robotic applications for (high-fidelity simulations) of tactical missions are being developed. On the one hand, we have low-level robotic simulators (or even robotic field testing). On the other hand, we have synthetic - usually mathematically defined - environments used for the design and formal testing of A.I. algorithms, e.g. randomly generated problem instances, synthetic graph structures, logical structures, regular grids, and similar. In this work, we are proposing a development process and a related software toolkit helping to narrow this gap. We use the simulation-aided development approach and tailor it towards the domain of tactical missions. The process is demonstrated on a specific application scenario, employing a general software toolkit Alite to glue together and adapt a number of A.I. algorithms, originally designed as highly abstract.

With scaling of multi-robot teams deployed in military operations, there is a need to boost autonomy of individual, as well as team behaviors. We developed a feature-rich simulation testbed for experimental evaluation of multi-agent coordination mechanisms applicable in tactical military operations in urban warfare. In particular, we investigated and implemented four approaches including multi-agent mission planning and plan repair, reactive planning for teamwork, patrolling of mobile targets, and tracking of smart targets. Besides the live-system demonstrator, we aim to showcase a scenario engaging a human in a pursuit-evasion game against the algorithms we implemented.

This paper proposes a modularisation framework for BDI based agent programming languages developed from a soft- ware engineering perspective. Like other proposals, BDI modules are seen as encapsulations of cognitive components. However, unlike other approaches, modules are here instan- tiated and manipulated in a similar fashion as objects in object orientation. In particular, an agent's mental state is formed dynamically by instantiating and activating BDI modules. The agent deliberates on its active module in-stances, which interact by sharing their beliefs and goals.

This paper proposes a modularisation framework for BDI based agent programming languages developed from a software engineering perspective. Like other proposals, BDI modules are seen as encapsulations of cognitive components. However, unlike other approaches, modules are here instantiated and manipulated in a similar fashion as objects in object orientation. In particular, an agent's mental state is formed dynamically by instantiating and activating BDI modules. The agent deliberates on its active module instances, which interact by sharing their beliefs and goals. The formal semantics of the framework are provided and some desirable properties of the framework are shown.

This paper proposes a mechanism for simulating limited com- munication bandwidth and processing power available to an agent in multi-agent simulations. Although there exist dedicated tools able to simulate computer networks, most multi-agent platforms lack support for this kind of resource allocation. We target such multi-agent plat- forms and offer an easy method to implement the missing functionality by the agent designer. The introduced method assigns two additional message buffers to each agent, which are used to (i) limit the number of messages an agent is able to send in one simulation round, and (ii) limit the number of messages an agent is able to process in one simulation round.