A common way to characterize problems having a good parallel solution is NC; roughly
NC: Problems solvable in polylog time on a polynomial number of processorswhere "polylog" means "O( log(n)k ) for some k".
Problems in P can also be "P-complete" meaning they are the hardest of the problems in P. The relationship between NC and P-complete for parallel complexity is analogous to that between P and NP-complete in sequential complexity. See Chapter 15 of Papadimitriou's book "Computational Complexity" for a more technical description.
The relevance of these classes is that the strict timebounds, and good scaling behavior, that are likely to be necessary for a distributed system ANT system are likely to be captured by requiring a at worst polylog scaling of runtime. Also, of course, it is unlikely an exponential number of ANTS would be available for computation, and so the complexity class NC is likely to be relevant to a characterization of what is efficiently achievable.
Many optimization problems to be solved by ANTS are both over-constrained and NP-hard. This is implicitly met by relaxing the requirement of optimality, instead taking "good enough" solutions, and also of relaxing some constraints. Relaxation of constraints and optimality can reduce the complexity to P. However for distributed ANT systems we will also need to ensure that the relaxations are chosen, whether implicitly or explicitly, so as to reduce the complexity to NC. Research is in progress as to what forms of negotiation and search will achieve this.
A common problem during search is that it can repeatedly find the same unsatisfiable combination of variables. The standard remedy is to learn such unsatisfiable combinations, and just keep them as extra "derived constraints". However, this has the problem that the number of derived constraints can rapidly become so large that the overheads of scanning them offsets the gains. Hence, it is important to find heuristics for which derived constraints, "no-goods", should be retained. A particularly successful recipe is that used in "relevance bounded learning" for SAT problems.
Derived constraints also potentially contain useful information about the
For a general informal introduction see "The Pseudo-Boolean Library"
However, propositional satisfiability is particularly poor at problems involving arithmetic, and hence a poor choice for many resource constrained problems. Hence, we have extended RelSAT to "PARIS" that solves problems expressed in the Pseudo-Boolean representation. Work is on progress testing out PARIS on instances from the ATTEND project within ANTS.
A major challenge within distributed systems is the lack of bandwidth for communications between different computational nodes.
Typically, distributed search methods will require the communication of single solutions or partial solutions. However, in many search problems, solutions will occur in clusters. if we can express the entire solution cluster in a compact fashion, then a single message containing a cluster might be able to replace many messages with individual solutions.
Progress on this is reported in