The MarCon algorithm: A systematic market approach to distributed constraint problems

摘要

MarCon (Market-based Constraints) applies market-based control to distributed constraint problems. It offers a new approach to distributing constraint problems that avoids challenges faced by current approaches in some problem domains, and it provided a systematic method for applying markets to a wide array of problems. Constraint agents interact with one another via the variable agents in which they have a common interest, using expressions of their preferences over sets of assignments. Each variable integrates this information from the constraints interested in it and provides feedback that enables the constraints to shrink their sets of assignments until they converge on a solution. MarCon originated in a system for supporting supporting human product designers, and its mechanisms are particularly useful for applications integrating human and machine intelligence to explore implicit constraints. MarCon has been tested in the domain of mechanical design, in which its set-narrowing process is particularly useful.