Computerized system for market-based constraint optimization

• US 6,536,935 B2
• Filed: 07/23/1997
• Issued: 03/25/2003
• Est. Priority Date: 07/23/1997
• Status: Expired due to Fees

• Current Assignee: Techteam Government Solutions Incorporated (Jacobs Solutions, Inc.)
• Original Assignee: Atarum Institute
• Inventors: Sauter, John A., Ward, Allen C., Parunak, H. Van Dyke
• Primary Examiner(s): Picard, Leo
• Assistant Examiner(s): Garland, Steven R.
• Application Number:
  US08/898,989
• Publication Number:
  US 20020013631A1
• Time in Patent Office: 2,071 Days
• Field of Search: 364/148-1-1, 364/153, 364/154, 364/156, 364/468.01, 364/468.03, 364/468.09, 364/468.1, 364/488, 364/578, 705/7-10, 705/37, 705/400, 707/104, 706/19, 706/45-47, 706/919-923, 706/10
• US Class Current: 700/99
• CPC Class Codes: G05B 13/024 in which a parameter or coefficient is automatically adjusted to optimise the performance
• CPC Class Codes: G06Q 10/0635 Risk analysis of enterprise or organisation activities
• CPC Class Codes: Y10S 706/919 Designing, planning, programming, CAD, CASE

Abstract

An apparatus for determining assignments to attributes (e.g., electrical power or overall dimensional size) of components within a system. A computerized constraint network is constructed which uses constraint agents, variable agents, and task agents in order to make assignments to the attributes of the components based upon market-based constraint optimization techniques. The attributes have variables indicative of the assignments to the attributes. Constraint data structures assist the agents in determining permissible assignments for the variables. The constraint data structures use preferential rules for determining the assignments to the variables. The preferential rules indicate which assignments for the variables of the agents produce higher utility and lower cost.

Claims

1. An apparatus for determining an assignment to a variable through iterative processing which converges from ranges of assignments to a single value, the apparatus comprising:

a first constraint data structure having a first preferential rule set for determining a preferential assignment range of a first variable;

a first computer module for determining a feasible assignment range of said first variable through an iterative adjustment of said feasible assignment range which satisfies said first preferential rule set such that said feasible assignment range converges towards a single assignment value for said first variable; and

a protocol providing communication between said first computer module and said first constraint data structure to repeatedly communicate said feasible and preferential assignment ranges and said iterative adjustments thereof between said first constraint data structure and said first computer module until said feasible and preferential assignment ranges converge at said single assignment value for said first variable.

2. The apparatus of claim 1 wherein said first computer module is a computerized agent.

3. The apparatus of claim 1, wherein said first computer module comprises a variable agent for determining an assignment trimming criteria based upon said first preferential rule set.

4. The apparatus of claim 3, wherein said first variable agent repeatedly communicates with said first computer module and said first constraint data structure via said protocol.

5. The apparatus of claim 4, wherein said protocol includes a one-of exchange protocol and an any-of exchange protocol.

6. The apparatus of claim 3, wherein said first computer module further comprises a constraint agent for determining said feasible assignment range of said first variable which satisfies said first preferential rule set.

7. The apparatus of claim 6, wherein said variable agent provides trimming data to said constraint agent, said trimming data indicating a direction and an amount for narrowing said feasible assignment range.

8. The apparatus of claim 7, wherein said trimming data indicates said feasible assignment range maximizing a difference between a utility function and a cost function of said variable for said constraint agent.

9. The apparatus of claim 7, wherein said trimming data is based upon at least one item selected from a group of items consisting of curve shape, assignment range, price range and exchange protocol.

10. The apparatus of claim 9, wherein said trimming data is based upon a combination of at least two items selected from said group.

11. The apparatus of claim 9, wherein said first constraint data structure stores said at least one item.

12. The apparatus of claim 7, wherein said constraint agent repeatedly communicates said trimming data via said protocol to said first computer module and said first constraint data structure for narrowing said feasible assignment range of said variable.

13. The apparatus of claim 1, further comprising:

a second constraint data structure having a second preferential rule set for determining a second preferential assignment range of a second variable, said second constraint data structure for establishing a relationship between said first variable and said second variable;

