Opportunistic planning for a fleet of transportation robots

The Dynamic Transportation-Planning Problem (DTPP) embodies a class of real -world applications that involve the reactive routing and scheduling of a f leet of vehicles in response to dynamically changing transportation demands . Examples include mobile robots in a warehouse, taxis in an urban road net work, or aeroplanes for medical evacuation. In contrast with the Vehicle Ro uting Problem, for which a plethora of techniques is available, few approac hes exist that permit the efficient deployment of a large number of vehicle s in a changing environment. This paper highlights the characteristic featu res of the problem, reviews possible approaches and existing techniques, an d proposes a heuristic solution to the DTPP using a Blackboard-based approa ch. The resulting application is an intelligent transportation planning sys tem (ITPS) for a fleet of automated robot taxis, based on the generic assum ption-based truth maintained Blackboard shell (GATMBS) and comprising traff ic simulation models as well as various monitoring and problem-solving stra tegies for assignment and routing. The Blackboard architecture supports the dynamic alteration of planned routes in response to changes in traffic con ditions and passenger requests. A prototype of the ITPS has been validated in simulation using a small fleet of robot taxis with randomly generated ro ad networks, background traffic load, and passenger requests. (C) 2001 Else vier Science Ltd. All rights reserved.