[go: up one dir, main page]

WO2006118193A1 - Agent et procédé de complément de restriction distribuée - Google Patents

Agent et procédé de complément de restriction distribuée Download PDF

Info

Publication number
WO2006118193A1
WO2006118193A1 PCT/JP2006/308836 JP2006308836W WO2006118193A1 WO 2006118193 A1 WO2006118193 A1 WO 2006118193A1 JP 2006308836 W JP2006308836 W JP 2006308836W WO 2006118193 A1 WO2006118193 A1 WO 2006118193A1
Authority
WO
WIPO (PCT)
Prior art keywords
data
variable
constraint
improvement
agent
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
PCT/JP2006/308836
Other languages
English (en)
Japanese (ja)
Inventor
Yasuki Iizuka
Takashi Shimojima
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Panasonic Holdings Corp
Original Assignee
Matsushita Electric Industrial Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Matsushita Electric Industrial Co Ltd filed Critical Matsushita Electric Industrial Co Ltd
Priority to JP2007514806A priority Critical patent/JPWO2006118193A1/ja
Publication of WO2006118193A1 publication Critical patent/WO2006118193A1/fr
Anticipated expiration legal-status Critical
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING OR CALCULATING; COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/004—Artificial life, i.e. computing arrangements simulating life

Definitions

  • the present invention relates to an agent that communicates with neighboring agents and obtains a solution for satisfying a constraint condition in an asynchronous manner, and an agent distributed constraint satisfaction method.
  • FIG. 29 shows the configuration of a computer that constitutes a conventional constraint satisfaction device.
  • a computer 900 includes a CPU 901, a memory 902, a display unit 903, an input unit 904, a secondary storage unit 905, and a network interface 906. Further, the secondary storage unit 905 stores initial values of variables, constraint data, and software for controlling each unit.
  • a constraint satisfaction device can generally apply its operation principle to a constraint satisfaction problem. This can be explained, for example, in Japanese Patent Laid-Open No. 11-316682 (pages 4-5) and Mitsuru Ishizuka, “Course of Information Science Core Curriculum, Knowledge Representation and Fast Reasoning” (Maruzen, 1996, p. 20, 103). — 119).
  • the constraint satisfaction problem is a set of m variables xl, x2,..., Xm and the possible values of each variable Dl, D2,..., Dm, and a set of constraints between each variable
  • P ⁇ pi, p2, ⁇ ⁇ ⁇ , pr ⁇ exists
  • predicate logic it is to find a set of variables when expression 1 is true.
  • tabu search which is a generalized local search method.
  • Tabu search has a mechanism that avoids searching for recently selected neighborhood solutions, and makes searching for neighborhoods efficient. This includes, for example, Japanese Patent Laid-Open No. 11-195 066 (page 9, Fig. 2) and Mitsuru Ishizuka "Information Science Core Curriculum Course, Knowledge Representation and Fast Inference” (Maruzen, 1996, p. 20, 103). — 119), Sadick ⁇ ⁇ Site, 1 other author, Hiroshi Shiraishi, “Latest method of combinatorial optimization algorithm” (Maruzen, 2002, p. 163), Rina's Deciter, “Constraint” 'Processing' ((USA), Morgan 'Power Ufman' Publicishers, 2003).
  • FIG. 30 is a diagram for explaining a constraint network diagram expressing the constraint satisfaction problem.
  • node 1001 indicates the variable of the constraint satisfaction problem
  • arc 1002 indicates the constraint relationship between the variables.
  • the constraint satisfaction problem can be expressed in such a constraint network diagram without losing generality because the constraint between ⁇ variables can be expressed by converting it into a binary constraint. For example, an example will be described in which each node takes one of the values “black” and “white” and the nodes at both ends of each arc cannot have the same value.
  • FIG. 31A is a constraint network diagram showing an example of an initial state of a constraint satisfaction problem
  • FIG. 31B is a constraint network diagram showing an example of a state in which a solution of the constraint satisfaction problem is defined.
  • a node with a “black” value is shown in black
  • a node with a “white” value is shown in white.
  • the values of node ⁇ 203 and node ⁇ 206 are both “black”, and a constraint violation has occurred between them.
  • a constraint violation has occurred between node ⁇ 204 and node ⁇ 205, which have the same value “white”.
  • Figure 31B shows the solution to this problem when the constraints between all nodes are met. One of them shows a fixed state. In the following description, such a restricted network diagram is used as appropriate.
  • a distributed plan such as a network resource allocation plan, a production plan including a large number of operations, or a work stoppage plan for power system equipment, and other plans.
  • a distributed constraint satisfaction device composed of multiple agents is known. It is known that the operating principle of the agents that make up this distributed constraint satisfaction device can be generally applied to distributed constraint satisfaction problems in which the variables and constraints of the constraint satisfaction problem are distributed.
  • FIG. 32 is a diagram for explaining a constraint network diagram expressing the distributed constraint satisfaction problem.
  • 1003a, 1003b, and 1003c are agents
  • a node 1001 is a variable that the agent 1003a has
  • an arc 1002 indicates a constraint relationship between these variables.
  • each agent targets some variables in the distributed constraint satisfaction problem and resolves the constraints asynchronously with agents that have neighboring constraint relationships with the target.
  • a production plan is made so that individual companies such as multiple independent companies and factories that have been signed through delivery contracts make profits, and the profits are increased as a whole. .
  • Plans are prepared independently and in parallel by each operator, and the plans are coordinated between each company.
  • This overall production planning can be generally described as a distributed constraint satisfaction problem.
  • business operators F1 to F7 individually formulate production plans for parts A to E and semi-finished products F, such as the number of products produced, inventories, and the number of deliveries. Adjust the overall plan. At this time, it is necessary to satisfy each constraint condition among business operators such as delivery date, price, production period, and production capacity.
  • each agent must maintain a large amount of constraint violation information called “no good”.
  • This algorithm is, for example, disclosed in Japanese Patent Application Laid-Open No. 11-316682 (pages 4-5), Makoto Yokoo, and three others, “Formulation and Solution of Distributed Cooperative Problem Solving by Satisfying Distributed Constraints” (The Institute of Electronics, Information and Communication Engineers) Journal D—I, 1992, Vol. 75, No. 8, p. 704—713), Makoto Yokoo, and 1 other, “Distribution constraint satisfaction algorithm: review” (autonomous agents and multi-agent systems) (USA), 2000, No. 3, IV, p. 189-212).
  • Asynchronous weak commitment search method that improves the asynchronous distributed backtracking method is known.
  • Asynchronous weak commitment search is fast by introducing the concept of priority, but it needs to hold and exchange large amounts of constraint violation information.
  • costs such as searching for the information and generating further constraint violation information depending on conditions are necessary.
  • it is necessary to distribute the restriction information between specific agents to the third agent, and security between agents cannot be maintained.
  • a diffuse breakout algorithm is known as an algorithm that does not require a knock track and does not have constraint violation information. However, under certain conditions, this algorithm may fall into a loop and fail to obtain a solution. In addition, because the constraints are weighted, it is not possible to deal with dynamic situations in which the constraints change while seeking a solution. This includes, for example, Japanese Patent Laid-Open No. 9-297689 (page 4, Fig. 1), Makoto Yokoo, and one other, "Distributed breakout: Iteratively improved distributed constraint satisfaction algorithm" (Journal of Information Processing Society of Japan, 19 1998, No. 39, No. 6, p. 1889-1897) etc.
  • the conventional agent like the conventional constraint satisfaction device, more specifically includes the hardware and software of the computer.
  • multiple agents communicate asynchronously over the network and work together to resolve constraint violations.
  • each agent tries to obtain a variable for eliminating the constraint violation state between agents asynchronously. Therefore, there is a problem that there is a high possibility of falling into a local optimal solution and a possibility of falling into an infinite loop of processing in which some agents change values in order.
  • the present invention solves such a problem, and when obtaining a variable for eliminating the constraint violation state between agents asynchronously, it does not attempt to resolve the constraint violation with only some of the agents.
  • By solving constraint violations with many agents we provide an agent in which the entire set of agents reaches the solution earlier as a result of not falling into a local optimal solution or an infinite loop.
  • the agent of the present invention is a variable storage that stores variable data indicating a current value of the solution to be obtained in an agent in which a plurality of agents obtain the solution in cooperation in an asynchronous manner.
  • a constraint storage unit for storing constraint data indicating a combination of values of variable data and variable data stored by neighboring agents, and a variable for storing variable change prohibition period data indicating a period during which the change of variable data is prohibited Generated by the change prohibition period storage unit, the improvement degree generation unit that generates the improvement degree data indicating the degree of ease with which the variable data of the own agent satisfies the constraint data, and the variable data and improvement degree generation unit Communication unit that transmits / receives improvement degree data to / from neighboring agents, improvement degree data and variable data obtained from neighboring agents Configuration to The neighborhood situation storage unit that stores the neighboring situation data, the improvement degree data generated by the improvement degree creation unit, and the improvement degree data of the neighboring agents stored in the neighborhood situation storage unit are compared, and According to the change prohibition period data, the variable data is changed to a value that satisfies the combination of the constraint data so that the constraint violation with the variable data of the neighboring agent stored in the neighborhood status storage unit is resolved, and the variable A
  • the improvement ease data includes at least the number of constraints indicating the number of constraint data, the number of constraint violations indicating the number of variable data violating the constraint data, and the variable data
  • the structure has one of the possible improvement numbers indicating the number of constraint data that can resolve the violation status, and the ease of improvement generation unit calculates the total number of constraint data for the variable data.
  • variable data and the variable data of the neighboring agent satisfy the combination of the values of the constraint data, the total number of constraint data is obtained as the constraint violation number, and the variable data and the variable data of the neighboring agent Among the constraint data that does not satisfy the constraint data value combination, the variable data is not included in the variable change prohibition period data, and the variable data value is changed. Therefore, the total number of combinations that can be changed to satisfy the combination of constraint data values is obtained, and the attribute value of the improvement ease data is generated as the number that can be improved.
  • the agent of the present invention further includes an improvement trend storage unit that stores improvement trend data indicating past transitions of the degree to which the variable data satisfies the constraint data
  • the constraint resolution unit includes: Based on the number of constraint violations included in the variable data, the improvement trend data stored in the improvement trend storage is additionally updated, and the length of the variable change prohibition period is determined according to the improvement trend data. Then, after changing the variable data, the variable change prohibition period data stored in the variable change prohibition period storage unit is updated.
  • the agent can adjust the variable change prohibition period of the variable data according to the improvement tendency of the constraint violation and prohibit the change of the variable only for the period adapted to the problem.
  • the possibility of falling into an infinite loop of only a part of the agents or falling is reduced, and as a result, the entire set of agents can reach the solution faster.
  • the improvement level generator generates the improvement level data at every first fixed time interval, and the communication unit transmits the improvement level data to neighboring agents. Configure.
  • the agent can periodically acquire the improvement degree of neighboring agents, and determines whether or not to change the variable based on the more recent improvement status, and as a result, the entire set of agents is determined. Can reach the solution faster.
  • the improvement ease generation unit generates improvement ease data at every second fixed time interval, and the constraint resolution unit determines the neighborhood change according to the variable change prohibition period data.
  • the variable data is changed so as to eliminate the constraint violation with the variable data stored in the agent, and the variable change prohibition period data stored in the variable change prohibition period storage unit is updated.
  • the agent can periodically check his / her improvement level, change the variable based on his / her latest improvement status, and as a result, the entire set of agents reaches the solution earlier. be able to.
  • the agent of the present invention is configured such that the first constant time interval is set smaller than the second constant time interval.
  • the frequency at which the agent checks its improvement level can be lower than the frequency at which the agent sends and receives the improvement level of the neighboring agent, and the improvement level can be checked based on the latest situation of the neighboring agent. As a result, the entire set of agents can reach the solution faster.
  • the agent of the present invention provides a variable change indicating a period during which change of variable data is prohibited.
  • the prohibited period is set to be k times the second fixed time interval (k is an integer).
  • the constraint solving unit determines whether or not to change the variable data, improvement of the neighboring agent stored in the improvement degree data of the own agent and the neighboring state storage unit. Comparing with ease data, there are at least the greatest number of possible improvements, cases where there is no agent that can change the variable data by violating the constraint other than its own agent, and when the number of constraint violations is the largest. It is configured so that it is determined that the variable data will be changed when one of the cases where the number of constraints is the smallest.
  • the agent of the present invention is configured such that, when changing the variable data, the constraint solving unit selects a variable value satisfying the constraint from the constraint data and updates the variable data in the variable storage unit. .
  • the agent can select a value from which the constraint is removed from the combination list, and a value that can properly eliminate the constraint is selected reliably. As a result, the entire set of agents can be solved more quickly. Can be reached.
  • the constraint resolution unit has the total ml of constraint violations in the latest third constant time interval of the improvement trend data and the number of constraint violations in the previous third constant time interval.
  • the current set value of the variable change prohibition period is shortened, and when ml ⁇ mO, it is determined that there is no improvement trend. It is configured to update the variable change prohibition period data by increasing the current setting value of the change prohibition period. [0038] Therefore, the agent can adjust the variable change prohibition period of the variable data according to the actual improvement trend of the number of constraint violations, and prohibit the change of the variable only for the period adapted to the problem. As a whole set of agents can reach the solution faster
  • the agent of the present invention by prohibiting the continuous change of a variable for a certain period under a certain condition, only a part of the agents does not try to resolve the constraint violation, and many By solving the constraint violation with the agent, the set of agents reaches the solution faster as a result of falling into the local optimal solution or infinite loop.
  • the agent stores a variable storage unit that stores variable data indicating a current value of the solution to be obtained, and variable data and neighboring agents store the variable data.
  • a constraint storage unit that stores constraint data indicating a combination of values with variable data, a variable change prohibition period storage unit that stores a period during which variable data is prohibited to be changed, a variable change prohibition period storage unit that stores data, and variable data of the own agent
  • An easy-to-improvement generator that generates easy-to-improvement data indicating the degree of ease for satisfying the constraint data, and a communication unit that transmits and receives variable data and the easy-to-improvement data generated by the easy-to-improvement generator
  • a proximity situation storage unit that stores improvement degree data and variable data obtained from neighboring agents, and an improvement degree generation unit.
  • the neighborhood stored in the neighborhood situation storage unit according to the variable change prohibition period data Constraint resolution by changing the variable data to a value that satisfies the combination of constraint data so that the constraint violation with the agent's variable data is resolved, and setting the variable change prohibition period data to a predetermined period A part.
  • the distributed constraint satisfaction method is a method in which each agent has variable data indicating the current value of a solution to be obtained, constraint data indicating a combination of variable data and variable data of neighboring agents, and variable data.
  • each agent has variable data indicating the current value of a solution to be obtained, constraint data indicating a combination of variable data and variable data of neighboring agents, and variable data.
  • multiple agents cooperate to obtain a solution of variable data in which all constraint relationships between variable data are established, each of which has variable change prohibition period data indicating a period during which the change of the value of the variable is prohibited.
  • Each agent can easily improve its own variable data to show the degree of ease for satisfying the constraint data
  • a generation step for generating degree data a step for asynchronously transmitting / receiving variable data and the improvement degree data generated in the generation step to each neighboring agent, and the variable data and improvement degree data as own improvement degree data
  • the decision step for determining whether or not to change its own variable data, and its own variable data when it is determined to change its own variable data at the decision step Change the data to a value that satisfies the combination of constraint data and notify neighboring agents.
  • Change step and variable change prohibition period when variable data is changed in the change step. Change prohibition to set data to a predetermined period. Steps.
  • FIG. 1 is a configuration diagram of an agent according to a first embodiment of the present invention.
  • FIG. 2A is a diagram showing a structure of variable data stored in the variable storage unit of the agent according to the first exemplary embodiment of the present invention.
  • FIG. 2B is a diagram showing a structure of constraint data stored in the constraint storage unit of the agent according to the first exemplary embodiment of the present invention.
  • FIG. 2C is a diagram showing a structure of ease of improvement data stored in the neighborhood state storage unit of the agent according to the first exemplary embodiment of the present invention.
  • FIG. 2D is a diagram showing a structure of variable change period data stored in the variable change prohibition period storage unit of the agent according to the first exemplary embodiment of the present invention.
  • FIG. 3 is a flowchart showing the operation of the agent according to the first exemplary embodiment of the present invention.
  • FIG. 4 is a diagram showing a setting example of a variable change prohibition period of the agent according to the first embodiment of the present invention.
  • FIG. 5 is a flowchart showing determination processing for changing an agent variable according to the first exemplary embodiment of the present invention.
  • FIG. 6 is a block diagram of the task assignment device according to the first exemplary embodiment of the present invention.
  • FIG. 7 is a diagram showing a task problem restriction network in which the task assignment device according to the first exemplary embodiment of the present invention creates a plan.
  • FIG. 8A is a diagram showing a constraint network in the initial state of the task assignment device according to the first embodiment of the present invention. It is a figure which shows a network.
  • FIG. 8B is a diagram showing the constraint network in the planning state of the task assignment device according to the first exemplary embodiment of the present invention.
  • FIG. 8C is a diagram showing a constrained network in the final state of the task assignment device according to the first exemplary embodiment of the present invention.
  • FIG. 9 is a diagram showing a configuration of an agent according to the second embodiment of the present invention.
  • FIG. 10 is a flowchart showing the operation of the agent according to the second exemplary embodiment of the present invention.
  • FIG. 11A is a diagram showing a structure of agent improvement tendency data according to the second embodiment of the present invention.
  • FIG. 11B is a diagram for explaining the storage operation of agent improvement tendency data according to the second embodiment of the present invention.
  • FIG. 11C is a diagram for explaining the operation of determining the improvement tendency of the agent according to the second embodiment of the present invention.
  • FIG. 12 is a flowchart showing an operation of adjusting the variable change prohibition period of the agent according to the second embodiment of the present invention.
  • FIG. 13 is a configuration diagram of a schedule adjustment apparatus equipped with an agent according to the second embodiment of the present invention.
  • FIG. 14 is a diagram for explaining a scheduling problem in which the schedule adjusting apparatus according to the second embodiment of the present invention creates a plan.
  • FIG. 15 is a diagram showing a schedule problem restriction network in which the schedule adjustment apparatus according to the second embodiment of the present invention creates a plan.
  • FIG. 16 is a diagram for explaining an initial operation of the schedule adjusting apparatus according to the second embodiment of the present invention.
  • FIG. 17 is a diagram for explaining the operation after TP adjustment of the schedule adjustment device according to the second exemplary embodiment of the present invention.
  • FIG. 18 is a configuration diagram of an agent according to the third embodiment of the present invention.
  • FIG. 19 is a collaborative work robot equipped with the agent according to the third embodiment of the present invention.
  • FIG. 19 is a collaborative work robot equipped with the agent according to the third embodiment of the present invention.
  • FIG. 20 is a diagram for explaining a movement problem in which the movement planning apparatus according to the third embodiment of the present invention creates a plan.
  • FIG. 21 is a diagram showing a movement problem restriction network in which the movement planning apparatus according to the third embodiment of the present invention creates a plan.
  • FIG. 22 is an explanatory diagram of the mobile operator of the cooperative work robot according to the third embodiment of the present invention.
  • FIG. 23 is a diagram for explaining an initial state of the movement planning apparatus according to the third embodiment of the present invention.
  • FIG. 24 is a diagram for explaining an intermediate state of the movement planning apparatus according to the third embodiment of the present invention.
  • FIG. 25 is a diagram for explaining the final operation of the movement planning apparatus according to the third embodiment of the present invention.
  • FIG. 26 is a diagram showing an example of a problem constraint network used in the experiment.
  • FIG. 27 is a diagram showing a comparison of the average number of cycles until reaching the solution of the experimental result.
  • FIG. 28 is a diagram showing comparison of solution arrival rates of experimental results.
  • FIG. 29 is a block diagram of a computer constituting a conventional constraint satisfaction device.
  • FIG. 30 is a diagram for explaining a constraint network expressing a constraint satisfaction problem.
  • Figure 31A shows a constraint network showing an example of the initial state of the constraint satisfaction problem.
  • Figure 31B is a diagram showing a constraint network showing an example of a state in which the solution of the constraint satisfaction problem is fixed.
  • Fig. 32 is a diagram for explaining a constraint network diagram expressing the distributed constraint satisfaction problem
  • FIG. 33 is a diagram for explaining an example of a dispersion constraint satisfaction problem.
  • the agent according to the first embodiment prohibits the change of the variable continuously for a certain period under a certain condition, so that it is possible to eliminate the constraint violation of many agents by simply eliminating the constraint violation of some agents.
  • the solution is to eliminate the reaction, and as a result of falling into the local optimal solution, the entire set of agents reaches the solution faster.
  • FIG. 1 is a configuration diagram of an agent according to the first embodiment of the present invention.
  • the agent 100 includes a variable storage unit 101, a constraint storage unit 102, a variable change prohibition period storage unit 104, an improvement ease generation unit 107, a communication unit 106, a neighborhood situation storage unit 103, and a constraint resolution unit 105. ing.
  • the variable storage unit 101 stores variable data indicating the current value of the solution to be obtained.
  • the constraint storage unit 102 stores constraint data indicating a combination of values of variable data and variable data stored in neighboring agents.
  • the variable change prohibition period storage unit 104 stores variable change prohibition period data indicating a period during which variable data change is prohibited.
  • the improvement degree generation unit 107 generates improvement degree data indicating the degree of ease with which the variable data of the own agent satisfies the constraint data.
  • the communication unit 106 transmits / receives the variable data and the improvement degree data generated by the improvement degree generation unit 107 to / from neighboring agents.
  • the neighborhood situation storage unit 103 stores neighborhood situation data composed of improvement ease data and variable data acquired from neighboring agents.
  • the constraint resolving unit 105 compares the improvement ease data generated by the improvement degree generation unit 107 with the improvement ease data of the neighboring agent stored in the neighborhood state storage unit 103, and sets it as variable change prohibition period data. In response, the variable data is changed to a value satisfying the combination of the constraint data so as to eliminate the constraint violation with the neighboring agent variable data stored in the neighborhood status storage unit 103. At the same time, the constraint resolution unit 105 sets the variable change prohibition period data to be a predetermined period.
  • FIG. 2A is a diagram showing a structure of variable data stored in the variable storage unit 101 of the agent according to the first exemplary embodiment of the present invention.
  • the variable data 121 stored in the variable storage unit 101 has a table structure in which variable names and their values are records.
  • Figure 2A shows that home agent A has one variable X and its value is 1.
  • FIG. 2B is a diagram showing a structure of constraint data stored in the constraint storage unit 102 of the agent according to the first exemplary embodiment of the present invention.
  • the constraint data 122 stored in the constraint storage unit 102 has a table structure in which a record indicating a combination of a variable name of its own variable name, a neighboring agent variable name, and a possible value of those values is a record.
  • self-agent A has a constraint related to variable X as a constraint related to variable X. Indicates that there is a constraint that the value combination (x, y) must be (1, 1) or (2, 2) or (3, 3). It is also shown that there is a constraint that the value combination force 1) or (2, 2) or (3, 3) with the variable y of agent C.
  • An agent that has a variable with respect to this variable X is called a neighbor agent.
  • FIG. 2C is a diagram showing a structure of variable change period data stored in the variable change prohibition period storage unit 104 of the agent according to the first exemplary embodiment of the present invention.
  • the variable change prohibition period data 123 stored in the variable change prohibition period storage unit 104 includes a variable name, time information indicating the start and end times of the period during which the change of the variable value is prohibited. Is a table structure in which is a record. In FIG. 2C, it is shown that the value of variable X of own agent A is prohibited until 00:00:00.
  • FIG. 2D is a diagram showing a structure of ease of improvement data stored in the neighborhood state storage unit 103 of the agent according to the first exemplary embodiment of the present invention.
  • the neighbor situation data stored in the neighbor situation storage unit 103 has a table structure in which the variable names and values of neighboring agents that have a constraint relationship with the variable data and the improvement ease data 125 are records.
  • the ease-of-improvement data 125 includes the constraint number 1 indicating the number of constraint data, the constraint violation number m indicating the number of variable data that violates the constraint data, and the restriction data when the variable data value is changed. It consists of a number n that can be improved to indicate the number of constraint data that can resolve the violation state.
  • variable X of own agent A and neighboring agent B that has constraints
  • the value of variable y is 2, and the number of constraints 1 in the improvement ease data 125 is 1, the number of constraint violations m is 1, and can be improved It shows that the number n is 1.
  • the value z of the variable z is S3, and the number of constraints 1 in the improvement ease data 125 is 1, the number of constraint violations m is 1, and the number of possible improvements n force Si.
  • the self-agent improvement ease data 125 is also configured to store the self-agent A improvement ease data 125 in a separate storage means. I don't mind!
  • FIG. 3 is a flowchart showing the operation of the agent according to the first exemplary embodiment of the present invention.
  • the time interval T1 timer event Evl
  • the time interval T2 timer event Ev2
  • This time interval T1 is an example of a first constant time interval.
  • the time interval T2 is an example of a second constant time interval.
  • the constraint resolution unit 105 generates a timer event Evl activated at a time interval T1, a timer event Ev2 activated at a time interval T2, and a message reception event Ev3 by receiving a message from a neighboring agent. Eventually it waits until one event occurs (step S401). Next, the constraint solving unit 105 instructs the start of the next process according to the type of event that has occurred (step S402).
  • the improvement ease generation unit 107 determines whether or not the change of the value of the variable is within the period during which the change of the variable value is prohibited from the variable change prohibition period data stored in the variable change prohibition period storage unit 104. If it is out of the period, the improvement ease generation unit 107 uses the variable data stored in the variable storage unit 101 and the constraint data stored in the constraint storage unit 102 to have 1 constraint, m constraint violations, The improvement ease data composed of the improvement possible number n is generated, and if it is within the period, it is stored that the value of the variable cannot be changed (step S403).
  • the improvement ease generation unit 107 generates the attribute value of the improvement ease data for the variable data stored in the variable data table 121 as follows.
  • the improvement level generation unit 107 calculates the total number of records including the variable name of the variable data from the constraint data 122 stored in the constraint storage unit 102 and sets the number of constraints to 1. And the variable data of neighboring agents are included in the value combination, and the total number of ⁇ records is calculated as the constraint violation number m.
  • the improvement ease generation unit 107 further includes that the variable data value is not stored in the variable change prohibition period data 123 in the record, and the value of the constraint data is changed by changing the variable data value.
  • the total number of records that can be combined is calculated, and the number that can be improved is n.
  • the time interval T1 is preferably shorter than the time interval T2 described later. Neighboring agents can always be notified of the latest situation where the time interval T1 is sufficiently short.
  • the communication unit 106 transmits the improvement ease data to all of the neighboring agents by message communication, and returns to step S401. However, the communication unit 106 uses the If the change of the variable is prohibited and it is determined that the value of the variable cannot be changed within the specified period, a message indicating that the change cannot be made is transmitted (step S404).
  • the communication unit 106 receives a message from a nearby agent (step S405).
  • the communication unit 106 stores the variable data and ease of improvement data of neighboring agents included in the received message in the neighboring state storage unit 103, and returns to step S401 (step S406).
  • the improvement ease generation unit 107 determines whether the change of the variable value is prohibited from the variable change prohibition period data 123 stored in the variable change prohibition period storage unit 104, similarly to the processing in step S403. Further, the ease-of-improvement generation unit 107 uses the variable data 121 stored in the variable storage unit 101 and the constraint data 122 stored in the constraint storage unit 102 to obtain a constraint number 1, a constraint violation number m, and an improvement possible number n. Generated improvement ease data (step S407). However, the neighbor agent name in the self-improvement degree data 125 of the self agent can be distinguished from the data of other agents as a value representing the self agent.
  • the constraint solving unit 105 records the improvement degree data 125 generated by the improvement degree generation unit 107 in step 407 in the neighborhood state storage unit 103, and the improvement degree of each neighboring agent. Compare with data 125 to determine if the value of the variable should be changed. If it is determined to be changed, the process proceeds to step S409. If it is determined not to change, this event processing is terminated, and the process returns to step S401 (step S408). Details of this determination method will be described later.
  • the constraint resolution unit 105 selects one of the variables that can be taken by the agent from the possible combinations of the constraint data 122 stored in the constraint storage unit 102, and obtains the value of the variable.
  • the current value of the variable data 121 stored in the variable storage unit 101 is updated.
  • the ease-of-improvement generation unit 107 generates the ease-of-improvement data with the updated variable data values in the same manner as the processing in step S403, and the communication unit 106 generates the variable data and the ease of improvement generated.
  • the degree data is notified to each neighboring agent by a message (step S409).
  • the constraint resolution unit 105 stores the variable change prohibition period in the variable change prohibition period storage unit 104 so that the value of the variable whose value has been changed in step S408 cannot be changed for a certain period.
  • the current time is set as the start time, the time after a lapse of a certain period is stored as the end time, and the process returns to step S401 (step S410).
  • this operation flow operates asynchronously independent of neighboring agents. For this reason, messages are sent at any time between neighboring agents that operate asynchronously between agents.
  • the message reception event Ev3 is stored in the event queue by the event processing mechanism, and even if a step other than step S401 is being processed, the process proceeds to step S401. This is so that events can be detected. Even if a timer event occurs during message processing in step S405, it can be detected and processed in the same way.
  • step S410 a method for setting the variable change prohibition period in step S410 will be described.
  • the method of prohibiting any change in the value of a variable (prohibition method 1) is used.However, there is a method of prohibiting a variable from being set to a certain value (prohibition method 2) or a certain value strength. It can also be realized as a method that prohibits changing to a value (prohibition method 3), or a method that prohibits the above combinations or other specific changes (prohibition method 4).
  • the range of variable X that is, the set of values taken by variable X is set to ⁇ 1, 2, 3 ⁇ , and the value of variable X is changed from "1" to "2"
  • the operation during the prohibition period according to the prohibition method described above is as follows.
  • variable change prohibition period is set for each variable.
  • the prohibition method 2 a force that prohibits the return of the value of the variable X to “1” for a certain period or a change of the value of the variable X to “2” is prohibited for a certain period. In this case, changing the value of variable X to “3” is not prohibited even during the prohibited period.
  • the variable change prohibition period is set for each variable value.
  • prohibition method 3 change of the value of variable X from “1” to “2” is prohibited. In this case, “1” or Even during the period when the change from “1” to “2” is prohibited, the change from “1” to “3” and the change from “3” to “2” are not prohibited.
  • the variable change prohibition period is set by distinguishing the direction of variable change.
  • prohibition method 4 change of the value of variable X from “3” to “2”, “2” to “1”, and “1” to “3” is prohibited.
  • the value is limited to changes in the ascending order, such as “1” to “2”, “2” to “3”, and “3” to “1”.
  • FIG. 4 is a diagram illustrating a setting example of the variable change prohibition period of the agent according to the first embodiment of the present invention.
  • a variable change prohibition period 151 is set (at time 153) to prohibit the change from “1” to “2”.
  • variable change prohibition period 152 is set (at time 154).
  • Each variable change prohibition period is set independently, and even if it is a variable change prohibition period from ⁇ 1 '' to ⁇ 2 '', it is a variable change prohibition period from ⁇ 2 '' to ⁇ 1 ''. Otherwise, changing from “2” to “1” is not prohibited. After the variable change prohibition period ends, the prohibition setting is canceled (at time 155 and time 156).
  • FIG. 5 is a flowchart showing the determination processing of the constraint solving unit 105 that changes the agent variable according to the first embodiment of the present invention.
  • the determination process shows the detailed operation of step S408 in the flowchart showing the operation of the agent in FIG.
  • the constraint solving unit 105 always determines that the value of the variable is not changed (S509), determines that the value of the variable is changed (S510), and ends.
  • step S501 the constraint resolution unit 105 sets the variable data value of the constraint data from the variable data 121 stored in the variable storage unit 101 and the constraint data 122 stored in the constraint storage unit 102.
  • the record is searched to determine whether there is any variable data that violates the constraint. If there is no variable data that violates the constraint, the constraint resolution unit 105 determines that the variable is not changed (S509), and ends.
  • step S502 the variable force variable violates the constraint examined in step S501. If the variable change prohibition period data 123 stored in the change prohibition period storage unit 104 is included in the prohibition period and the change of the variable is prohibited, the constraint resolution unit 105 must change the value of the variable. Judge (S509) and end.
  • step S503 the constraint resolving unit 105 calculates the ease of improvement data composed of the number of constraints 1, the number of constraint violations m calculated by the improvement ease generator 107, and the number of possible improvements n, and the neighborhood status memory.
  • the improvement ease data 125 of the neighboring agent stored in the part 103 is compared. If the possible improvement number n is greater than the possible improvement number n of any neighboring agent, the constraint solving unit 105 determines to change the value of the variable (S510), and ends. On the contrary, if the improvement possible number n is smaller than the improvement possible number n of any neighboring agent, the constraint solving unit 105 determines that the variable is not changed (S509), and ends.
  • the case where the improvement possible number n is 0 is also included with all neighboring agents.
  • the constraint solving unit 105 includes the ease of improvement data composed of the number of constraints 1, the number of constraint violations m, and the number of possible improvements n calculated by the ease of improvement generation unit 107 and the neighborhood status storage unit 103. From the data on the ease of improvement of the neighboring agents stored in (the number of constraints 1, the number of constraint violations m, the number of possible improvements n ) 125 Check if there is an agent that can change the variable from the number n that can be improved. If the target number of agents is 0, the constraint resolution unit 105 determines to change the variable (S510), and the process ends. If the number of target agents is 1 or more, the process proceeds to step S505.
  • step S505 the constraint resolution unit 105 compares the number of constraint violations m with the number of constraint violations m of the agent targeted in step S504. Determines that the value of the variable is to be changed (S510) and ends. If the number of constraint violations of any neighboring agent is smaller than m, it is determined that the variable should not be changed (S509), and the process ends. If the constraint violation number m is the same as the maximum constraint violation number m of the neighboring agent, the process proceeds to step S506.
  • step S506 the constraint resolution unit 105 compares the constraint number 1 with the constraint number 1 of the agent targeted in step S504, and the constraint number of any neighboring agent is small. If so, it is determined to change the variable (S510), and the process ends. If the number of constraints of any neighboring agent is too large, it is determined that the variable is not changed (S509), and the process ends. If the restriction number 1 is the same as the minimum one of the neighboring agent restriction numbers 1, the process proceeds to step S507.
  • step S507 the constraint resolving unit 105 includes an agent that includes the agent and the agent that is the target in step S504. Determine.
  • step S508 if the constraint solving unit 105 determines that the self agent is to change the variable, the constraint solving unit 105 determines to change the variable, and ends. If it is not determined that the variable is to be changed, it is determined that the variable is not changed, and the process ends.
  • the probabilistic determination of agents in step S508 may be a method of calculating according to data that agents can refer to in common, such as time information and ranking among agents.
  • both variables are determined with an average probability distribution with no bias in the determination result, and at least one of the variables is continuously excellent for a long time on average. It shall not be changed first. For example, the case where only the wrong judgment method is used in which the node with the younger node name is always changed with priority is excluded.
  • step S501 to step S508 an example of the power used as the processing procedure from step S501 to step S508 is shown.
  • the types of steps to be judged and the order of judgment are not limited to this.
  • FIG. 6 is a configuration diagram of the task assignment device according to the first exemplary embodiment of the present invention.
  • the agent 100a, agent 100b,..., Agent 100c in the task assignment device 300 are connected via a wired or wireless network and can communicate with each other.
  • agent 100, agent 100b,..., And agent 100c have the same configuration as agent 100 shown in FIG. If agent 100a is its own agent, agent 100b and the like are neighboring agents.
  • variable storage unit 101 constraints
  • the storage unit 102 and the variable change prohibition period storage unit 104 will be described assuming that initial values necessary for the operation are set in advance, but an initial setting device for setting the initial value of each agent is provided separately through the network. It can also be implemented as a configuration set for each agent.
  • FIG. 7 is a constrained network diagram in which the task assignment device according to the first exemplary embodiment of the present invention creates a plan.
  • each node shows a variable xl of agent XI, a variable X 2 of X2,..., A variable x7 of X7.
  • Each node takes one of the values “black” indicating “black task” and “white” indicating “white task”.
  • each arc represents a constraint between each variable.
  • nodes connected by constraints cannot have the same value.
  • node xl and node x4 must not be “white” or “black” at the same time.
  • the values of node x4 and node x5 are “black” at the same time, and a constraint violation has occurred.
  • FIG. 7 shows the constraint relationship between variables for each agent in the task assignment device, and does not show an actual network connection configuration for connecting the agents. However, as shown in Fig. 6, it is not always necessary to configure communication paths between all agents. It is only necessary to configure communication paths between agents that have at least a variable in a constraint relationship.
  • FIG. 8A is a constrained network diagram of an initial state of the task assignment device according to the first exemplary embodiment of the present invention.
  • FIG. 8B is a constraint network diagram in a planning state of the task assignment device according to the first exemplary embodiment of the present invention.
  • FIG. 8C shows the final state of the task assignment device according to the first exemplary embodiment of the present invention.
  • the ease-of-improvement data for each node is shown as “(number of improvement possible nZ constraint violation number mZ constraint number 1)” after the symbol xj representing each node.
  • the decision whether to change the variable or not is changed when the number n that can be improved is larger. If this is the same, the one with the larger number of constraint violations m changes, and if this is the same, the agent with the smaller number of constraints 1 changes the value of the variable.
  • change of variable values is prohibited.
  • FIG. 8A shows an initial state.
  • a constraint violation occurs between node x4 and node x5.
  • Nodes xl, x2, x3, x6, and x7 do not violate the constraint and the number of constraints is 1, so all the ease of improvement data is (OZOZ1).
  • Node ⁇ 4 has one constraint violation with node ⁇ 5, and if node ⁇ 4 changes to white, the constraint violation with node ⁇ 5 is resolved, but the constraint between nodes xl, ⁇ 2, and ⁇ 3 Since a violation occurs, the number ⁇ that can be improved (in this case, a number greater than or equal to 0) is zero. Therefore, the improvement ease data of the node ⁇ 4 is (0/1/4).
  • the improvement ease data of node ⁇ 5 is (OZ1Z3). This information is exchanged between neighboring agents through step S403, step S404, step S405, and step S406 in FIG.
  • Constraint violation node x4 and variable x5 have almost the same conditions Force Constraint number 1 is smaller in node x5, so node x4 is determined not to change value, and node x5 changes value It is determined to be. Therefore, the node x5 changes the value to “white” and becomes the state shown in FIG. 8B.
  • node x5 can improve two constraint violations between node x6 and node x7 by changing the value from "white” to "black”. Since this is a violation, the number of possible improvements 1 is 1. Therefore, the ease of improvement data for node x5 is (1Z2Z3). The improvement degree data of nodes x6 and x7 are both (1Z1Z1). The number of possible improvements n is the same, but the number of constraints 1 is larger for node x5. If the value of node x5 is changed from “white” to “black” here, it returns to the state shown in Fig. 8A and falls into an infinite loop of the local optimal solution.
  • node x5 is in the variable change prohibition period because the value was changed earlier, and the value cannot be changed. Therefore, node x6 and node x7 change their values in step S504. It is determined. Since node x6 and node x7 are not directly connected, both can change the value at the same time.
  • the agent in the present embodiment exchanges information with neighboring agents at the time interval T1 and improves the state at the time interval T2. However, these operations are executed at the same timing. May be. In other words, the information exchange with the neighboring agent and the judgment of improvement may be operated continuously.
  • the agent is prohibited from changing the variable continuously, and the same variable cannot be changed to the same value for a certain period.
  • the possibility of falling into a local optimal solution decreases, and as a result, the solution can reach the solution faster as a whole.
  • the agent working on the present embodiment eliminates restriction violations of some agents by prohibiting continuous change of variables in a period corresponding to the resolution situation of variable constraint violations.
  • the goal is for the entire set of agents to reach the solution even faster as a result of the local optimal solution and the infinite loop.
  • FIG. 9 is a configuration diagram of an agent according to the second embodiment of the present invention.
  • Agent 200 stores the improvement trend data indicating the past transition of the degree to which the force variable data that has almost the same configuration as Agent 100 shown in Fig. 1 meets the constraint data. 1 is different from FIG. 1 in that a trend storage unit 208 is further provided. Further, when the constraint resolution unit 205 changes the value of the variable data stored in the variable storage unit 101, the latest improvement trend. 1 is different from FIG. 1 in that the direction data is generated and stored in the improvement trend storage unit 208, and the length of the variable change prohibition period of the variable data is adjusted according to the improvement trend data.
  • the improvement trend data stored in the improvement trend storage unit 208 is a table structure of transition data of the variable name and the number of constraint violations m of the variable.
  • the improvement trend data is history data of the number of constraint violations including the past several times. Details of the data structure of past changes will be described later.
  • FIG. 10 is a flowchart showing the operation of the agent according to the second exemplary embodiment of the present invention.
  • the operation of the agent 200 is different from that in FIG. 3 in that force steps S601 and S602 that are substantially the same as the steps of the agent 100 shown in FIG. 3 are added.
  • the time interval T4 which is a period for determining the improvement tendency of variables, and the current set value TP of the variable change prohibition period are used as parameters.
  • This time interval T4 is an example of a third constant time interval.
  • the time interval T4 is a period corresponding to several times the time interval T2, but in the present embodiment, the time interval T4 is described as being set to 5 times the time interval T2.
  • the current set value TP of the variable change prohibition period is k times the time interval T2 (k is an integer) because of the relationship between the synchronization timing of the variable update operation and the determination operation. The set value in will be described later.
  • step S601 the constraint solving unit 205 records the number of constraint violations m calculated by the ease-of-improvement generation unit 107 in the improvement trend storage unit 208 as current improvement trend data.
  • the number of constraint violations, m is set so that a record of about twice the time interval T4 remains.
  • FIG. 11A is a diagram showing a structure of agent improvement tendency data according to the second embodiment of the present invention.
  • improvement trend data 210 has a structure that records the number of constraint violations m for past variables, and stores the current number of constraint violations m in the rightmost column.
  • the constraint violation number m recorded at the previous time is stored, and in the left column, the constraint violation number m recorded two times before is stored. In this way, it is twice as long as T4 time, that is, 10 times as long as T2. The period is recorded.
  • FIG. 11A is a diagram showing a structure of agent improvement tendency data according to the second embodiment of the present invention.
  • improvement trend data 210 has a structure that records the number of constraint violations m for past variables, and stores the current number of constraint violations m in the rightmost column.
  • the constraint violation number m recorded at the previous time is stored, and in the left column, the constraint violation number m recorded two times before is stored. In this way, it is twice as long as T
  • FIG. 11B is a diagram explaining an agent improvement tendency data storage operation according to the second embodiment of the present invention.
  • the number of constraint violations is recorded as new data in the improvement trend data 210
  • the previous records are shifted one by one, and the current number of constraint violations is recorded in the rightmost column. It is recorded to keep the time order according to the past number of constraint violations.
  • step S602 the constraint solving unit 205 determines an improvement trend from the history of the number of constraint violations m recorded in the improvement trend storage unit 208.
  • the constraint resolution unit 205 compares the total number of constraint violations in the latest time interval T4 with the total number of constraint violations in the previous time interval T4, and determines the improvement trend. This determination changes the value of the current setting value TP during the variable change prohibition period.
  • FIG. 11C is a diagram illustrating an operation of determining an improvement tendency of an agent according to the second embodiment of the present invention.
  • the total ml of the constraint violations in the recent time interval T4 and the total mO of the constraint violations in the previous time interval T4 are compared. If ml> mO, it is judged as “not improved”, and if ml ⁇ mO, it is judged as “improved”.
  • the current set value TP of the variable change prohibition period is changed.
  • the total number of previous constraint violations is 6, the total number of recent constraint violations is 5, and the improvement trend is judged as “improved”.
  • FIG. 12 is a flowchart showing an operation of adjusting the variable change prohibition period of the agent according to the second embodiment of the present invention.
  • the current set value TP of the variable change prohibition period takes a value within a predetermined range from the minimum value TP-min to the maximum value TP-max.
  • step S701 the constraint resolution unit 205 determines an improvement tendency from the number of constraint violations m stored in the improvement trend storage unit 208. If it is determined that the improvement is improved, the constraint resolution unit 205 proceeds to step S704. move on. If it is determined that “Improved !, NA! /,”, The process proceeds to step S702. In step S702, if TP is greater than TP-max, the process proceeds to step S703. Otherwise, exit without changing TP.
  • step S703 TP is incremented by a predetermined value, and the process ends.
  • step S704 If TP> TP—min in step S704, the process proceeds to step S705. Otherwise, exit without changing TP.
  • step S705 the predetermined value is reduced by the TP force and the process is terminated.
  • FIG. 13 is a configuration diagram of a schedule adjustment apparatus equipped with an agent that can make full use of Embodiment 2 of the present invention.
  • the schedule adjustment apparatus 301 is composed of a plurality of agents 200a, 200b, 200c,. ⁇ IJ user ⁇ ⁇ inputs / outputs the schedule to Agent 200a, User B to Agent 200b, User C to Agent 200c, and User n to Agent 200 ⁇ via the input / output unit.
  • Each agent adjusts the schedule with other users based on the entered schedule.
  • the user ⁇ ⁇ inputs his / her desired schedule to the schedule adjustment device on which the agent 200a is installed, and instructs the start of conference adjustment and schedule adjustment with other participants.
  • Agent 20 Oa force S The plan created by coordinating with other agents 200b, 200c, and 200 ⁇ is received as a schedule result from the schedule adjustment device.
  • FIG. 14 is a diagram for explaining a schedule problem in which the schedule adjustment device according to the second embodiment of the present invention creates a plan.
  • the settable days for each user are 1 and 2 days for ⁇ IJ user A, 2 days, 3 and 4 days for ⁇ IJ user B, and ⁇ IJ user C for 2 days and 3 days, and the initial setting of the desired date to hold each user's meeting is 2 days. Show.
  • each user cannot set up two meetings at the same time.
  • each user does not disclose the conference setting date to other users from the beginning from the viewpoint of privacy.
  • User B does not disclose to User C that he / she will set up a first meeting with User A.
  • User B does not disclose to User A that he will have a second meeting with User C.
  • FIG. 15 is a restriction network diagram of a schedule problem in which the schedule adjustment apparatus according to the second embodiment of the present invention creates a plan.
  • each node shows variables of the agent 200a, the agent 200b, and the agent 200c.
  • Agent 2 OOa has node x8 indicating the conference setting date of user A, and node x8 takes “1” or “2”.
  • the agent 200b includes a node x9 indicating a date when the user B sets up a conference with the user A, and a node xlO indicating a date when the user B sets up a conference with the user C.
  • Node x9 and node xlO each take one of the values “2”, “3”, and “4”.
  • the agent 200c has a node xl l indicating the date when the user IJ C sets up a meeting with the user B.
  • the node xl l takes “2” or “3”.
  • step S408 for determining whether or not to change the variable value is performed.
  • the node with the younger node name for example, node x9
  • node xlO it shall be determined to change the value with priority.
  • it is possible that such a younger node will be permanently changed in preference and may be judged in this way for a limited period of time.
  • the node value change prohibition method is to change the value back to the value before the change after changing the value. It is prohibited during the prohibited period. However, if there is a possible value other than the value before the change, the change to that value is not prohibited.
  • FIG. 16 is a diagram for explaining an initial operation of the schedule adjusting apparatus according to the second embodiment of the present invention. In Fig. 16, each line shows the value of the variable at each time. In addition, the ease-of-improvement data is indicated after each variable value as “(number of improvement possible nZ constraint violation number mZ constraint number 1)”.
  • agent 200a, agent 200b, and agent 200c have the values of variable x8, variable x9, variable ⁇ 10, and variable xl l all set to "2"
  • a constraint violation has occurred between variable x9 and variable xlO.
  • each agent generates improvement ease data, transmits and receives it, and determines whether to change the value of the variable.
  • Agent 200b changes the value of x9, which has priority, to "3" because variable x9 and variable xlO have the same improvement ease data.
  • Agent 200a and Agent 200c are determined not to change the value of the variable.
  • variable x9 can be changed to the force value "3" and the value "4", which are prohibited from changing to the value "2".
  • variable x8 is prohibited from changing to the value "2". Since variable x8 needs to have a value of “l” or “2”, variable x8 is in a state where its value cannot be changed at all. In addition, the variable change prohibition setting for the variable x9 is cancelled, and the agent 200b determines to change the value of the variable x9.
  • the variable x9 has a constraint violation number m of 1, If the value is changed to “2”, the number of constraint violations m increases to 2, so change it to “4”.
  • variable change prohibition setting for variable x8 is cancelled.
  • agent 200a changes the value of variable x8 from “1” to “2”.
  • the agent 200b changes the value of the variable x9 from "4" to "3" as at time 2.
  • time 5 is almost the same as time 1, and after this time, the operation of changing the values of variable x8 and variable x9 is continued and the constraint violation state is not resolved. .
  • the variable x8 and the variable x9 are in a state of constraint violation power.
  • the constraint resolution unit 205 of agent 200a and agent 200b is judged as “not improved” from the improvement trend data, and agent 200a is currently in the variable change prohibition period for variable x8 and agent 200b for variable x9. Increase the set value TP.
  • Agent 200c does not change the current set value TP of the variable change prohibition period regardless of the variable.
  • FIG. 17 is a diagram for explaining an operation example after the TP adjustment of the schedule adjustment apparatus according to the second embodiment of the present invention.
  • each row indicates the value of the variable at each time.
  • the second operation example shows the operation example that follows the change of the TP of the variable x8 and variable x9 in the first operation example, but the initial values of each variable are easier to compare. Is the same as the initial value of the operation example shown in Fig. 16.
  • variable change prohibition period is set for any variable !, and how the state force starts to operate and how it operates is explained.
  • the variable x8 and the variable x9 are set to a period twice the time interval T2, which is the setting value in the previous operation example shown in FIG. 16, that is, 2 XT2 time. .
  • the agent 200a changes the value of the variable x 9 to “3”.
  • agent 200b changes the variable x9 to the value "2". Set prohibited. The constraint violation between variable x8 and variable x9 has not been resolved. Restriction Change the value of variable x8 with a small number of constraints.
  • the agent 200a changes the value of the variable x8 to "1” and prohibits the change to the value "2". Since the value of the variable x8 needs to be “1” or “2”, the agent 200a cannot change the value of the variable x8 at all. Since the constraint violation between the variable x8 and the variable x9 has not yet been resolved, the agent 200b changes the value of the variable x9 from “3” to “4” in the same manner as the operation at time 2 in FIG. . Variable x9 is changed to the value “4” because changing to the value “2” is prohibited.
  • variable x8 At time n + 3, the constraint violation between variable x8 and variable x9 is resolved. Since the change of the value of the variable x8 is still prohibited, the agent 200b determines to change the value of the variable x9. When variable x9 is changed to value “2”, the number of constraint violations increases to 2, but change to value “3” is prohibited, so change to value “2”.
  • the agent is prohibited from changing the variable continuously during the period according to the resolution state of the constraint violation, and may fall into a local optimal solution.
  • the agent according to the second embodiment is configured by computer hardware and software.
  • the agent according to the second embodiment has the configuration shown in FIG. 29, for example, in the same manner as the conventional agent.
  • the variable storage unit 101, the constraint storage unit 102, the neighborhood status storage unit 103, the variable change prohibition period storage unit 104, and the improvement trend storage unit 208 are realized by the memory 902, the secondary storage unit 905, and software that manages them.
  • the constraint solving unit 205 and the improvement ease generating unit 107 are configured by a software module stored in the CPU 901, the memory 902, and the secondary storage unit 905.
  • the communication unit 106 includes a network interface 906 and software for controlling the network interface 906.
  • a user who uses the schedule adjustment device can interactively set his / her schedule by using the display unit 903 such as a display and the input unit 904 such as a mouse, a keyboard, and a voice input device. Further, the schedule adjustment result can be confirmed by the display unit 903.
  • the display unit 903 such as a display
  • the input unit 904 such as a mouse, a keyboard, and a voice input device. Further, the schedule adjustment result can be confirmed by the display unit 903.
  • a movement planning device for a cooperative work robot (hereinafter referred to as a robot) in which a plurality of agents according to the third embodiment of the present invention are connected will be described.
  • Many of the agents that can be used in this embodiment do not need to continuously change the variables for a certain period of time under certain conditions.
  • the goal is to eliminate constraint violations, and the goal is for the entire set of agents to reach the solution faster as a result of falling into the local optimal solution.
  • Figure 18 is a configuration diagram of an agent according to the third embodiment of the present invention.
  • the agent 700 has almost the same configuration as that of the agent 100 shown in the first embodiment.
  • the agent 700 has a planned coordinate storage unit 701 that stores a planned coordinate series instead of the variable storage unit 101, and The difference is that a neighboring planned coordinate storage unit 703 that stores the planned coordinate series of neighboring agents in place of the storage unit 103 is provided.
  • the data structure of the planned coordinate series stored in the planned coordinate storage unit 701 is an arrangement structure of position coordinates.
  • the data structure of the planned coordinate series stored in the neighboring planned coordinate storage unit 703 has a table structure in which data for identifying neighboring agents and array structure data of position coordinates are used as records.
  • the basic operation of the agent 700 is the same as that of the agent 100 shown in the first embodiment.
  • FIG. 19 is a diagram showing a configuration example of a collaborative work robot equipped with an agent that can perform the third embodiment of the present invention.
  • the robot 800 is an external environment detection unit 801 including sensors for detecting its own position, the position of another robot, an obstacle, etc., a moving unit 802 for a motor or leg force for movement, unplanned or predicted A collision avoidance unit 803 for avoiding a collision with an outside obstacle, and 700 agents who make their own movement plan according to the constraints between various inputs from sensors and the movement plan with other robots.
  • the agent 700 determines other data according to the variable data and constraint data that are preliminarily set and the data acquired by the external detection unit 801 and the collision avoidance unit 803. It communicates with the agent of the robot, adjusts the movement plan, makes a movement plan, and instructs the movement unit 802 to move the movement plan.
  • FIG. 20 is a diagram for explaining a movement problem in which the movement planning apparatus according to the third embodiment of the present invention creates a plan.
  • two robots Ra811 and Rb812 work in the same room.
  • Robot Ra811 and Robot Rb812 have their own Sensors can detect and confirm your position in the room, the position of the opponent, and the position of obstacles.
  • the movement plan is planned with quantized tile coordinate values.
  • the space in which the cooperative robots Ra811 and Rb81 2 can move has a width of 5 in the X direction and a width of 2 in the Y direction. Robot Ra811 and robot Rb812 exist in this space.
  • the cooperative work robot Ra811 is located at the initial coordinates (1, 1), and the robot Rb812 is located at the initial coordinates (0, 0).
  • the robot Ra811 and the robot Rb81 2 move to the goal Ga814 and the goal Gb815 on the shortest path, respectively, and the robot Rb812 stays when it reaches the goal Gb815.
  • the mouth bot Ra811 reaches the final coordinate, that is, the goal Ga814 (coordinate (4, 1)), and the robot Rb812 reaches the goal Gb815 (coordinate (4, 0)) within 5 steps.
  • the planned coordinate series for the robot Ra811 is from the planned coordinates (xl l, y 11) to the planned coordinates (xl5, yl5), and for the robot Rb812, the planned coordinate (x21, y21) force is also the planned coordinates (x25 , y25).
  • the planned coordinates (xl l, yl l) and the planned coordinates (xl5, yl5) are the initial position of the mouth bot Ra811 and the position of the goal Ga814, respectively.
  • the planned coordinates (x21, y21) and the planned coordinates (x25, y25) Is the initial position of robot Rb812 and the position of goal Gb815. These values are already determined, and the movement planning problem is to fill in the coordinates between them
  • FIG. 21 is a restriction network diagram of a movement problem created by the movement planning apparatus according to the third embodiment of the present invention.
  • the X coordinate value of the planned coordinate is “0”, “1”, “2”, “3”, “4”, and the Y coordinate value is “0”, “1”.
  • the coordinate (3, 1) has an obstacle K813 and cannot have this planned coordinate value.
  • the movement operator "op" indicates restrictions on the movement command. There are a total of five movements: one movement operator that moves the coordinates one step up, down, left, or right in one step, and one movement operator that does not move at all.
  • FIG. 22 is an explanatory diagram of the mobile operator of the cooperative work robot according to the third embodiment of the present invention.
  • the “left” operator decrements the X coordinate value by 1 and does not change the Y coordinate value. That is, “X coordinate value change” is “1”, and “Y coordinate value change” is “not changed”.
  • the “right” operator increases the X coordinate value by 1, and does not change the ⁇ coordinate value. That is, “X coordinate value change” is “+1”, and “Y coordinate value change” is “Do not change!”.
  • the “up” operator increases the Y coordinate value by 1, and does not change the X coordinate value. That is, “Y coordinate value change” is “+1”, and “X coordinate value change” is “not changed”.
  • the “down” operator decrements the ⁇ coordinate value by 1 and does not change the X coordinate value. That is, “Y coordinate value change” is “ ⁇ 1”, and “X coordinate value change” is “not changed”. Also, the “stay” operator does not change the coordinate value. In other words, “X coordinate value change” and “Y coordinate value change” are “do not change!”.
  • Robot Ra811 and Robot Rb812 select one of these five operators at a time. At this time, as a restriction between these operators, the coordinate series is determined between the coordinates before and after the movement for each movement.
  • FIG. 23 is a diagram for explaining an initial state of the movement planning apparatus according to the third embodiment of the present invention.
  • the robot Ra811 and the robot Rb812 first have their own planned coordinate series (xl l, y 11) and planned coordinate series (xl 5, yl5) and planned coordinates stored in the planned coordinate storage unit 701, respectively.
  • the plan coordinate series (x25, y25) from the series (x21, y21) is shown as planned by the constraint resolution unit 105 based on the restrictions of the moving operator.
  • the robot Ra811 and the robot Rb812 send and receive the planned coordinate series via the communication unit 106, and from the planned coordinates (xl2, y12) to the planned coordinates (xl5, yl5) and the planned coordinates (x22, y22) ) Plan Detects a violation of the constraint because the mark (x25, y25) exists at the same coordinates
  • FIG. 24 is a diagram for explaining an intermediate state of the movement planning apparatus according to the third embodiment of the present invention.
  • the robot Ra811 with priority to eliminate the constraint condition changes the value of the planned coordinate (xl2, yl2) from coordinate (1, 0) to coordinate (2, 1) for the state force in Fig. 23.
  • Robot Ra811 cannot change the planned coordinate series after the planned coordinates (xl2, yl2) in order to reach the goal Ga814 within the target number of movements.
  • the robot Ra811 transmits to the robot Rb812 improvement ease data including information on the previous change and variable change prohibition period generated by the improvement degree generation unit 107.
  • the robot Rb812 that received the improvement ease data of the robot Ra811 changes the planned coordinates (x23, y23) and changes the subsequent planned coordinates.
  • FIG. 25 is a diagram for explaining the final state of the movement plan planning apparatus according to the third embodiment of the present invention.
  • the planned coordinates of robot Ra811 and robot Rb812 are shown in a state where all the constraints are satisfied.
  • the robot Ra811 can reach the goal Ga814, good!] Coordinates (4, 1).
  • Robot Rb812 can reach Gonore Gb815, ie, coordinates (4, 0). Thereby, the movement plan of the robot Ra811 and the robot Rb812 is completed.
  • the agent uses the coordinate series as a variable, and the sensor device acquires the initial value of the variable data and constraint data and the value at the time of change from the outside. And create a plan.
  • the possibility of falling into a local optimal solution and the possibility of some agents falling into an infinite loop are further reduced.
  • the entire set of agents installed on the robot can make a movement plan quickly.
  • the coordinate series is used as a variable.
  • the mobile operator may be used as a variable.
  • the problem of the task assignment device in 1 is solved using a simulator and evaluated by the number of message exchanges.
  • Figure 26 shows an example of the constraint network.
  • the problem is created by first dividing the agents into three groups, and connecting the agents in different groups randomly with constraints.
  • the constraint is an X ⁇ Y type constraint. When you create a problem like this, you can always create a problem that has a solution.
  • Figure 26 shows 10 types of problems with a total of 120 agents and a total of 324 constraints in the force experiment with 12 agents. This is Issue I.
  • Figures 27 and 28 show the results.
  • Figure 27 shows the average number of cycles to reach the solution.
  • Figure 28 shows the solution arrival rate.
  • the average number of cycles to reach the solution by the method of the present invention is much smaller than the average number of cycles to reach the solution by the existing method.
  • the solution arrival rate according to the method of the present invention is 100% in both the problem I and the problem II.
  • the achievement rate by the existing method reached 100% for both Problem I and Problem ⁇ .
  • the method of the present invention reliably reaches the solution in a shorter time than the existing method.
  • the existing method has 5277.30 cycles (solution attainment rate of 74%), while the method of the present invention has 407.82 cycles (solution attainment rate of 100%). Appears.
  • Embodiments 1 to 3 each problem can be solved by exchanging information several times between agents. But the actual problem is very complex. For example, in the third embodiment, the number of coordinates that the robot can take is very small, the force of the form The constraints in the real world are complicated, and the number of times of information exchange is very large. However, solving such a distributed constraint satisfaction problem with such a complex problem requires a very long time with the existing algorithm, but according to the present invention, it can be solved at high speed. Embodiments 1 to 3 simplify the problem to briefly explain it, and the scope of application of the agent according to the present invention is not limited to a simple problem. .
  • the present invention is not limited to the field of the above-described embodiment.
  • it can also be applied to task distribution to robots, robot position identification, and map creation by multiple robots.
  • variables and constraints are distributed for each robot, and it is necessary to solve them by using a plurality of robots. Therefore, the present invention can be applied.
  • the present invention provides a It can be applied to integration of sensing information. In order to remove the sensing noise and error of each sensor and obtain accurate information as a whole, it is necessary to solve the variables and restrictions of each sensor and the restrictions on the sensing information between sensors. it can.
  • the present invention can be applied to tasks such as task assignment to each sensor, formation of a network between sensors, assignment of communication frequency between sensors, and a device for sending sensing information to a target node.
  • the present invention can also be applied to an apparatus that assigns a tracking target to an observation device in tracking a plurality of observation targets by a plurality of observation devices.
  • an apparatus that assigns a tracking target to an observation device in tracking a plurality of observation targets by a plurality of observation devices.
  • variables and constraints such as the performance of each observation device, the observation range, and movement of the tracking target are distributed among the observation devices.
  • the present invention can be applied when operating in a distributed environment.
  • the present invention can be applied to production planning, inventory planning, delivery planning and the like in supply chain management.
  • the present invention can be applied to solving various logistic problems and planning.
  • the problem can be solved by distributing it, but the present invention can also be applied to concealing some information.
  • the present invention can also be applied to a power system facility work stoppage plan.
  • the present invention can also be applied to energy delivery plans based on energy demand forecasts. For example, in power distribution plans for power plants, the present invention can be applied even when various constraints and variables such as power plant capabilities and maintenance plans, demand forecasts, and distribution networks are distributed and operated in a distributed environment. it can.
  • the present invention can also be applied to an air conditioning plan using a plurality of air conditioning devices. Even when distributed air conditioning equipment adjusts the temperature independently, variables and constraints are dispersed! The present invention can also be applied to the case where each device solves the stale state. Further, the present invention can be applied to failure diagnosis of a system consisting of a plurality of devices, communication route routing, communication frequency allocation of a wireless network, and the like.
  • the present invention can also be applied to schedule creation and work assignment for railways, buses, and the like. For example, the creation of a diagram at a railway company that has multiple trains entering each other can be performed even when the variables of the diagram and restrictions on entry are distributed among the companies and the control of the variables is solved by each device.
  • the invention can be applied.
  • the agent that is effective in the present invention is suitable for a control device or the like that is mounted on a network-connected task allocation device, schedule device, robot, etc., autonomously communicates asynchronously with neighboring agents and cooperates to eliminate restrictions. .

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Health & Medical Sciences (AREA)
  • Computing Systems (AREA)
  • Biomedical Technology (AREA)
  • Biophysics (AREA)
  • Computational Linguistics (AREA)
  • Data Mining & Analysis (AREA)
  • Evolutionary Computation (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Molecular Biology (AREA)
  • Artificial Intelligence (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • Software Systems (AREA)
  • Health & Medical Sciences (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

L’invention concerne un agent comprenant une section de stockage variable stockant des données variables, une section de stockage de restriction stockant des données de restriction, une section de stockage de période d’inhibition de changement de variable stockant des données de période d’inhibition de changement de variable, une section de création de facilité d’amélioration permettant de créer des données de facilité d’amélioration représentant la facilité avec laquelle les données variables satisfont aux données de restriction, une section de communication permettant de communiquer les données de facilité d’amélioration avec des agents voisins, une section de stockage de situation voisine stockant les données de facilité d’amélioration sur les agents voisins, une section de résolution de constriction permettant de comparer les données de facilité d’amélioration et les données des agents voisins, de modifier les données variables afin de résoudre toute violation de restriction selon les données de période d’inhibition de changement de variable, et de mettre à jour les données de période d’inhibition de changement de variable. Lesdits nombreux agents coopèrent de manière asynchrone et résolvent toute violation de restriction. Tout le groupe d’agents obtient une solution plus rapidement sans tomber dans une solution optimale locale.
PCT/JP2006/308836 2005-04-27 2006-04-27 Agent et procédé de complément de restriction distribuée Ceased WO2006118193A1 (fr)

Priority Applications (1)

Application Number Priority Date Filing Date Title
JP2007514806A JPWO2006118193A1 (ja) 2005-04-27 2006-04-27 エージェントおよび分散制約充足方法

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
JP2005129304 2005-04-27
JP2005-129304 2005-04-27

Publications (1)

Publication Number Publication Date
WO2006118193A1 true WO2006118193A1 (fr) 2006-11-09

Family

ID=37307991

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2006/308836 Ceased WO2006118193A1 (fr) 2005-04-27 2006-04-27 Agent et procédé de complément de restriction distribuée

Country Status (2)

Country Link
JP (1) JPWO2006118193A1 (fr)
WO (1) WO2006118193A1 (fr)

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2011013810A (ja) * 2009-06-30 2011-01-20 Internatl Business Mach Corp <Ibm> 文字列の妥当性を判定するシステム、方法及びプログラム
US8528095B2 (en) 2010-06-28 2013-09-03 International Business Machines Corporation Injection context based static analysis of computer software applications
US8584246B2 (en) 2009-10-13 2013-11-12 International Business Machines Corporation Eliminating false reports of security vulnerabilities when testing computer software
JP2016166697A (ja) * 2015-03-09 2016-09-15 富士電機株式会社 負荷配分決定支援装置、そのプログラム、負荷配分決定支援方法
EP4625212A1 (fr) 2024-03-27 2025-10-01 Fujitsu Limited Programme de traitement de données, dispositif de traitement de données et procédé de traitement de données

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH09297689A (ja) * 1996-04-30 1997-11-18 Nippon Telegr & Teleph Corp <Ntt> 複数ジョブへの分散型資源割当方法

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH09297689A (ja) * 1996-04-30 1997-11-18 Nippon Telegr & Teleph Corp <Ntt> 複数ジョブへの分散型資源割当方法

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
FINK A. ET AL.: "Generic Application of Tabu Search Methods to Manufacturing Problems", PROCEEDINGS OF THE 1998 IEEE INTERNATIONAL CONFERENCE ON SYSTEMS, MAN, AND CYBERNETICS, October 1998 (1998-10-01), pages 2385 - 2390, XP010310633 *
HIRAYAMA K. ET AL.: "Local Search for Distributed SAT with Complex Local Problems", PROC. FIRST INT. JOINT CONF. AUTONOMOUS AGENT AND MULTIAGENT SYSTEM, July 2002 (2002-07-01), pages 1199 - 1206, XP003003083 *

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP2011013810A (ja) * 2009-06-30 2011-01-20 Internatl Business Mach Corp <Ibm> 文字列の妥当性を判定するシステム、方法及びプログラム
US8584246B2 (en) 2009-10-13 2013-11-12 International Business Machines Corporation Eliminating false reports of security vulnerabilities when testing computer software
US8528095B2 (en) 2010-06-28 2013-09-03 International Business Machines Corporation Injection context based static analysis of computer software applications
JP2016166697A (ja) * 2015-03-09 2016-09-15 富士電機株式会社 負荷配分決定支援装置、そのプログラム、負荷配分決定支援方法
EP4625212A1 (fr) 2024-03-27 2025-10-01 Fujitsu Limited Programme de traitement de données, dispositif de traitement de données et procédé de traitement de données

Also Published As

Publication number Publication date
JPWO2006118193A1 (ja) 2008-12-18

Similar Documents

Publication Publication Date Title
Fink et al. Robust control of mobility and communications in autonomous robot teams
Liu et al. An iterative two-phase optimization method based on divide and conquer framework for integrated scheduling of multiple UAVs
Çelik et al. The post-disaster debris clearance problem under incomplete information
Fink et al. Robust control for mobility and wireless communication in cyber–physical systems with application to robot teams
Fanti Event-based controller to avoid deadlock and collisions in zone-control AGVS
Kala Rapidly exploring random graphs: motion planning of multiple mobile robots
US20210232990A1 (en) Workflow deployment
WO2006118193A1 (fr) Agent et procédé de complément de restriction distribuée
Chen et al. Optimal path planning with spatial-temporal mobility modeling for individual-based emergency guiding
Dudeja Fuzzy-based modified particle swarm optimization algorithm for shortest path problems.
Lim et al. Congestion-aware multi-agent path planning: distributed algorithm and applications
Wang et al. Hybrid bidirectional rapidly exploring random tree path planning algorithm with reinforcement learning
CN119830712A (zh) 基于数字孪生的化工园区应急处理方法
Ye et al. Multi-agent pathfinding with communication reinforcement learning and deadlock detection
Laguna et al. Diversified local search for the optimal layout of beacons in an indoor positioning system
Desai et al. Adaptive routing based on predictive reinforcement learning
RU2742959C1 (ru) Система для управления работой участка железной дороги с построением единого расписания
Chen et al. Distributed in‐network path planning for sensor network navigation in dynamic hazardous environments
Navarro et al. Temporal bounded reasoning in a dynamic case based planning agent for industrial environments
Xiao et al. Cooperative reinforcement learning in topology-based multi-agent systems
Yu et al. Probability-triggered formation control with adaptive roles
Sreelekha et al. Revolutionizing Urban Traffic Management: IoT-Driven Algorithms for Intelligent Transportation Systems
Ilin et al. A survey of hybrid artificial intelligence algorithms for dynamic vehicle routing problem
Ahmed Modeling, scheduling and optimization of wireless sensor networks lifetime
Wu et al. A competitive analysis approach for route choice with uncertain travel times and blocked nodes

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 2007514806

Country of ref document: JP

NENP Non-entry into the national phase

Ref country code: DE

NENP Non-entry into the national phase

Ref country code: RU

122 Ep: pct application non-entry in european phase

Ref document number: 06745764

Country of ref document: EP

Kind code of ref document: A1