a second computer module for determining a second feasible assignment range of said second variable through an iterative adjustment of said second feasible assignment range based on said feasible assignment range and which satisfies said second preferential rule set such that said second feasible assignment range converges towards a single assignment value for said second variable;

said protocol providing communication between said first computer module, said second computer module and said second constraint data structure to repeatedly communicate said feasible and preferential assignment ranges and said iterative adjustments thereof to said apparatus until said feasible and preferential assignment ranges converge at said single assignment value for said second variable.

14. The apparatus of claim 13, wherein said first and second computer modules are computerized agents.

15. The apparatus of claim 13, wherein said second variable is an input to a third computer module, said third computer module determining a third feasible assignment range to a third variable based upon said preferential assignment range of said variable.

16. The apparatus of claim 15, wherein said second and third computer modules provide respectively a second and third bid for acquiring said variable as said input.

17. The apparatus of claim 16, wherein said first computer module includes a variable agent for providing a timing function to indicate when said second and third bids are to be processed by said first computer module.

18. The apparatus of claim 16, further comprising a variable agent for aggregating said second and third bids and providing a recommendation to said first, second, and third computer modules with respect to a price and said second preferential assignment range for said second variable.

19. The apparatus of claim 18, wherein said second and third bids each have a buy price function, each of said buy price functions representing a price to be paid by a computer object for said particular assignment to said first variable.

20. The apparatus of claim 19, wherein said buy price function of said second bid is based on trimming data provided by said second computer module and said buy price function of said third bid is based on trimming data provided by said third computer module.

21. The apparatus of claim 20, wherein said trimming data associated with said second and third computer modules indicate a relationship between said price and said second and third feasible assignment ranges for said first variable.

22. The apparatus of claim 19, wherein said buy price functions provided by said second and third computer modules are used by said first computer module to determine a difference between a utility function and a cost function for selecting between said second and third bids.

23. The apparatus of claim 22, wherein said first computer module has a sell price function representing a price to be offered to said first computer module for said feasible assignment range of said variable.

24. The apparatus of claim 23, wherein said sell price function is based upon a curve shape of said first computer module.

25. The apparatus of claim 23, wherein said utility function for providing said feasible assignment range is determined based upon said sell price function of said first computer module and upon said buy price functions of said second and third computer modules.

26. The apparatus of claim 25, further comprising a variable agent for determining a non-overlap situation based upon an evaluation of said sell price function of said first computer module and upon said buy price functions of said second and third computer modules.

27. The apparatus of claim 26, wherein said variable agent communicates a non-overlap data signal to said first, second, and third computer modules via said protocol when said variable agent determines a non-overlap situation.

28. The apparatus of claim 26, wherein said variable agent communicates a non-overlap data signal to a computer-human interface via said protocol when said variable agent determines a non-overlap situation.

29. The apparatus of claim 28, wherein said second computer module includes a human-computer interface for receiving from a human input related to said feasible assignment range of second variable by said second computer module.

30. The apparatus of claim 29, wherein said human-computer interface is an additive computer-human interface.

31. The apparatus of claim 29, wherein said human-computer interface is a base+attribute human-computer interface.

32. The apparatus of claim 13, wherein said feasible assignment ranges of said first and second variables are determined substantially simultaneously.

33. The apparatus of claim 13, wherein said second computer modules communicates a preferred buy range of assignments for said first variable to said first computer module via said protocol.

34. The apparatus of claim 33, wherein said second computer module includes a second constraint agent for determining said preferred buy range of assignments for said first variable.

35. The apparatus of claim 34, wherein said first computer module includes a first constraint agent, said second constraint agent communicating said preferred buy range of assignments to said first constraint agent.

36. The apparatus of claim 35, wherein a variable agent communicates said preferred buy range of assignments from said second constraint agent to said first constraint agent via said protocol.

37. The apparatus of claim 35, wherein said first constraint agent communicates a preferred sell range of assignments for said first variable to said second constraint agent via said protocol.

38. The apparatus of claim 37, wherein a variable agent communicates said preferred sell range of assignments from said first constraint agent to said second constraint agent via said protocol.

