| Abstract: | COMMUNICATING PROBLEM SOLVERS CAN COOPERATE IN VARIOUS WAYS, SUCH AS NEGOTIATING OVER TASK ASSIGNMENTS, EXCHANGING PARTIAL SOLUTIONS TO CONVERGE ON GLOBAL RESULTS, AND PLANNING INTERACTIONS THAT HELP EACH OTHER PERFORM THEIR TASKS BETTER. WE INTRODUCE A NEW FRAMEWORK THAT SUPPORTS DIFFERENT STYLES OF COOPERATION BY USING PARTIAL GLOBAL PLANS TO SPECIFY EFFECTIVE, COORDINATED ACTIONS FOR GROUPS OF PROBLEM SOLVERS. IN THIS FRAMEWORK, PROBLEM SOLVERS SUMMARIZE THEIR LOCAL PLANS AND SELECTIVELY EXCHANGE INFOR- MATION TO BUILD UP DYNAMIC MODELS OF NETWORK ACTIVITY, WHICH THEY IN TURN USE TO FORM PARTIAL GLOBAL PLANS. HOWEVER, BECAUSE NETWORK AND PROBLEM CHARACTERISTICS CAN CHANGE AND COMMUNICATION CHANNELS HAVE DELAYS AND LIMITED CAPACITY, PROBLEM SOLVERS' MODELS AND PARTIAL GLOBAL PLANS MAY BE INCOMPLETE, OUT-OF-DATE, AND INCONSISTENT. OUR MECHANISMS ALLOW PROBLEM SOLVERS TO AGREE ON CONSISTENT PARTIAL GLOBAL PLANS WHEN POSSIBLE, AND TO LOCALLY FORM PARTIAL GLOBAL PLANS THAT LEAD TO SATISFACTORY COOPERATION EVEN IN RAPIDLY CHANGING ENVIRONMENTS WHERE COMPLETE AGREEMENT IS IMPOSS- IBLE. IN THIS PAPER, WE DESCRIBE THE MECHANISMS, KNOWLEDGE REPRESENTATIONS, AND ALGORITHMS THAT WE HAVE DEVELOPED FOR GENERATING AND MAINTAINING PARTIAL GLOBAL PLANS IN A DISTRIBUTED SYSTEM. WE USE EXPERIMENTS TO ILLUS- TRATE HOW THESE MECHANISMS IMPROVE AND PROMOTE COOPERATION IN A VARIETY OF STYLES. |
