The future of scheduling-DAI?

It appears that AI scheduling research is moving outwards in a number of different directions: constraint-based reasoning, distributed AI, stochastic search, iterative repair, look-ahead techniques. The author is not suggesting that the community is `pulling apart´, merely that the net is being thrown further, and to good effect. He believes that there is another promising direction to be explored. When we solve some combinatorial problem, the order that we choose to make our decisions may have a profound effect on the difficulty in solving that problem. This `order´ is sometimes referred to as the instantiation order. Clearwater, B.A. Huberman, and T. Hogg (1991) published a paper on a distributed solution to the constraint satisfaction problem. We are given a single problem, and a number of agents, where each agent is capable of solving that problem on its own. The agents are each given a copy of the problem but attempt to solve it using different instantiation orders. That means that the agents navigate through the same problem space, but start from different positions. During the process of exploration the agents are allowed to share their discoveries. The authors claim that this can result in a super-linear speed up, or a `combinatorial implosion´