39. The apparatus of claim 38, wherein said preferred buy range of assignments is based upon a buy range curve shape and said preferred sell range of assignments is based upon a sell range curve shape.

40. The apparatus of claim 38, wherein said variable agent provides a narrowing recommendation to said second constraint agent based upon said preferred sell and buy ranges of assignments of said first and second constraint agents.

41. The apparatus of claim 40, wherein said first and second constraint agents each determine a degree of satisfaction ranging from 0 to 1 based upon said preferential assignment range of said variable.

42. The apparatus of claim 40, wherein said preferred buy range of assignments is based upon a buy range curve shape and said preferred sell range of assignments is based upon a sell range curve shape.

43. The apparatus of claim 42, wherein said narrowing recommendations by said variable agent are determined based upon aggregating said buy range curve shape and said sell range curve shape.

44. The apparatus of claim 40, wherein said sell range of assignments of said variable for said first constraint agent is based upon a first figure of merit.

45. The apparatus of claim 44, wherein said first figure of merit for said first constraint agent is based upon a utility function and a cost function associated with said feasible assignment range of said variable.

46. The apparatus of claim 44, wherein said first figure of merit is based upon an internal operation cost function of said first constraint agent.

47. The apparatus of claim 44, wherein said first figure of merit is based upon a net cost function of said first constraint agent in purchasing an assignment of said variable for which said first constraint agent is a buyer.

48. The apparatus of claim 44, wherein said first figure of merit is based upon an internal utility function for making an assignment of said variable for which said first constraint agent is a seller.

49. The apparatus of claim 44, wherein said first figure of merit is based upon a utility function of said first constraint agent gained by selling said variable to another constraint agent.

50. The apparatus of claim 44, wherein said first constraint data structure stores said first figure of merit.

51. The apparatus of claim 40, wherein said buy range of assignments of said variable for said second constraint agent is based upon a second figure of merit.

52. The apparatus of claim 51, wherein said second figure of merit for said second constraint agent is based upon a utility function and a cost function associated with said second feasible assignment range to said variable.

53. The apparatus of claim 52, wherein said second figure of merit is based upon an internal operation cost function of said second constraint agent.

54. The apparatus of claim 52, wherein said second figure of merit is based upon a net cost function of said second constraint agent in purchasing an assignment of said variable for which said second constraint agent is a buyer.

55. The apparatus of claim 52, wherein said second figure of merit is based upon an internal utility function for making an assignment of said variable for which said second constraint agent is a seller.

56. The apparatus of claim 52, wherein said second figure of merit is based upon a utility function of said second constraint agent gained by selling said variable to another constraint agent.

57. The apparatus of claim 52, wherein said second constraint data structure stores said second figure of merit.

58. The apparatus of claim 37, wherein said preferred sell and buy ranges of assignments of said first and second constraint agents are expressed in substantially equivalent currency units.

59. The apparatus of claim 58, wherein said currency units are a currency units of a predetermined geographical region.

60. The apparatus of claim 13, wherein said second computer module has an internal cost and an internal utility, said second computer modules acquiring an assignment to said variable from said first computer module, when an offer by said second computer module for said variable is substantially equal to a summation of said internal cost, said internal utility and an offer provided by another computer module which has offered to purchase said variable.

61. The apparatus of claim 13, wherein at least one of said first and second constraint data structures includes an implicit constraint.

62. The apparatus of claim 1, wherein said first computer module has an internal cost and an internal utility, said first computer module determining said assignment of said variable when an asking price by said first computer module for said variable is substantially equal to a summation of said internal cost, said internal utility and a price provided by another computer module which has offered to purchase said variable.

63. The apparatus of claim 1, further comprising a task agent for providing a tax on said first computer module when said first computer modules determine said preferential assignment range to said first variable in a time frame greater than a predetermined threshold.

64. The apparatus of claim 63, wherein said task agent provides a grant to said first computer module when said first computer module determines said preferential assignment range to said variable in a time frame less than a predetermined threshold.

65. The apparatus of claim 1, further comprising a task agent for providing a grant to said first computer module when said first computer module determines said preferential assignment range to said variable in a time frame less than a predetermined threshold.