Distributed Route Planning and Scheduling via Hybrid Conflict Resolution

This paper is concerned with decentralized planning and scheduling where the information for decision making resides within local agents. When considering a decentralized approach, the goal is not primarily on achieving global optimality. For instance, [Greenstadt et al. 2006] studies the tradeoff in the Distributed Constraint Optimization (DCOP) problem on efficiency, privacy and optimality. In principle, even if the problem size does allow for a centralized approach, there is still a heavy penalty on the excessive sharing of information. This penalty is a combined consequence of issues such as information security/privacy. Furthermore, if response time is critical, the network communication/latency time becomes a limiting factor. The alternative extreme is to have a fully decentralized scheme which may also not be ideal in terms of excessive negotiations (in terms of number or size of messages) needed to obtain global consistency. An interesting research challenge is to derive a reasonable balance between the two extreme approaches which best suits the problem to be tackled.

I. Introduction

This paper is concerned with decentralized planning and scheduling where the information for decision making resides within local agents. When considering a decentralized approach, the goal is not primarily on achieving global optimality. For instance, [Greenstadt et al. 2006] studies the tradeoff in the Distributed Constraint Optimization (DCOP) problem on efficiency, privacy and optimality. In principle, even if the problem size does allow for a centralized approach, there is still a heavy penalty on the excessive sharing of information. This penalty is a combined consequence of issues such as information security/privacy. Furthermore, if response time is critical, the network communication/latency time becomes a limiting factor. The alternative extreme is to have a fully decentralized scheme which may also not be ideal in terms of excessive negotiations (in terms of number or size of messages) needed to obtain global consistency. An interesting research challenge is to derive a reasonable balance between the two extreme approaches which best suits the problem to be tackled.