Coordination of distributed agents frequently involves globally conflicting solutions to multiple local objectives. While much computer research on support of collaborative concerns global metrics for optimization, decision support, and negotiation, a basic coordination function is support of Pareto optimality[5].
It is frequently difficult to find a global objective function even for problems that otherwise can be easily mapped into integer programming (IP), a general technique for satisfying multiple objectives with constraints. This is because it is difficult to assign a metric to different objectives. For example, how should the cost of the artifact be weighted with respect to its time to market, weight, or various features? The difficulty of generating an ``objective'' function is increased by the fact that even small numeric changes in weights can generate very different solutions[3].
When problem solving is distributed over multiple agents with expertise in different domains, the difficulty is exacerbated. For example, an electronics engineer may want to use a position sensor that the mechanical engineer finds too heavy for the gimbal and motors of an artifact they are collaboratively designing. The resolution of such a conflict is often not subject to any objective algorithm. Such conflicts are likely to be resolved by intervention of a manager or simply the give and take of normal engineering discussion. An objective function is simply not an appropriate tool for support of such conflicts.
There are decision support tools for providing argumentation in such a situation[3,15] and for attempting to optimize multiple objective decisions[7]. It is sometimes feasible to at least perform local optimization over weighted objectives[2]. We do not here address all of the problems in these approaches beyond noting that there seems to be no general solution to multiple objective optimization. This suggests that approaches to negotiating and resolving conflicts must be domain knowledge-intensive.
However, there is a simple useful somain-independent formalism applicable to the satisfaction of multiple objectives among distributed agents: the tracking of Pareto optimality.
``Tracking'' means that the problem solver is automatically notified of Pareto optimality loss and of the particular opportunity to improve the design. This functionality has three important properties for multiple objective problem solving: 1) opportunities to improve the local solution are noticed that otherwise would be lost, 2) resolution of conflicts may be delayed indefinitely, and 3) ``thrashing'' during problem solving backtracking is prevented. These properties are especially important when problem solving is distributed.
Pareto optimality[5] is an economics term for describing a solution for multiple objectives.
Pareto optimality is a predicate. While one may be able to assign a quantitative metric, such as the area of the circle, the answer as to whether the global solution is Pareto optimal is ``yes" or ``no". It does not matter initially how much a circle can be enlarged, only that it can be. How much is to be evaluated after the possibility is noted. A corollary is that Pareto optimality does not address local extrema with respect to any utility. Neither does Pareto optimality provide a method for choosing among preferences or alternatives.
Nevertheless, tracking Pareto optimality is an important function for distributed agents. Detection of a lack of Pareto optimality is an alert to an opportunity to improve the design that otherwise might be missed, especially when no one engineer understands all of the design dependencies. Once such a lack has been detected, then special purpose algorithms can provide various evaluation functions that are likely to be domain-specific. Tracking Pareto optimality does not preclude such methods and it does not require an objective function that must compare ``apples and oranges'' in complex domains: it is a domain-independent function.
In addition to such notification, the tracking of Pareto optimality also offers the ability to track the various ways in which any given conflict might be resolved. The result is an an OR tree of AND possiblities that might be considered by all the participants. Furthermore, such tracking can take into account subsumption relationships to offer some domain-independent advice about resulution. For instance, if one method of resolving a conflict would include in its effects a proper subset of the effects of some other method, then parsimony suggests the latter method be tried first.
[2] Descotte, Y. & Latombe, J. (1985). Making Compromises among Antagonist Constraints in a Planner. Artificial Intelligence 27, pp. 183-217.
[3] Dhar, V. & Raganathan, N. (1990). An Experiment in Integer Programming. Communications of the ACM, March .
[4] Doyle, J. (1985). Reasoned Assumptions and Pareto Optimality. Proc. of the 9th IJCAI, pp. 87-90.
[5] Feldman, Allan M. (1980). Welfare Economics and Social Choice Theory. Kluwer, Boston.
[6] James G. McGuire et al. (1993). SHADE: A Medium for SHaring Design Knowledge among Engineering Tools. Journal of Concurrent Engineering: Applications and Research (CERA), 1(2), September.
[7] Korhonen, P. & Wallenius, J. (1990). A Multiple Objective Linear Programming Decision Support System. Decision Support Systems, 6, pp 243-251.
[8] Jintae, Lee, & Lai, Kum-Yew (1991). A Comparative Analysis of Design Rationale Representations. MIT Sloan School TR CCS TR 121, May.
[9] Park, H. et al. (1994). An Agent-Based Approach to Concurrent Cable Harness Design. Artificial Intelligence for Engineering Design, Analysis and Manufacturing (AIEDAM), Vol. 8, pp. 45-61, March.
[10] Park, H. (1995). Modeling of Collaborative Design Processes for Agent-Assisted Product Design. Dissertation, Center for Design Research, Stanford U., January.
[11] Petrie, C. (1991). Context Maintenance. Proc. 9th Nat. Conf. on AI, pp. 288-295, AAAI Press, July.
[12] Petrie, C. (1992). Constrained Decision Revision. Proc. 10th Nat. Conf. on AI, pp. 393-400, AAAI Press, July.
[13] Petrie, C. (1993). The Redux' Server. Proc. Internat. Conf. on Intelligent and Cooperative Information Systems (ICICIS), Rotterdam, May.
[14] Petrie, C.et al. (1994). Design Space Navigation as a Collaborative Aid. Proc. AI in Design: 3rd Internat. Conf., pp. 611-623. Lausanne.
[15] Ramesh, B. &Dhar, V. (1994). Representing and Maintaining Process Knowledge for Large-Scale Systems Development. IEEE Expert, 9,2, pp. 54-59.
[16] Wilkens, D. (1988). Practical Planning, Morgan Kaufmann, San Mateo.