NewVectors Tools and Products
Market-Based Constraint Management (MarCon)
Agent-based techniques allow developers to decompose complex applications into relatively simple components that can be developed, deployed, and modified independently of one another. The result is simpler software that is more robust in the face of environmental changes and is much less expensive to maintain. However, the lack of centralized control makes it difficult to ensure that the agents in the community coordinate their actions to achieve a common goal.
NewVectors’ MarCon builds on the paradigm of constraint optimization. In this paradigm, the world is divided into variables that can take on different assignments and constraints on the assignments to those variables. Each constraint has an interest in some subset of the variables, and a utility that varies depending on the assignments to those variables.
Constraint optimization seeks assignments to the variables that maximize the sum of the utilities of all the constraints. MarCon extends this paradigm with market dynamics to permit the problem to be distributed across many agents while retaining global coordination.
The agents in an application often constitute implicit constraints on some set of variables. For example, NewVectors originally developed MarCon in an agent-based design system for electro-mechanical design. Each component in the system needs to agree with the other components on various design characteristics. For example, a motor and a transmission need to agree on the torque and RPM of the shaft that connects them; an engine needs to agree with the rest of a vehicle on the amount of power. Each component is a constraint, and the design characteristics are the variables to which assignments are required.
The MarCon design process begins by identifying the constraints and the variables in the problem. These are organized in a directed graph like Figure 1, in which constraints and variables alternate. Each constraint is adjacent to those variables in which it has an interest. Each variable must have at least one adjacent constraint that offers it for sale, and at least one constraint that is interested in purchasing it. In the simplest case, these relations are defined causally: a constraint sells assignments to those variables that it causally affects, and buys assignments to those variables that it cannot cause, but in which it has an interest.
In NewVectors’ MarCon, both constraints and variables are agents. Each constraint agent buys and sells assignments to variables while seeking to maximize the difference between its utility and its cost. MarCon defines run-time behaviors for both classes of agents to propagate costs (grounded by suppliers) and utilities (grounded by consumers) through the network, thus providing a global flow of price information around which the distributed, autonomous agents can organize themselves.