Pruning can also be performed using state dominance. For instance, assume that a location on the map is reached in the search on two different pathways. As compared to the second one, the first pathway requires at most the same travel time, at most the same walking time, at most the same cycling time, and at most the same number of legs. Furthermore, the first pathway is reached on a sequence of deterministic transitions (i.e., following it does not depend on chance). Then the first pathway dominates the second, and the latter can be pruned away. Heuristics and pruning techniques are key in making an algorithm such as AO* scale to the size of a real city.
Licensing. The planning engine has been developed from scratch, being free from any potential licensing issues. A customized development allowed to focus on an efficient, domain-specific implementation.
Architecture and tooling. In a deployed system, a multimodal journey planning engine is a component of a larger eco-system, which we call a multi-modal journey advisor. Besides, the planner, modules include: aggregating all network data into a so-called network snapshot; keeping track of active trips, with monitoring, detecting plan invalidation, and replanning; interaction with the user, through an API and apps; collecting data and presenting meaningful analyses to an operator.
Docit (Botea et al. 2016) is a multi-modal journey advisor that implements the functionality summarized in the previous paragraphs (see Figure 2). Dija is integrated in Docit as a multi-modal journey planner, and so is also a planning system called Frequency Planner (Nonner 2012).
Knowledge engineering: data acquisition and representation. The knowledge about a multi-modal transportation network can be static or dynamic. Static data is easier to create and more broadly available. For instance, sources such as OpenStreetMap provide static roadmap data. Data about scheduled public transport vehicles (e.g., buses and trains) can be represented in the GTFS4 format. More and more cities make static public transport data available using the GTFS format. In Docit, GTFS was extended in the following directions: represent uncertainty in the data (e.g., in the arrival and the departure times of buses); and integrate additional transport modes, such as private cars, shared cars, taxis, and bicycles in a shared network.
Dynamic data, such as traffic conditions, or updates in the actual schedules of buses, require sensing capabilities (e.g., cars reporting their speed, buses reporting their GPS location), and an expensive additional infrastructure. When Docit was deployed in cities such as Rome, Italy and Haifa, Israel, as part of the EU project Petra, dynamic updates in the public transport schedules were provided to the system.
Visualisation. Docit computes contingent journey plans, for a better robustness against failures in a network with dynamic events (see Figure 3). While contingent plans can have a tree shape in general, most users are accustomed to deterministic, sequential plans. We found that contingent plans are more difficult to explain to an audience with no AI knowledge. An interesting lesson learned from this work is that a useful feature can also be a hard-to-grasp feature. This could further creating a potential barrier, making the adoption of the feature sensitive to how well the users understand it.
Visualising in a mobile app a contingent plan, and key summary data about the contingent plan, is more challenging as compared to using sequential plans. Docit provides an API for the interaction with a mobile app. Third parties can develop apps complying with the API. Given a contingent plan, a mobile app developed at IBM Research, Ireland visualises possible arrival time, with a probability associated with each possible arrival time.
Benchmarking value: experimental, qualitative. As previous work focused on deterministic multi-modal journey planning, no benchmarking data was available about multi-modal journey planning under uncertainty. An important benefit stemming from systems such as Docit is the opportunity to learn about the performance and the potential of uncertainty-aware multi-modal journey planning. This allows comparing contingent planning and deterministic planning in terms of the quality of plans, speed of computing plans, and scalability.
Plan execution and monitoring. Besides plan computation, a multi-modal journey advisor should contain other important components, such as monitoring the progress of a trip, monitoring the status of the transport network, detecting cases when a current plan is invalidated, and perform replanning. Botea and Braghin (2015) have presented a technique to simulate ahead the execution of the plan, given new information about the transportation network. The outcome helps decide whether recent changes in the transportation network, not available at the time when the journey plan was computed, impact the plan at hand. If so, notify the user and possibly trigger re-planning.
Other remarks. As AI researchers, we might be more excited about developing innovative approaches, such as moving from deterministic planning to non-deterministic planning in a domain where deterministic planning is a broadly embraced de facto standard. Yet, regardless of whether it implements a novel technology, a deployed system needs to feature many “standard” features. In multi-modal journey planning, examples of “standard” features include the following options to a user: choose between a departure time and an arrival time; choose a subset of transport modes acceptable in a trip; set max acceptable values for the total walking time, the number of legs in a journey, and the cycling time, for example; a user-friendly mobile app. The effort required to implement these is very considerable and the level of detail can be crucially important.
Planning for Web Services
Commercial IT solutions were for long built as monolithic applications in an ad-hoc manner resulting in poor reuse of software assets, longer time-to-delivery and costlier software maintenance costs. Viewing software components as (web-enabled) services, the promise of automated (web) service composition is that new applications can be seamlessly assembled from existing components (services) meeting overall functional and non-functional requirements.
Services oriented computing was being implemented in early 2000s using web services standards (e.g., WSDL, SOAP and BPEL4WS) and lately, using REpresentational State Transfer (REST) APIs (Application Programming Interfaces).The relative trade-offs between the two architectural styles was studied by (Pautasso et al. 2008) based on the architectural decisions that must be made and the number of available alternatives. The authors concluded that REST is well suited for basic, ad hoc integration scenarios, while web services standards are suitable for operational service requirements of enterprise computing. The automated composition problem, however, is common regardless of implementation style. For more details on approaches for web services composition (WSC) and issues, see (Lemos et al. 2015; Srivastava and Koehler 2003).