Modeling and controlling AMoD systems

Spatial queueing model of AMoD systems

At a high level, an AMoD system can be mathematically modeled as follows. Consider a given environment, where a fleet of self-driving vehicles fulfills transportation requests. Transportation requests arrive according to an exogenous dynamical process with associated origin and destination locations within the environment. The transportation request arrival process and the spatial distribution of the origin-destination pairs are modeled as stochastic processes, leading to a probabilistic analysis. Transportation requests queue up within the environment, which gives rise to a network of spatially-localized queues dynamically served by the self-driving vehicles. Such network is referred to as “spatial queueing system.” Performance criteria include the availability of vehicles upon the request's arrival

Fig. 19.2 A spatial queueing model of an AMoD system entails an exogenous dynamical process that generates “transportation requests” (yellow dots) at spatially-localized queues. Self-driving vehicles (represented by small car icons) travel among such locations according to a given network topology to transport passengers.

(i.e., the probability that at least one vehicle is available to provide immediate service) or average wait times to receive service. The model is portrayed in Figure 19.2.

Controlling a spatial queueing system involves a joint task allocation and scheduling problem, whereby vehicle routes should be dynamically designed to allocate vehicles to transportation requests so as to minimize, for example, wait times. In such a dynamic and stochastic setup, one needs to design a closed-loop control policy, as opposed to open-loop preplanned routes. The problem combines aspects of networked control, queueing theory, combinatorial optimization, and geometric probability (i.e., probabilistic analysis in a geometrical setting). This precludes the direct application of “traditional” queueing theory due to the complexity added by the spatial component (these complexities include, for example, congestion effects on network edges, energy constraints, and statistical couplings induced by the vehicles' motion [17, 19, 20]). It also precludes the direct application of combinatorial static optimization, as the dynamic aspect of the problem implies that the problem instance is incrementally revealed over time and static methods can no longer be applied. As a consequence, researchers have devised a number of alternative approaches, as detailed in the next section.