Optimization and coordination of multiagent systems using principled negotiation

Principled negotiation coordinates the actions of agents with different interests, allowing distributed optimization. In principled negotiation, agents search for and propose options for mutual gain. If the other agents agree to the proposal, it is implemented. Under certain conditions, an agent can search for options for individual gain without impacting other agents. In these cases, the agent can negotiate with a coordinator, rather than obtain agreement from all other agents. The tenets of principled negotiation are outlined and stated mathematically. Two examples are formulated to test principled negotiation performance. The first has no coupling between the agent actions if coordination criteria are met. Principled negotiation allows the agents to achieve a solution as good as that achieved by a centralized controller with perfect knowledge. The second problem, based on the air traffic management problem of negotiating arrival slots, is highly coupled, constraining each agent's available set of actions. Principled negotiation allows agents to search options that would not be available otherwise, improving the utility function of all agents. Applied to air traffic operations, principled negotiation allows much greater freedom for optimization by system users while maintaining safety.