SPEED-UP AND APPLICATION DISTRIBUTED CONSTRAINT SATISFACTION TO COMMUNICATION-NETWORK PATH ASSIGNMENTS

The distributed constraint satisfaction is considered interesting in r ecent years as a technique which provides the basis for handling vario us problems in the distributed artificial intelligence in a formal way . The author defined formally the distributed constraint satisfaction in [18], and presented the algorithm that guarantees the completeness of the solution (the property that the solution can finally be derived even if multiple agents operate asynchronously). This paper considers the distributed constraint satisfaction algorithm, and attempts to im prove the processing speed by introducing the ordering based on heuris tics. The ordering is a technique which suppresses the expansion of th e search space by ordering the variables and the value assignments. As an application of the distributed constraint satisfaction, the commun ication path allocation problem is considered. It is shown how the com munication path assignment problem can be formulated as the distribute d constraint satisfaction. The presented method is evaluated through t he problems derived from the actual data of the communication network, and the effectiveness of the ordering is demonstrated.