Graph-based negotiation system with encapsulated constraint solver

• US 20050108036A1
• Filed: 05/28/2004
• Published: 05/19/2005
• Est. Priority Date: 11/14/2003
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Castellani, Stefania, Andreoli, Jean-Marc
• Granted Patent: US 7,647,212 B2
• Time in Patent Office: Days
• US Class Current: 705/80
• CPC Class Codes: G06Q 40/04 Trading; Exchange, e.g. stocks, commodities, derivatives or currency exchange
• CPC Class Codes: G06Q 50/188 Electronic negotiation

Abstract

A constraint solver is encapsulated in a service adapted to participate in a negotiation. In operation, the system constructs a graph in its memory for negotiating a set of actions to be performed by selected ones of a plurality of participants. Each node of the graph defines a negotiation context that has associated therewith a constraint store with at least a set of domain constraints stored therein that limit during the negotiation a set of semantic constraints of the service on variables of the constraint solver.

Claims

1. In a system having a processor for carrying out a negotiation concerning a set of actions to be performed by selected ones of a plurality of participants, a method for carrying out the negotiation with at least one of the plurality of participants encapsulating a constraint solver in a service, comprising:

defining processing instructions in a memory of the system for carrying out the negotiation using the service encapsulating the constraint solver; and

executing the processing instructions for carrying out the negotiation with the service encapsulating the constraint solver;

wherein said executing the processing instructions for carrying out the negotiation with the service encapsulating the constraint solver further comprises;

(A) establishing encapsulation input in the memory that includes;

(a) a mapping between aspects of parameters of the service and corresponding variables of the constraint solver, (b) a translation between negotiation statements on the aspects of the parameters of the service and domain constraints imposed on the corresponding variables of the constraint solver, and (c) a set of semantic constraints of the service on variables of the constraint solver;

(B) constructing a graph in the memory for negotiating the set of actions to be performed;

each node of the graph defining a negotiation context that has associated therewith a constraint store with at least a set of domain constraints stored therein;

(C) propagating constraints defined by the set of semantic constraints and the set of domain constraints associated with nodes of the graph to other participants in the negotiation as domain constraints augment the set of semantic constraints during the negotiation.

2. The method according to claim 1, wherein the processing instructions are stored in memory of the system and are executed by one or more processors of the system.

3. The method according to claim 1, wherein the parameters specify print-jobs.

4. The method according to claim 3, wherein an aspect of the print-jobs is one of price, size, and delivery date.

5. The method according to claim 1, where the negotiation is defined by a negotiation problem statement.

6. The method according to claim 1, wherein the set of domain constraints are first propagated across each constraint store of the graph before propagating the set of domain constraints to other participants of the negotiation.

7. The method according to claim 6, wherein the set of domain constraints are first propagated within each constraint store of the graph before propagating the set of domain constraints across each constraint store of the graph.

8. The method according to claim 1, wherein the set of domain constraints are first propagated within each constraint store of the graph before propagating the set of domain constraints to other participants of the negotiation.

9. A system having a processor for carrying out a negotiation concerning a set of actions to be performed by selected ones of a plurality of participants, the negotiation being carried out with at least one of the plurality of participants encapsulating a constraint solver in a service, comprising:

a memory for storing processing instructions for carrying out the negotiation using the service encapsulating the constraint solver; and

a processor for executing the processing instructions for carrying out the negotiation using the service encapsulating the constraint solver;

the processor in executing the processing instructions for carrying out the negotiation using the service encapsulating the constraint solver;

(A) establishing encapsulation input in the memory;

(a) a mapping between aspects of parameters of the service and corresponding variables of the constraint solver, (b) a translation between negotiation statements on the aspects of the parameters of the service and domain constraints imposed on the corresponding variables of the constraint solver, and (c) a set of semantic constraints of the service on variables of the constraint solver;

(B) constructing a graph in the memory for negotiating the set of actions to be performed;

each node of the graph defining a negotiation context that has associated therewith a constraint store with at least a set of domain constraints stored therein;

(C) propagating constraints defined by the set of semantic constraints and the set of domain constraints associated with nodes of the graph to other participants in the negotiation as domain constraints augment the set of semantic constraints during the negotiation.

10. The system according to claim 9, further comprising one or more additional processors for executing the processing instructions to carry out the negotiation.

11. The system according to claim 9, wherein the parameters specify print-jobs.

12. The system according to claim 11, wherein an aspect of the print-jobs is at least one of price, size, and delivery date.

13. The system according to claim 9, where the negotiation is defined by a negotiation problem statement.

14. The system according to claim 9, wherein the set of domain constraints are first propagated across each constraint store of the graph before propagating the set of domain constraints to other participants of the negotiation.

15. The system according to claim 14, wherein the set of domain constraints are first propagated within each constraint store of the graph before propagating the set of domain constraints across each constraint store of the graph.

16. The system according to claim 9, wherein the set of domain constraints are first propagated within each constraint store of the graph before propagating the set of domain constraints to other participants of the negotiation.

17. An article of manufacture for use in a machine comprising:

a memory;

processing instructions stored in the memory for carrying out a negotiation concerning a set of actions to be performed by selected ones of a plurality of participants, the negotiation being carried out with at least one of the plurality of participants encapsulating a constraint solver in a service;

wherein the processing instructions in carrying out the negotiation with at least one of the plurality of participants encapsulating a constraint solver in a service;

defining processing instructions in a memory of the system for carrying out the negotiation using the service encapsulating the constraint solver; and

executing the processing instructions with the processor for carrying out the negotiation with the service encapsulating the constraint solver;

the processor in executing the processing instructions for carrying out the negotiation with the service encapsulating the constraint solver;

(A) establishing encapsulation input in the memory;

(a) a mapping between aspects of parameters of the service and corresponding variables of the constraint solver, (b) a translation between negotiation statements on the aspects of the parameters of the service and domain constraints imposed on the corresponding variables of the constraint solver, and (c) a set of semantic constraints of the service on variables of the constraint solver;

(B) constructing a graph in the memory for negotiating the set of actions to be performed;

each node of the graph defining a negotiation context that has associated therewith a constraint store with at least a set of domain constraints stored therein;

(C) propagating constraints defined by the set of semantic constraints and the set of domain constraints associated with nodes of the graph to other participants in the negotiation as domain constraints augment the set of semantic constraints during the negotiation.

18. The article of manufacture according to claim 17, wherein the parameters specify print-jobs and an aspect of the print-jobs is at least one of price, size, and delivery date.

19. The article of manufacture according to claim 17, wherein the set of domain constraints are first propagated across each constraint store of the graph before propagating the set of domain constraints to other participants of the negotiation.

20. The article of manufacture according to claim 19, wherein the set of domain constraints are first propagated within each constraint store of the graph before propagating the set of domain constraints across each constraint store of the graph.

21. The article of manufacture according to claim 17, wherein the set of domain constraints are first propagated within each constraint store of the graph before propagating the set of domain constraints to other participants of the negotiation.