CONTROL APPARATUS, METHOD AND PROGRAM

Abstract

On the assumption that a combined control object unit and a second type control object unit are alternately disposed along a Hamilton cycle at intermediate positions, and intermediate positions include an intermediate position M before exchange and an intermediate position M after exchange, a control device includes a first movement planning unit 1 and a first movement unit 2 that move each control object at an initial position S to an intermediate position M before exchange in control object units, a second movement planning unit 3 that creates a second movement plan for moving each control object assumed to be at a target position G to an intermediate position M after exchange in control object units, and an intermediate position exchange unit 4 that moves each control object at the intermediate position M before exchange to a movement destination of each control object determined by the second movement plan among intermediate positions M after exchange.

Claims

1. A control device comprising, on the assumption that control object units include a first type control object unit and a second type control object unit, each of the first type control object unit and the second type control object unit is composed of U (U is an integer of 4 or more) control objects, an initial position S and a target position G are determined for each control object, a structure composed of control objects at initial positions S and target positions G is constituted by a combined control object unit composed of 2U control objects by combining the first type control object unit and the second type control object unit, a graph in which a control object unit at an intermediate position is defined as a node and a plane connecting two control object units in contact with each other is defined as an edge constitutes a part or the whole of a Hamilton cycle, a combined control object unit and a second type control object unit are alternately disposed at intermediate positions along the Hamilton cycle, and intermediate positions include an intermediate position M before exchange and an intermediate position M after exchange wherein: a first movement planning unit configured to create a first movement plan for moving each control object at an initial position S to an intermediate position M before exchange in control object units; a first movement unit configured to move each control object at the initial position S to the intermediate position M before exchange in control object units according to the first movement plan; a second movement planning unit configured to create a second movement plan for moving each control object assumed to be at a target position G to an intermediate position M after exchange in control object units; an intermediate position exchange unit configured to move each control object at the intermediate position M before exchange to a movement destination of each control object determined by the second movement plan among intermediate positions M after exchange; and a second movement unit configured to move each control object at the intermediate position M after exchange to a target position G in control object units according to a plan obtained by temporally reversing the second movement plan.

2. The control device according to claim 1, wherein the intermediate position exchange unit moves a first type control object unit j along the Hamiltonian cycle, and in a case in which there is a movement destination of a control object constituting the first type control object unit j, determined by the second movement plan, among second type control object units adjacent to the first type control object unit j, repeats processing of exchanging the control object with the control object at the movement destination to move each control object moved by the first movement unit to the movement destination of each control object determined by the second movement plan among intermediate positions M, wherein, in the processing, each control object unit moves at all positions on the Hamilton cycle as the first type control object unit j.

3. A control method, wherein control object units include a first type control object unit and a second type control object unit, each of the first type control object unit and the second type control object unit is composed of U (U is an integer of 4 or more) control objects, an initial position S and a target position G are determined for each control object, a structure composed of control objects at initial positions S and target positions G is constituted by a combined control object unit composed of 2U control objects by combining the first type control object unit and the second type control object unit, a graph in which a control object unit at an intermediate position is defined as a node and a plane connecting two control object units in contact with each other is defined as an edge constitutes a part or the whole of a Hamilton cycle, a combined control object unit and a second type control object unit are alternately disposed at intermediate positions along the Hamilton cycle, and intermediate positions include an intermediate position M before exchange and an intermediate position M after exchange, the control method comprising: a first movement planning step of creating, by a first movement planning unit, a first movement plan for moving each control object at an initial position S to an intermediate position M before exchange in control object units; a first movement step of moving, by a first movement unit, each control object at the initial position S to the intermediate position M before exchange in control object units according to the first movement plan; a second movement planning step of creating, by a second movement planning unit, a second movement plan for moving each control object assumed to be at a target position G to an intermediate position M after exchange in control object units; an intermediate position exchange step of moving, by an intermediate position exchange unit, each control object at the intermediate position M before exchange to a movement destination of each control object determined by the second movement plan among intermediate positions M after exchange; and a second movement step of moving, by a second movement unit, each control object at the intermediate position M after exchange to a target position G in control object units according to a plan obtained by temporally reversing the second movement plan.

4. (canceled)

5. A control device comprising, A computer-readable non-transitory recording medium storing computer-executable program instructions that when executed by a processor cause a computer to execute a control method comprising: on the assumption that control object units include a first type control object unit and a second type control object unit, each of the first type control object unit and the second type control object unit is composed of U (U is an integer of 4 or more) control objects, an initial position S and a target position G are determined for each control object, a structure composed of control objects at initial positions S and target positions G is constituted by a combined control object unit composed of 2 U control objects by combining the first type control object unit and the second type control object unit, a graph in which a control object unit at an intermediate position is defined as a node and a plane connecting two control object units in contact with each other is defined as an edge constitutes a part or the whole of a Hamilton cycle, a combined control object unit and a second type control object unit are alternately disposed at intermediate positions along the Hamilton cycle, and intermediate positions include an intermediate position M before exchange and an intermediate position M after exchange wherein: a first movement planning unit configured to create a first movement plan for moving each control object at an initial position S to an intermediate position M before exchange in control object units; a first movement unit configured to move each control object at the initial position S to the intermediate position M before exchange in control object units according to the first movement plan; a second movement planning unit configured to create a second movement plan for moving each control object assumed to be at a target position G to an intermediate position M after exchange in control object units; an intermediate position exchange unit configured to move each control object at the intermediate position M before exchange to a movement destination of each control object determined by the second movement plan among intermediate positions M after exchange; and a second movement unit configured to move each control object at the intermediate position M after exchange to a target position G in control object units according to a plan obtained by temporally reversing the second movement plan.

6. The computer-readable non-transitory recording medium according to claim 5 wherein the control method further comprises: the intermediate position exchange unit moves a first type control object unit j along the Hamiltonian cycle, and in a case in which there is a movement destination of a control object constituting the first type control object unit j, determined by the second movement plan, among second type control object units adjacent to the first type control object unit j, repeats processing of exchanging the control object with the control object at the movement destination to move each control object moved by the first movement unit to the movement destination of each control object determined by the second movement plan among intermediate positions M, wherein, in the processing, each control object unit moves at all positions on the Hamilton cycle as the first type control object unit j.

Description

BRIEF DESCRIPTION OF DRAWINGS

[0016] FIG. 1 is a diagram for describing an example of robot movement.

[0017] FIG. 2 is a diagram for describing examples of an initial position and a target position of a control object unit.

[0018] FIG. 3 is a diagram for describing an example of a state of void movement.

[0019] FIG. 4 is a diagram for describing an example of a control object unit.

[0020] FIG. 5 is a diagram for describing an example of forms of intermediate positions M and M.

[0021] FIG. 6 is a diagram for describing an example of generating the intermediate position M.

[0022] FIG. 7 is a diagram for describing numbering of each position of the intermediate position M.

[0023] FIG. 8 is a diagram for describing numbering of each position of the intermediate position M.

[0024] FIG. 9 is a diagram for describing an intermediate position Mpre in a transformation process of S.fwdarw.M.

[0025] FIG. 10 is a diagram for describing an exchange process.

[0026] FIG. 11 is a diagram for describing formation of the intermediate position M when A_max=0.

[0027] FIG. 12 is a diagram for describing the intermediate position M when A_max=1, 2.

[0028] FIG. 13 is a diagram for describing an example of movement of a control object unit.

[0029] FIG. 14 is a diagram for describing an example of movement of a control object unit.

[0030] FIG. 15 is a diagram for describing transformation from LCMM to UCMM of a control object unit.

[0031] FIG. 16 is a diagram for describing transformation from LCMM to UCMM of a control object unit.

[0032] FIG. 17 is a diagram for describing an operation example of an exchange process.

[0033] FIG. 18 is a diagram for describing an operation example of an exchange process.

[0034] FIG. 19 is a diagram for describing an operation example of an exchange process.

[0035] FIG. 20 is a diagram for describing an operation example of an exchange process.

[0036] FIG. 21 is a diagram for describing an operation example of an exchange process.

[0037] FIG. 22 is a diagram for describing an operation example of an exchange process.

[0038] FIG. 23 is a diagram for describing an operation example of an exchange process.

[0039] FIG. 24 is a diagram for describing an operation example of an exchange process.

[0040] FIG. 25 is a diagram for describing an operation example of an exchange process.

[0041] FIG. 26 is a diagram for describing an operation example of an exchange process.

[0042] FIG. 27 is a diagram for describing an operation example of an exchange process.

[0043] FIG. 28 is a diagram for describing an example of an exchange operation of a control object.

[0044] FIG. 29 is a diagram for describing an example of an exchange operation of a control object.

[0045] FIG. 30 is a diagram for describing an example of an exchange operation of a control object.

[0046] FIG. 31 is a diagram for describing an example of an exchange operation of a control object.

[0047] FIG. 32 is a diagram for describing an example of an exchange operation of a control object.

[0048] FIG. 33 is a diagram for describing an example of an exchange operation of a control object.

[0049] FIG. 34 is a diagram for describing an example of an exchange operation of a control object.

[0050] FIG. 35 is a diagram for describing an example of an exchange operation of a control object.

[0051] FIG. 36 is a diagram for describing an example of an exchange operation of a control object.

[0052] FIG. 37 is a diagram for describing an example of an exchange operation of a control object.

[0053] FIG. 38 is a diagram for describing an example of an exchange operation of a control object.

[0054] FIG. 39 is a diagram for describing an example of an exchange operation of a control object.

[0055] FIG. 40 is a diagram for describing an example of an exchange operation of a control object.

[0056] FIG. 41 is a diagram for describing an example of an exchange operation of a control object.

[0057] FIG. 42 is a diagram for describing an example of an exchange operation of a control object.

[0058] FIG. 43 is a diagram for describing an example of an exchange operation of a control object.

[0059] FIG. 44 is a diagram for describing an example of an exchange operation of a control object.

[0060] FIG. 45 is a diagram for describing an example of an exchange operation of a control object.

[0061] FIG. 46 is a diagram for describing an example of an exchange operation of a control object.

[0062] FIG. 47 is a diagram for describing an example of an exchange operation of a control object.

[0063] FIG. 48 is a diagram for describing an example of an exchange operation of a control object.

[0064] FIG. 49 is a diagram for describing an example of an exchange operation of a control object.

[0065] FIG. 50 is a diagram for describing an example of an exchange operation of a control object.

[0066] FIG. 51 is a diagram for describing an example of an exchange operation of a control object.

[0067] FIG. 52 is a diagram for describing an example of an exchange operation of a control object.

[0068] FIG. 53 is a diagram for describing an example of an exchange operation of a control object.

[0069] FIG. 54 is a diagram for describing an example of an exchange operation of a control object.

[0070] FIG. 55 is a diagram for describing an example of an exchange operation of a control object.

[0071] FIG. 56 is a diagram for describing an example of an exchange operation of a control object.

[0072] FIG. 57 is a diagram for describing an example of an exchange operation of a control object.

[0073] FIG. 58 is a diagram for describing an example of an exchange operation of a control object.

[0074] FIG. 59 is a diagram for describing an example of an exchange operation of a control object.

[0075] FIG. 60 is a diagram for describing an example of an exchange operation of a control object.

[0076] FIG. 61 is a diagram for describing an example of an exchange operation of a control object.

[0077] FIG. 62 is a diagram for describing an example of an exchange operation of a control object.

[0078] FIG. 63 is a diagram for describing an example of an exchange operation of a control object.

[0079] FIG. 64 is a diagram for describing an example of an exchange operation of a control object.

[0080] FIG. 65 is a diagram for describing an example of an exchange operation of a control object.

[0081] FIG. 66 is a diagram for describing an example of an exchange operation of a control object.

[0082] FIG. 67 is a diagram for describing an example of an exchange operation of a control object.

[0083] FIG. 68 is a diagram for describing an example of an exchange operation of a control object.

[0084] FIG. 69 is a diagram for describing an example of an exchange operation of a control object.

[0085] FIG. 70 is a diagram for describing an example of an exchange operation of a control object.

[0086] FIG. 71 is a diagram for describing an example of an exchange operation of a control object.

[0087] FIG. 72 is a diagram for describing an example of an exchange operation of a control object.

[0088] FIG. 73 is a diagram for describing an example of an exchange operation of a control object.

[0089] FIG. 74 is a diagram for describing an example of an exchange operation of a control object.

[0090] FIG. 75 is a diagram for describing an example of an exchange operation of a control object.

[0091] FIG. 76 is a diagram for describing an example of an exchange operation of a control object.

[0092] FIG. 77 is a diagram for describing an example of an exchange operation of a control object.

[0093] FIG. 78 is a diagram for describing an example of an exchange operation of a control object.

[0094] FIG. 79 is a diagram for describing an example of an exchange operation of a control object.

[0095] FIG. 80 is a diagram for describing an example of an exchange operation of a control object.

[0096] FIG. 81 is a diagram for describing an example of an exchange operation of a control object.

[0097] FIG. 82 is a diagram for describing an example of an exchange operation of a control object.

[0098] FIG. 83 is a diagram for describing an example of an exchange operation of a control object.

[0099] FIG. 84 is a diagram for describing an example of an exchange operation of a control object.

[0100] FIG. 85 is a diagram for describing an example of an exchange operation of a control object.

[0101] FIG. 86 is a diagram for describing an example of an exchange operation of a control object.

[0102] FIG. 87 is a diagram for describing an example of an exchange operation of a control object.

[0103] FIG. 88 is a diagram for describing an example of an exchange operation of a control object.

[0104] FIG. 89 is a diagram for describing an example of an exchange operation of a control object.

[0105] FIG. 90 is a diagram for describing an example of an exchange operation of a control object.

[0106] FIG. 91 is a diagram for describing an example of an exchange operation of a control object.

[0107] FIG. 92 is a diagram for describing an example of an exchange operation of a control object.

[0108] FIG. 93 is a diagram for describing an example of an exchange operation of a control object.

[0109] FIG. 94 is a diagram for describing an example of an exchange operation of a control object.

[0110] FIG. 95 is a diagram for describing an example of an exchange operation of a control object.

[0111] FIG. 96 is a diagram for describing an example of an exchange operation of a control object.

[0112] FIG. 97 is a diagram for describing an example of an exchange operation of a control object.

[0113] FIG. 98 is a diagram for describing an example of an exchange operation of a control object.

[0114] FIG. 99 is a diagram for describing an example of an exchange operation of a control object.

[0115] FIG. 100 is a diagram for describing an example of an exchange operation of a control object.

[0116] FIG. 101 is a diagram for describing an example of an exchange operation of a control object.

[0117] FIG. 102 is a diagram for describing an example of an exchange operation of a control object.

[0118] FIG. 103 is a diagram for describing an example of an exchange operation of a control object.

[0119] FIG. 104 is a diagram for describing an example of an exchange operation of a control object.

[0120] FIG. 105 is a diagram for describing an example of an exchange operation of a control object.

[0121] FIG. 106 is a diagram for describing an example of an exchange operation of a control object.

[0122] FIG. 107 is a diagram for describing an example of an exchange operation of a control object.

[0123] FIG. 108 is a diagram showing an example of a functional configuration of a control device.

[0124] FIG. 109 is a diagram showing an example of a processing procedure of a control method.

[0125] FIG. 110 is a diagram showing a functional configuration example of a computer.

DESCRIPTION OF EMBODIMENTS

[0126] Hereinafter, embodiments of the present invention will be described. Note that in the figures used in the following description, constituent parts having identical functions and steps in which identical processing is performed are denoted by the same reference numerals, and redundant description thereof will be omitted.

Theoretical Background

[0127] First, a theoretical background to a control device and method will be described. Although a case in which a control object serving as an action control subject is a robot will be described below as an example, the control object is not limited to a robot and may be any object that can be a control subject.

Problem Setting

[0128] In a task in which a large number of control objects cooperatively perform formation transformation from a formation creation state at an initial position to a target position by moving while maintaining a state in which respective control objects are in contact with each other, it is assumed that cubic control objects capable of moving by sliding over a mutual contact plane, as illustrated in FIG. 1, for example, are used. This is realized by movement of a plurality of control objects from an initial position to a target position in a room partitioned by walls (walls are omitted in the figure), as shown in FIG. 2.

[0129] As shown in FIG. 1, for example, a control object is assumed to move while maintaining a state in which another control object is present in one of 6 squares in vertical, horizontal and height directions around the control object (hereinafter, referred to as upward, downward, leftward, rightward, frontward, and rearward directions). This method has an advantage in that by moving one control object itself by a distance corresponding to the size of a single control object, the movement amount of a single action can be measured accurately. Further, by measuring relative positions of adjacent control objects sharing a single plane, the position of each control object from among all of the control objects in a control object group can easily be ascertained. As a result, a problem in which the formation collapses due to an error in the movement amount of the control objects is unlikely to occur. Furthermore, a plurality of control objects can be moved simultaneously as if the plurality of control objects had been connected. Note that the control object is assumed to be capable of ascertaining whether or not another control object is present in a position adjacent thereto, whether or not there is an obstacle, and whether or not the control object itself is in a target position.

[0130] The number of control objects performing the task is p (where p24=83 is satisfied), and each control object is assumed to be capable of moving in X-Y-Z axis directions within a three-dimensional space while sharing at least one plane with the adjacent control object. Each cube in FIG. 1 shows the position of one control object. Only one control object can exist in each cube. It is assumed that each control object stops in a case where an obstacle or another control object is present in a direction in which the control object attempts to move. Note that a cubic space in which the control object can be present is also referred to as a square or a grid cell. In FIG. 2, dark gray squares indicate the positions at which control objects are present. The position where the control objects are present in FIG. 2A indicates a set of initial positions of the control objects, and the position where the control objects are present in FIG. 2C indicates a set of target positions of the control objects. As shown in FIG. 2B, the set of target positions and the set of initial positions are in contact with each other or have overlapping parts (common parts). An area represented by a set of target positions is also referred to as a target formation area. In this manner, each initial position and each target position is adjacent to another initial position and target position in at least any of the vertical, horizontal and height directions, and formation shapes at the initial positions and target positions of the control objects are groups of arbitrary shapes.

[Coordinate Setting of Control Object]

[0131] When the position of each control object i (i represents a control object number, i=0, 1, 2, 3, . . . , p1) is (Xr[i], Yr[i], Zr[i]), an initial position is (Xr0[i], Yr0[i], Zr0[i]), and a target position is (Xre[i], Yre[i], Zre[i]), the problem can be defined as obtaining an action plan for moving the control object disposed at the initial position to the target position. A set of initial positions of the control object is represented by s, and a set of target positions (Xre[i], Yre[i], Zre[i]) is represented by g.

[Definition of Task Space]

[0132] When i is defined as a control object number, each state of the control object i (position and action of the control object) is represented by a discrete value. When a room is represented by a three-dimensional space composed of the X, Y and Z orthogonal coordinate system, each position is represented by values obtained by discretely representing the X-axis, the Y-axis, and the Z-axis. That is, the room (three-dimensional space) is divided into grid cells, and each grid cells corresponds to each position. In addition, in each grid cell, presence or absence of an obstacle is set in advance.

[Definition of Control Object Operation]

[0133] Further, a subject of action is each control object disposed in the room. An action a of the control object i (i is a control object number) takes one of seven kinds of remaining stationary and moving by one grid cell in the vertical, horizontal and height directions. For example, a{0, 1, 2, 3, 4, 5, 6} is established. [0134] 0: remaining stationary [0135] 1: moving by one grid cell within the three-dimensional space in a direction in which the X coordinate value increases [0136] 2: moving by one grid cell within the three-dimensional space in a direction in which the Y coordinate value increases [0137] 3: moving by one grid cell within the three-dimensional space in a direction in which the X coordinate value decreases [0138] 4: moving by one grid cell within the three-dimensional space in a direction in which the Y coordinate value decreases [0139] 5: moving by one grid cell within the three-dimensional space in a direction in which the Z coordinate value increases [0140] 6: moving by one grid cell within the three-dimensional space in a direction in which the Z coordinate value decreases are defined.

[Problem in Search Calculation]

[0141] The state space in such a task environment includes a number of states corresponding to the number of dimensions of control objects3, and the number of selectable actions is equal to the number of actions of the control objects (=7) multiplied by the number of control objects. For example, if the number of control objects is 50 and the number of grid cells in the vertical, horizontal and height directions of the room is 20 each, the number of states is 20 to the power of 150, and thus a massive amount of resources is required for search calculations. Moreover, each time the number of control object increases by 1, the number of states increases 8000 times. As described in [problem setting] section of the present embodiment, in a case in which the constraint condition that the control objects are in contact with each other is adopted, search calculations need to be performed in consideration of mutual movement of the control objects, and thus it is difficult to reduce the basic calculation amount, which becomes a significant problem in cases where a plurality of control objects are used.

Features in Reference 1

[0142] In the heterogeneous formation control in Reference 1, a concept of void control is introduced as one of measures for solving the above-described calculation load problem. In addition, in order to overcome the problem of formation transformation as described in the [problem setting], a concept of 8-square control objects is also introduced. First, void control will be described. A void mentioned here is a void, as illustrated in FIG. 3, formed at a vacant position after a certain control object has moved to another position. In other words, the void is a virtual presence that moves in a direction opposite to a direction in which the control object moves. In such a formation creation problem of group control objects, the search calculation amount significantly increases since attention is paid to the operations of a plurality of control objects, however, if attention is paid to movement of a void by changing a viewpoint, the problem of the operation plan of a large number of control objects can be considered as an operation plan of a single void, and it is suitable to reduce the search calculation load. However, each control object belonging to the control object unit is scattered during the transformation operation, and is divided into different control object units, leading to increase in the load of the subsequent control object exchange operation, and a space other than sets of initial positions and target positions is not required for transformation, but a delay of transformation in which a time required for transformation is proportional to a square of the number of control objects becomes a problem. The main cause is the duration of a time required for the position exchange operation of each control object. At the time of performing the exchange operation, it is difficult to secure a space necessary for the exchange operation in a robot structure in which control objects are densely assembled and therefore, it is difficult to speed up an exchange process by performing the exchange operations of a plurality of sets of control objects in parallel. [0143] [Reference 1] Kawano, H., Tunneling-Based Self-Reconfiguration of Heterogeneous Sliding Cube-Shaped Modular Robots in Environments with Obstacles, 2017 IEEE International Conference on Robotics and Automation, pp. 825-832, May 2017, Singapore.

[Introduction of 4-Square Control Object Unit]

[0144] Therefore, as shown in FIG. 4A, four adjacent control objects are defined as one unit (control object unit) and the control objects are assumed to move while maintaining the control object unit. In other words, one control object unit is configured for four control objects, and the four control objects constituting one control object unit move while maintaining a state in which they are adjacent to other control objects constituting one control object unit in three directions. The group of control object unit is controlled such that the control objects share one plane for each control object unit and move in contact with each other. It is assumed that four control objects belonging to the same control object unit are not the same but heterogeneous, and each control object has a unique target position even in a control object unit and moves between different control object units before and after formation transformation.

[0145] The reason why the four control objects are moved as one unit is that the control objects belonging to another control object unit can pass through four void spaces inside each control object unit, and thus the control objects belonging to different control object units can easily come and go. Further, it is easy to maintain connectivity when the control objects belonging to another control object unit pass through the four void spaces inside each control object unit. That is, this is because the calculation load for considering connection between the control objects is reduced in determination of the operation of each control object for which maintaining of formation shape needs to be considered.

[0146] Here, the control object unit formed by the four control objects is defined as one square unit (this unit is referred to as a square unit or a position unit below in the present embodiment), and one square unit is set as one state to form a state space. When the position of a control object unit is (Xr_u[j], Yr_u[j], Zr_u[j]) (j=0, 1, 2, . . . , j_max1), if the control objects in the control object unit j are defined as i1, i2, i3, and i4,

Xr[i1]=2Xr_u[j]

Yr[i1]=2Yr_u[j]+1

Zr[i1]=2Zr_u[j]

Xr=2Xr_u[j]+1

Yr=2Yr_u[j]

Zr=2Zr_u[j]

Xr=2Xr_u[j]

Yr=2Yr_u[j]

Zr=2Zr_u[j]+1

Xr=2Xr_u[j]

Yr=2Yr_u[j]

Zr=2Zr_u[j]

[0147] Note that a variable representing the control object unit j to which each control object i belongs is defined as Rr[i]=j. Further, a variable indicating which position of i1, i2, i3, i4 is the position of the control object i is defined as Ir[i]=(1, 2, 3, 4). The initial position of each control object unit is defined as (Xr_u0[j], Yr_u0[j], Zr_u0[j]), and the target position is defined as (XR_ue[j], Yr_ue[j], Zr_ue[j]. Hereinafter, the total number of control objects p is set to a multiple of 4.

[0148] As shown in FIG. 4B, it is also possible to constitute a control object unit with 8 squares by combining two control object units, and it is also possible to perform formation control of the control object group constituted by the control object unit with 8 squares by controlling the control object unit with 4 squares. A combination of two control object units may be referred to as a combined control object unit.

[0149] In addition, the present invention is not limited to the example shown in FIG. 4, and the control object unit may be configured to satisfy the following conditions. That is, the control object unit is (1) a substructure in a cubic space (this space is hereinafter referred to as a meta module) having a length M (M2, where the length of one control object is 1) in each axial direction in a three-dimensional orthogonal coordinate system (in other words, the control object unit occupies a part of the meta module), (2) the number of control objects included in the control object unit in the meta module is equal to the number of parts (i.e., voids) other than the control object unit in the meta module, and (3) M control objects are adjacent to each other in each axial direction. For example, the control object unit illustrated in FIG. 4 is (1) a substructure of a meta module composed of cubes of 8 squares in total having a length M=2 in each axial direction, (2) the number of control objects in the control object unit and the number of voids in the meta module are identical as 4, and (3) two control objects are adjacent to each other in each axial direction.

[0150] Although a case in which a structure constituted by four control objects shown in FIG. 4 is defined as a control object unit will be described as an example of the control object unit in the following description, if a control object unit is configured to satisfy the above-described conditions (1) to (3) in a meta module having a size of M.sup.3, for example, the same effect can be obtained.

[Heterogeneous Formation Control]

[0151] A heterogeneous control object formation control method in which a structure composed of control objects i constituting an 8-square control object unit is transformed from a state in which each control object is present at an initial position (Xr0[i], Yr0[i], Zr0[i]) in a set S of initial positions to a state in which each control object is present at a target position (Xre[i], Yre[i], Zre[i]) in a set G of target positions will be described below.

[0152] It is assumed that the sets S and G are composed of an 8-square control object unit formed by combining two 4-square control object units. The number j_max of 4-square control object units is an even number, and the numbers of two 4-square control object units j1 and j2 constituting one 8-square control object unit has a relationship of j1+j_max/2=j2 therebetween (In the case of j_max=8, j1 is 0, 1, 2 and 3, and j2 is 4, 5, 6 and 7, sets of (j1, j2)=(0, 4) (1, 5) (2, 6) (3, 7) constitute the 8-square unit). j2 is a 4-square control object unit represented by dots in FIG. 4B. The name of j1 is defined as LCMM, and the name of j2 is defined as UCMM. In some cases, j1 is referred to as a second type control object unit, and j2 is referred to as a first type control object unit. If control objects in the j-th UCMM are set to i5, 16, i7, and i8 (FIG. 4),

Xr=2Xr_u[j]+1

Yr=2Yr_u[j]

Zr=2Zr_u[j]+1

Xr=2Xr_u[j]+1

Yr=2Yr_u[j]+1

Zr=2Zr_u[j]

Xr=2Xr_u[j]

Yr=2Yr_u[j]+1

Zr[i7]=2Zr_u[j]+1

Xr=2Xr_u[j]+1

Yr=2Yr_u[j]+1

Zr=2Zr_u[j]+1

[0153] Similarly, in the UCMM, a variable representing the control object unit j to which each control object i belongs is defined as Rr[i]=j. In addition, a variable indicating which position of i5, 16, i7, and i8 is the position of the control object i is defined as Ir[i]=(5, 6, 7, 8).

[0154] In this manner, it is assumed that the control object unit includes the first type control object unit and the second type control object unit, each of the first type control object unit and the second type control object unit is composed of U (U is an integer of 4 or more) control objects, an initial position and a target position are determined for each control object, and a structure composed of control objects at the initial positions and the target positions is constituted by a combined control object unit which is composed of 2 U control objects by combining the first type control object unit and the second type control object unit.

[0155] In the process of transformation, an intermediate position at the start of an exchange process for exchanging the positions of each robot is defined as M, and an intermediate position after the exchange process is defined as M. M and M are not a form constituted by an 8-square robot unit such as S and G, but a form in which only LCMM is present at a certain robot unit position.

[0156] Here, transformation of robots from S to G is divided into the following three processes. [0157] (1) Homogeneous transformation process from S to M [0158] (2) Process of exchanging the position of each control object at M After the exchange process, M.fwdarw.M is achieved. [0159] (3) Homogeneous transformation process from M to G

[0160] In the transformation process of (1) and (3), a homogeneous transformation method proposed in the past is utilized (for example, PCT/JP 2021/025458), and in transformation of S.fwdarw.M, S is first transformed into an intermediate form Mpre of an 8-square form by homogeneous transformation, and Mpre is transformed into M through the method proposed in the present invention. Even in transformation of M.fwdarw.G, G is first transformed into an intermediate form Mpost of the 8-square form by homogeneous transformation, the process of transforming Mpost into M through the method proposed in the present invention is calculated by simulation, and the calculated operation is reversely reproduced.

[0161] The robot intermediate positions M and M where the control object exchange process in the process (2) is performed are constituted by a mixture of 4-square control object units LMCC and UCMM (note that, unlike S and G which are composed of 8 squares, there is a robot unit position where LCMM is present alone). By adopting a robot structure constituted by 4-square control object units, it is possible to secure a space of 4 squares for allowing control objects belonging to another control object unit to pass through each control object unit and allowing each control object to exchange the position. Each control object unit in M secures such a space, and thus the control object exchange operations can be performed simultaneously in parallel in the respective control object units, and the exchange operations can be performed at a high speed.

[0162] As another condition regarding the forms of M and M, in a graph created when each LCMM in M and M is defined as a node (vertex) and two planes connecting two LCMMs in contact with each other are defined as edges (branches), the graph needs to form a part of the Hamilton cycle pH. This is because a plurality of control objects moving simultaneously in parallel to the positions of control objects of exchange destinations for the exchange operation can reach the positions of the respective exchange destinations while avoiding collision with each other by tracing the common cycle pH. In this method, although it is difficult to individually optimize routes to be traced by the respective control objects, it is possible to easily increase the number of control objects which are simultaneously exchanged to a number close to the total number of control objects while providing routes with a length having no practical problem to the respective control objects. As another approach, there is an approach of optimizing and calculating a route for each control object unit which moves simultaneously by route search while taking collision avoidance into consideration without using the Hamilton cycle pH, but in a case in which the number of control object units which are simultaneously exchanged is increased to the limit as in the present invention, there is a small space available for securing the moving route of each moving control object, and thus it is still difficult to realize a method of providing a solution with a satisfactory high speed for the shape of an arbitrary robot structure through a route search based approach (a limited solution only for a rectangular parallelepiped robot structure has been reported), and therefore, the approach using the Hamilton cycle pH is advantageous in terms of realization.

[0163] Under the conditions related to the forms of M and M described above, the transformation processes of (1) and (3) are transformation processes between S and G composed of an 8-square control object unit and M and M composed of a 4-square control object, and thus they are transformation in which a structure formed of an 8-square control object unit is developed into a structure formed of a 4-square control object unit. As a matter of course, SnG (common part of S and G) may not be a O set as the positional relationship between S and G, and thus as a result, it is also necessary to consider that there are a plurality of control objects included in SOM (common part of S and M) and MNG (common part of M and G), but this corresponds to the aforementioned homogeneous transformation technique (for example, the method described in PCT/JP2021/025458). The problem in Low speed property of heterogeneous transformation resulting from difficulty in simultaneous movement of control objects due to a dense robot structure in [Reference 1] can be solved by adopting a structure having a large number of voids using the 4-square control object unit in M and M in the present invention.

[Determination of Intermediate Positions M and M]

[0164] The form of M (and M. Only M will be described hereinafter) will be described. As shown in FIG. 5, in a graph formed when an LCMM in M is defined as a node (vertex) and two planes connecting two control object units in contact with each other are defined as edges (branches), the graph needs to form a part of the Hamilton cycle pH (here, it is said that M is a Hamilton graph shape) (In FIG. 5, among the Hamilton cycle pH including twelve control object unit positions, ten control object unit positions are occupied by the LCMM in M). A graph created by LCMMs in M forms one Hamilton path (not limited to a cycle). UCMMs in M are disposed such that a control object unit position having only the LCMM and a control object unit position having an 8-square control object unit composed of LCMM+UCMM alternately appear along a Hamilton cycle including LCMMs. With this structure, the number of LCMMs in M becomes almost twice the number of UCMMs, and thus the number of control object unit positions occupied by M becomes almost j_max(2/3) which is a Number (4/3) Times the Number of control object unit positions occupied by S and G. Here, the reason why almost is described is that the accurate number slightly differs depending on the number of the remainder obtained by dividing J_max/2 (=the number of control object unit positions in S and G) by 3. In the example shown in FIG. 5, the number of UCMMs is 5 and, the number of LCMMs is 10, and thus the number of LCMMs is just twice the number of UCMMs. By adopting such a structure of M, heterogeneous transformation can be performed simply by excessively requiring an area having a size of about (1/3) of the size of S and G for the intermediate position M (in the method shown in NPL 2, an area having a size of about twice the size of S and G is occupied by the intermediate position M).

[0165] Here, in the present state of graph theoretical research, since a method for generally determining whether or not an arbitrary graph has a Hamilton cycle when the graph is given has not been established, it is impossible to easily determine whether or not S+G is a Hamilton graph shape, for example. Therefore, it is considered that a Hamilton graph satisfying geometric conditions to be taken by M is generated from scratch.

[0166] This technique will be briefly described. First, as a robot structure having a small Hamilton graph shape, a structure M.sub.0 in which four control object units are arranged in a square shape is considered. M.sub.0 clearly has a Hamilton cycle around four sides of a square as shown in FIG. 6. Here, two adjacent vertexes on the Hamilton cycle (for example, two adjacent control object units 1 and 2) are selected, two control objects a and b at positions in contact with the two control object units and at positions not overlapping the control object in M.sub.0 are added to M.sub.0, and a structure in which edges respectively connecting the control object unit 1 and a, a and b, and b and 2 are added is defined as M.sub.1. Then, M.sub.1 is a Hamilton graph-shaped structure having a Hamilton cycle 1.fwdarw.a.fwdarw.b.fwdarw.2.fwdarw.3.fwdarw.4.fwdarw.1. M.sub.L is grown by repeating addition of such two control objects to M.sub.L (L=0, 1, 2, 3, . . . ), and when the number of control object units included in M.sub.L finally exceeds a certain value, M.sub.L satisfies conditions required for the Hamilton cycle shape including M. The number of control object units to be included at the minimum in M.sub.L slightly differs depending on the value of j_max/2. In a case in which the quotient obtained by dividing j_max/2 by 3 is defined as k_max and the remainder is defined as A_max, when the remainder A_max is 0, the number of UCMMs in M is 2k_max, the number of LCMMs is 4k_max, and the number of control object unit positions to be included at the minimum in M.sub.L is 4k_max+2. When the remainder A_max is 1, the number of UCMMs in M is 2k_max, the number of LCMMs is 4k_max+2, and the number of control object unit positions to be included at the minimum in M.sub.L is 4k_max+2. When the remainder A_max is 2, the number of UCMMs in M is 2k_max+1, the number of LCMMs is 4k_max+3, and the number of control object unit positions to be included at the minimum in M.sub.L is 4k_max+4. Hereinafter, the number of UCMMs in M is defined as N.sub.ucmm, the number of LCMMs is defined as N.sub.lcmm, and the number of control object units to be included at the minimum in M.sub.L is defined as N.sub.hamilton_min.

[0167] In this case, by setting M.sub.0 and repeatedly adding two control objects to M.sub.L after setting of M.sub.0 in consideration of the position of an obstacle in the space where transformation of robots is performed and the shapes of S and G, the shape of M can be determined in consideration of various geometric conditions of the space where transformation of robots is performed.

[0168] For example, M can be determined by the following processing.

[M_Decision]

[0169] (1) M.sub.0 to be settled within S+G is selected. [0170] (2) The following (3) and (4) are repeated. [0171] (3) Control object units included in M.sub.L are numbered 0, 1, 2, 3, . . . , (41)+L2 in the order traced by the Hamiltonian cycle in M.sub.L to be represented as pH0, pH1, pH2, pH3, . . . , pH(4-1)+L2. k=0 is set. [0172] (4) Two control object units having adjacent numbers (k and k+1. (41)+L2 and 0 when k=(41)+L2) are selected in ascending order, and in a case in which there are two new control object unit positions which are in contact with both the two control object units, are within S+G and are not within M.sub.L each time selection is performed, the two new control object unit positions (defined as a and b) are added to M.sub.L, and a Hamilton cycle of M.sub.L+1 is set to pH 0, pH 1, . . . , pH k, a, b, pH k+1, . . . , pH (4-1)+L2. In a case in which the control object unit positions included in M.sub.L+1 do not reach N.sub.hamilton_min, processing returns to (3). In a case in which the control object unit positions included in M.sub.L+1 reach N.sub.hamilton_min, processing is terminated. In a case in which there is no control object position which is within additional S+G and not within M.sub.L with respect to all adjacent control object sets in the Hamilton cycle in M.sub.L, processing proceeds to (5). [0173] (5) The following (6) and (7) are repeated. [0174] (6) The control object units included in M.sub.L are numbered 0, 1, 2, 3, . . . (41)+L2 in the order of the Hamiltonian cycle in M.sub.L to be represented as pH0, pH1, pH2, pH3, . . . , pH(41)+L2. k=0 is set. [0175] (7) Two control object units having adjacent numbers (k and k+1. (41)+L2 and 0 when k=(41)+L2) are selected in ascending order, and in a case in which there are two new control object unit positions which are in contact with both the two control object units, at least one of which is within S+G, both of which are not within M.sub.L, and which do not overlap an obstacle position, the two new control object unit positions (defined as a and b) are added to M.sub.L and a Hamilton cycle of M.sub.L+1 is set to pH 0, pH 1, . . . , pH k, a, b, pH k+1, . . . , pH (4-1)+L2. In a case in which the number of control object unit positions included in M.sub.L+1 does not reach N.sub.hamilton_min, processing returns to (6). In a case in which the number of control object unit positions included in M.sub.L+1 reaches N.sub.hamilton_min, processing ends. In a case in which there is no control object position that can be added with respect to all adjacent control object sets in the Hamilton cycle in M.sub.L, processing proceeds to (8). [0176] (8) The following (9) and (10) are repeated. [0177] (9) Control object units included in M.sub.L are numbered 0, 1, 2, 3, . . . , (4-1)+L2 in the order traced by the Hamilton cycle in M.sub.L to be represented as pH0, pH1, pH2, pH3, . . . , pH(41)+L2. k=0 is set.) [0178] (10) Two control object units having adjacent numbers (k and k+1. (41)+L2 and 0 when k=(41)+L2) are selected in ascending order, and in a case in which there are two new control object unit positions which are in contact with both the two control object units, are not within M.sub.L and do not overlap an obstacle position, the two new control object unit positions (defined as a and b) are added to M.sub.L, and the Hamilton cycle of M.sub.L+1 is set to pH 0, pH 1, . . . , pH k, a, b, pH k+1, . . . , pH(4-1)+L2. In a case in which the control object unit positions included in M.sub.L+1 do not reach N.sub.hamilton_min, processing returns to (6). In a case in which the control object unit positions included in M.sub.L+1 reach N.sub.hamilton_min, processing is terminated. In a case in which there is no control object position that can be added with respect to all adjacent control object sets in the Hamilton cycle in M.sub.L, processing proceeds to (11). [0179] (11) Another M.sub.0 than the one selected so far is selected again within S+G. When it is not found in S+G, M.sub.0 at a position where a part is within S+G and does not overlap an obstacle is selected and returned to (2).

[0180] In a case in which M.sub.L including an appropriate Hamilton cycle is found according to [M_Decision], the number of control object units included in M.sub.L is always N.sub.hamilton_min. This is because the process of [M_Decision] is a process of generating a Hamilton cycle by sequentially adding two control object unit positions to M.sub.L starting from M.sub.0 including minimum four control object unit positions. However, in a case in which no appropriate M.sub.L is found according to [M_Decision], that is, in a case in which the number of control object unit positions included in M.sub.L generated according to [M_Decision] is equal to or less than N.sub.hamilton_min, it is possible to generate M.sub.L in which the number of control object unit positions included in M.sub.L is greater than N.sub.hamilton_min through the following additional process. Even in such a case, high-speed heterogeneous transformation can be realized by applying a control object exchange process which will be described later.

[M_Additional_Decision]

[0181] (1) The following (2) and (3) are repeated for M.sub.L generated through [M_Decision]. [0182] (2) The control object units included in M.sub.L are numbered 0, 1, 2, 3, . . . (4-1)+L2 in the order traced by the Hamilton cycle within M.sub.L to be represented as pH0, pH1, pH2, pH3, . . . , pH(4-1)+L2. [0183] (3) Two control object units having adjacent numbers (k and k+1. When k=(41)+L2, ((41)+L2)-th and 0-th) are selected in ascending order, and it is searched whether the two control object units are connected each time selection is performed and there is a path p.sub.k which does not pass through the control object positions included in the current M.sub.L and the position of an obstacle. In a case in which the path p.sub.k is present, n.sub.p positions (p.sub.k1, p.sub.k2, p.sub.k3, p.sub.k4, . . . , p.sub.kn.sub.p) in the path p.sub.k is added to M.sub.L, and the Hamilton cycle of M.sub.L+1 is set to pH 0, pH 1, . . . , pH k, p.sub.k1, p.sub.k2, p.sub.k3, p.sub.k4, . . . , p.sub.kn.sub.p, PH k+1, . . . , pH(41)+L2. In a case in which the number of control object unit positions included in M.sub.L+1 does not exceed N.sub.hamilton_min, processing returns to (2). In a case in which the number of control object unit positions included in M.sub.L+1 exceeds N.sub.hamilton_min, processing is terminated. In a case in which there is no control object position which is not within additional M.sub.L and does not overlap the obstacle position with respect to all adjacent control object sets in the Hamilton cycle in M.sub.L, processing is terminated.

[0184] Each vertex (control object unit) position in the Hamilton cycle in M selected by [M_Decision] and [M_Additional_Decision] is defined as (Hamilton_X[k], Hamilton_Y[k], Hamilton_Z[k]) (k=0, 1, 2, . . . , N.sub.hamilton1). N.sub.hamilton is the number of positions of each vertex (control object unit) of a Hamilton cycle included in M.

[Process of Transformation of SM]

[0185] This transformation process is divided into two processes, i.e., homogeneous transformation from S to Mpre and homogeneous transformation from Mpre to M. In M, the position of the j-th UCMM is defined as P_UCMM[j]=(X_UCMM[j], Y_UCMM[j], Z_UCMM[j]), the position of the j-th LCMM is defined as P_LCMM[j]=(X_LCMM[j], Y_LCMM[j], Z_LCMM[j]). Here, for convenience, numbering is made as follows. P_UCMM[j]=(Hamilton_X[2], Hamilton_Y[2j], Hamilton_Z[2j]), [0186] (i) When A_max=0 [0187] P_LCMM[j]=(Hamilton_X[j]), Hamilton_Y[j], Hamilton_Z[j]) [0188] (ii) When A_max=1 [0189] (ii-i) when 0jN.sub.lcmm2 [0190] P_LCMM[j]=(Hamilton_X[j]), Hamilton_Y[j], Hamilton_Z[j]) [0191] (ii-ii) When jN.sub.lcmm2 [0192] P_LCMM[j]=(Hamilton_X[N.sub.hamilton2+(jN.sub.lcmm+2)], Hamilton_Y[N.sub.hamilton2+(jN.sub.lcmm+2)], Hamilton_Z[N.sub.hamilton2+(jN.sub.lcmm+2)]) [0193] (iii) When A_max=2 [0194] (iii-i) When 0j<N.sub.lcmm2 [0195] P_LCMM[j]=(Hamilton_X[j]), Hamilton_Y[j], Hamilton_Z[j]) [0196] (iii-ii) When jN.sub.lcmm2 [0197] P_LCMM[j]=(Hamilton_X[N.sub.hamilton2+(jN.sub.lcmm+2)], Hamilton_Y[N.sub.hamilton2+(jN.sub.lcmm+2)], Hamilton_Z[N.sub.hamilton2+(jN.sub.lcmm+2)])

[0198] (FIGS. 7 and 8 (in the case of N.sub.hamilton_min=N.sub.hamilton)). As can be ascertained from the above equations and FIGS. 7 and 8, in the case of N.sub.hamilton_min=N.sub.hamilton, the number of control object unit positions in a (blank) Hamilton cycle pH having neither UCMM nor LCMM in M is 2 when A_max=0, 0 when A_max=1, and 1 when A_max=2. In a case in which the number N.sub.hamilton of control object unit positions in the Hamilton cycle pH is greater than N.sub.hamilton_min, N_add0, and when N.sub.hamilton_min+N_add=N.sub.hamilton, the number of control object unit positions in the blank Hamilton cycle pH in M is 2+N_add when A_max=0, N_add when A_max=1, and 1+N_add when A_max=2. The control object unit positions in the blank Hamilton cycle pH in M are between P_LCMM[0] and P_LCMM[N.sub.lcmm1] when A_max=0, and between P_LCMM[N.sub.lcmm2] and P_LCMM[N.sub.lcmm3] when A_max=1 and A_max=2.

[0199] In the case of Mpre, similarly, for the convenience in the process of exchange of M.fwdarw.M which will be described later, 8-square control object positions in Mpre are numbered as P_Mpre[j]=(X_Mpre[j], Y_Mpre[j], Z_Mpre[j]) (j=0, 1, 2, . . . , j_max/21) as follows (FIG. 9). [0200] (i) When A_max=0, [0201] P_Mpre[j]=(Hamilton_X[j], Hamilton_Y[j], Hamilton_Z[j]) [0202] (ii) When A_max=1, [0203] P_Mpre[0]=(Hamilton_X[N.sub.hamilton2], Hamilton_Y[N.sub.hamilton2], Hamilton_Z[N.sub.hamilton2]) [0204] P_Mpre[1]=(Hamilton_X[N.sub.hamilton1], Hamilton_Y[N.sub.hamilton1], Hamilton_Z[N.sub.hamilton1]) [0205] for j2, P_Mpre[j]=(Hamilton_X[j2]), Hamilton_Y[j2], Hamilton_Z[j2]) [0206] (iii) When A_max=2, [0207] P_Mpre[0]=(Hamilton_X[N.sub.hamilton2], Hamilton_Y[N.sub.hamilton2], Hamilton_Z[N.sub.hamilton2]) [0208] P_Mpre[1]=(Hamilton_X[N.sub.hamilton1], Hamilton_Y[N.sub.hamilton1], Hamilton_Z[N.sub.hamilton1]) [0209] for j2, P_Mpre[j]=(Hamilton_X[j2]), Hamilton_Y[j2], Hamilton_Z[j2])

[0210] In homogeneous transformation from S to Mpre, both S and Mpre are composed of the same number of 8-square control objects, and thus transformation can be performed by an existing 8-square homogeneous transformation technique, and therefore the details thereof will be omitted here. An example of an existing 8-square homogeneous transformation technique is the method described in PCT/JP2021/025458.

[0211] Transformation from Mpre to M is performed in the following two processes (1) and (2).

[0212] (1) Each UCMM at a control object unit position from P_Mpre[j_max/21] to P_Mpre[j_max/21j_become_lcmm] is moved to fill a Hamilton cycle position which is blank in Mpre. The value of j_become_lcmm is N.sub.lcmmj_max/21, that is, k_max1 when A_max=0, k_max when A_max=1, and k_max when when A_max=2.

[0213] (2) UCMM at the control object unit position from P_Mpre[N.sub.ucmm1](=P_Mpre[j_max/21j_become_lcmm1]) to P_Mpre[0] is moved to a predetermined UCMM position in M. [0214] Pseudo code is as follows.

[Mpre->M_Transform]

[0215] (1) In j=0 to j_become_lcmm, UCMM at a control object unit position of P_Mpre[j_max/21j] has a target position set to (Hamilton_X[N.sub.hamilton_min3j], (Hamilton_Y[N.sub.hamilton_min3j], (Hamilton_Z[N.sub.hamilton_min3j]) when A_max=0 and 1, and set to (Hamilton_X[N.sub.hamilton_min4j], (Hamilton_Y[N.sub.hamilton_min4j], (Hamilton_Z[N.sub.hamilton_min4j] when A_max=2 to move on LCMMs along the Hamilton cycle pH in a direction in which the number of the position within pH increases until reaching an adjacent position in the Hamilton cycle pH at each target position. Thereafter, it is transformed and moved to LCMM to each target position. The difference of the movement start time between UCMMs at P_Mpre[j_max/21j] and P_Mpre[j_max/21(j+1)] is set to the number of time steps required for P_Mpre[j_max/21j] to be transformed and moved to LCMM.

[0216] (2) In j=0 to N.sub.ucmm1, UCMM at the control object unit position of P_Mpre[N.sub.ucmm1j] has a target position set to P_UCMM[N.sub.ucmm1j]=(Hamilton_x[2(N.sub.ucmm1j)], Hamilton_Y[2(N.sub.ucmm1j)], Hamilton_Z(2[N.sub.ucmm1j]) to move above LCMM, and moves on LCMMs along the Hamilton cycle pH in a direction in which the number of the position in pH increases until reaching each target position. The difference of the movement start time between UCMMs at P_Mpre[N.sub.ucmm1j] and P_Mpre[N.sub.ucmm1(j+1)] is set to the number of time steps required for each UCMM to move on LCMMs.

[Setting of Target Position in Exchange Process]

[0217] The position exchange process in M is performed as follows. A target position of each control object i in M is set to target[i]. Control objects in the LCMM at P_LCMM[j] are defined as i1 [j], i2 [j], i3 [j], and i4 [j] (Rr [i][j]]=Rr[i2 [j]]=Rr[i3 [j]]=Rr[i4 [j]]=j). Control objects in the UCMM at P_UCMM[j] are defined as i5 [j], i6 [j], i7 [j], and i8 [j] (Rr[i5 [j]]=Rr[i6 [j]]=Rr[i7 [j]]=Rr[i8 [j]]=j). Here, the number of the position in the Hamilton cycle pH including the target position target[i] of each control object i is set to target_hamilton[i]. In M, target_hamilton[i]=j when target[i] is within the LCMM at the j-th position in the Hamilton cycle pH, and target_hamilton[i]=j+N.sub.hamilton when within the UCMM. A variable representing an inner position of target[i] in the UCMM or the LCMM including target[i] is defined as target_inner[i], and when target[i] is at the inner position of iX(=i1, i2, i3, 14, 15, 16, 17, 18), target_inner[i]=X. In the present invention, further attention is required to handle the target position of each control object. This because, since M and M do not have the same structure in general, control object units at the positions of P_LCMM[j] and P_UCMM[j] in M are not present at the same positions as those in M in M. Since the control object position exchange process is constituted by exchange of control objects between each UCMM and LCMM, the position in M at which the UCMM or the LCMM at a control object unit position including the target position target[i] of each control object i in M was present must be appropriately managed (strictly speaking, when the process of performing only the operation of moving each UCMM and LCMM to transform them into M without performing only position exchange of control objects in the exchange process is considered, it is necessary to manage positions in pH in M to which the control object units at P_LCMM[j] and P_UCMM[j] in M move). A variable representing the number of the LCMM or the UCMM present at the control object unit position including the target position target[i] of each control object i is defined as target_UCMM_or_LCMM[i], target_UCMM_or_LCMM[i] is set to j when the control object i moves into the LCMM that was present at P_LCMM[i] in M, and target_UCMM_or_LCMM[i] is set to j+N.sub.lcmm when moving to the UCMM at P_UCMM[i] in M. Assuming that the inner position of each control object i in the LCMM or UCMM that is a movement destination is target_inner[i], in M, a variable indicating the inner position in M where the control object at the position of target_inner[i] in M was present is set to target_inner_before[i] (strictly speaking, this means that the control object that was present at target_inner_before[i] in M moves to target_inner[i] in M when the process of performing only the operation of moving each UCMM and LCMM to transform them into M without performing only position exchange of control objects in the exchange process is considered).

[0218] The outline of the position exchange process of the present invention is as follows. Each UCMM moves on LCMMs step by step along the Hamilton cycle pH at the same time in a direction in which the number of the position in pH increases, and if a target position of a control object within each UCMM is present within an LCMM (referred to as an exchange destination LCMM) at a position adjacent to the LCMM (LCMM paired with each UCMM to constitute a 8-square unit) on which each UCMM rides (strictly in other words, if the exchange destination LCMM is the UCMM that was present at P_UCMM[target_UCMM_or_LCMM[i]N.sub.lcmm] and has moved to that position or the LCMM that was present at P_LCMM[target_UCMM_or_LCMM[i] and has moved to that position), the operation of exchanging each control object i to be exchanged with the control object that was at target_inner_before[i] in M among control objects in the exchange destination LCMM is repeated (FIG. 10). In a case in which there is no LCMM at the movement destination position of a UCMM, the UCMM is transformed and moved to an LCMM at a void position of the movement destination (the position of a void at the position next to the position of the UCMM in the Hamilton cycle pH). Then, as the number of UCMMs decreases by one, the LCMM in which the previous position in the Hamilton cycle pH is a void is transformed and moved to a UCMM (it becomes the UCMM in the next position in the Hamilton cycle pH). Although the exchange process is completed after all control objects included in all LCMMs and UCMMs are moved to LCMMs or UCMMs including target positions of the control objects in this manner, to this end, all control object units which were UCMMs in M must be LCMMs once, and it is necessary to trace the positions of all the control object units (all of the control object units which were LCMMs and UCMMs in M) as UCMMs at least once. Similarly, all the control object units which were LCMMs in M must be UCMMs once, and when they have become UCMMs, it is necessary to trace the positions of all the control object units (all of the control object units which were LCMMs and UCMMs in M) at least once.

[0219] That is, before the start of the exchange process, the relationship between the preset values of target_hamilton[i] and target_inner[i] and target_UCMM_or_LCMM[i] and target_inner_before[i] must be accurately calculated in consideration of the operation of the above-described exchange process. Here, M will be described. FIG. 11 shows formation of M when A_max=0. (1) of FIG. 11 shows M (at the start of the exchange process). All of control object units which were UCMMs after the start of the exchange process are converted into LCMMs once (FIG. 11(2)). Thereafter, when all of them are converted into UCMMs again, the exchange process is terminated. The structure at the end of the exchange process is shown in (3), and at the same time, the structure shown in (3) is M. Since all the control object units which were UCMMs in M are converted into LCMMs once during the exchange process, the positions of LCMMs and UCMMs in M have moved to positions shifted by N.sub.ucmm(2+N_add) ahead on the Hamilton cycle pH from the positions in M (naturally, the position of a void has also moved in the same manner.). That is, the positions of each UCMM and each LCMM in M are as follows. [0220] (i) When A_max=0, [0221] (i-i) when (j+N.sub.ucmm(2+N_add))N.sub.hamilton1 [0222] P_LCMM[j]=(Hamilton_X[j+N.sub.ucmm(2+N_add)], [0223] Hamilton_Y[j+N.sub.ucmm(2+N_add)], [0224] Hamilton_Z[j+N.sub.ucmm(2+N_add)]) [0225] (i-ii) when (i+N.sub.ucmm(2+N_add))>N.sub.hamilton1 [0226] P_LCMM[j]=(Hamilton_X[j+N.sub.ucmm(2+N_add)N.sub.hamilton], [0227] Hamilton_Y[j+N.sub.ucmm(2+N_add)N.sub.hamilton], [0228] Hamilton_Z[j+N.sub.ucmm(2+N_add)N.sub.hamilton] [0229] (i-iii) when (2j+N.sub.ucmm(2+N_add))N.sub.hamilton1 [0230] P_UCMM[j]=(Hamilton_X[2j+N.sub.ucmm(2+N_add)], [0231] Hamilton_Y[2j+N.sub.ucmm(2+N_add)], [0232] Hamilton_Z[2j+N.sub.ucmm(2+N_add)]) [0233] (i-iv) when (2j+N.sub.ucmm(2+N_add))>N.sub.hamilton1 [0234] P_UCMM[j]=(Hamilton_X[2j+N.sub.ucmm(2+N_add)N.sub.hamilton], [0235] Hamilton_Y[2j+N.sub.ucmm(2+N_add)N.sub.hamilton], [0236] Hamilton_Z[2j+N.sub.ucmm(2+N_add)N.sub.hamilton]

[0237] Accordingly, [0238] (i) when the target position of a control object i is an LCMM [0239] (i-i) when target_hamilton[i](N.sub.ucmm(2+N_add))0 [0240] target_UCMM_or_LCMM[i]+target_hamilton[i](N.sub.ucmm(2+N_add)) [0241] (i-ii) when target_hamilton[i](N.sub.ucmm(2+N_add))<(2+N_add) target_UCMM_or_LCMM[i] [0242] target_hamilton[i](N.sub.ucmm(2+N_add))+ (2+N_add)+N.sub.lcmm

[0243] FIG. 12 shows M for cases in which A_max=1 and 2. Similarly, since the positions of LCMMs and UCMMs in M have moved to positions shifted by N.sub.ucmm(0+N_add) ahead from the positions in M on the Hamilton cycle pH when A_max=1 and the positions of LCMMs and UCMMs in M have moved to positions shifted by N.sub.ucmm(1+N_add) ahead from the positions in M on the Hamilton cycle pH when A_max=2, [0244] (i) when A_max=1, [0245] (i-i) when 0j<N.sub.lcmm2 and (j+N.sub.ucmm(0+N_add))N.sub.hamilton1 [0246] P_LCMM[j]=(Hamilton_X[j+N.sub.ucmm(0+N_add)], [0247] Hamilton_Y[j+N.sub.ucmm(0+N_add)], [0248] Hamilton_Z[j+N.sub.ucmm(0+N_add)]) [0249] (i-ii) when 0j<N.sub.lcmm2 and (j+N.sub.ucmm(0+N_add))>N.sub.hamilton1 [0250] P_LCMM[j]=(Hamilton_X[j+N.sub.ucmm(0+N_add)N.sub.hamilton], [0251] Hamilton_Y[j+N.sub.ucmm(0+N_add)N.sub.hamilton], [0252] Hamilton_Z[j+N.sub.ucmm(0+N_add)N.sub.hamilton] [0253] (i-iii) when jN.sub.lcmm2 and N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)N.sub.hamilton1 [0254] P_LCMM[j]=(Hamilton_X[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)], [0255] Hamilton_Y[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)], [0256] Hamilton_Z[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)]) [0257] (i-iv) when jN.sub.lcmm2 and N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)>N.sub.hamilton1 [0258] P_LCMM[j]=(Hamilton_X[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)N.sub.hamilton], [0259] Hamilton_Y[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)N.sub.hamilton], [0260] Hamilton_Z[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(0+N_add)N.sub.hamilton] [0261] (i-v) when (2j+N.sub.ucmm(0+N_add))N.sub.hamilton1 [0262] P_UCMM[j]=(Hamilton_X[2j+N.sub.ucmm(0+N_add)], [0263] Hamilton_Y[2j+N.sub.ucmm(0+N_add)], [0264] Hamilton_Z[2j+N.sub.ucmm(0+N_add)]) [0265] (i-vi) when (2j+N.sub.ucmm(0+N_add))>N.sub.hamilton1 [0266] P_UCMM[j]=(Hamilton_X[2j+N.sub.ucmm(0+N_add)N.sub.hamilton], [0267] Hamilton_Y[2j+N.sub.ucmm(0+N_add)N.sub.hamilton], [0268] Hamilton_Z[2j+N.sub.ucmm(0+N_add)N.sub.hamilton] [0269] when A_max=2, [0270] (ii-i) when 0j<N.sub.lcmm2 and (j+N.sub.ucmm(1+N_add))N.sub.hamilton1 [0271] P_LCMM[j]=(Hamilton_X[j+N.sub.ucmm(1+N_add)], [0272] Hamilton_Y[j+N.sub.ucmm(1+N_add)], [0273] Hamilton_Z[j+N.sub.ucmm(1+N_add)]) [0274] (ii-ii) when 0j<N.sub.lcmm2 and (j+N.sub.ucmm(1+N_add))>N.sub.hamilton1 [0275] P_LCMM[j]=(Hamilton_X[j+N.sub.ucmm(1+N_add)N.sub.hamilton], [0276] Hamilton_Y[j+N.sub.ucmm(1+N_add)N.sub.hamilton], [0277] Hamilton_Z[j+N.sub.ucmm(1+N_add)N.sub.hamilton] [0278] (ii-iii) when jN.sub.lcmm2 and (N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)N.sub.hamilton1 [0279] P_LCMM[j]=(Hamilton_X[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)], [0280] Hamilton_Y[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)], [0281] Hamilton_Z[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)]) [0282] (ii-iv) when jN.sub.lcmm2 and (N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)>N.sub.hamilton1 [0283] P_LCMM[j]=(Hamilton_X[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)N.sub.hamilton], [0284] Hamilton_Y[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)N.sub.hamilton], [0285] Hamilton_Z[N.sub.hamilton2+(jN.sub.lcmm+2)+N.sub.ucmm(1+N_add)N.sub.hamilton] [0286] (ii-v) when (2j+N.sub.ucmm(1+N_add))N.sub.hamilton1 [0287] P_UCMM[j]=(Hamilton_X[2j+N.sub.ucmm(1+N_add)], [0288] Hamilton_Y[2j+N.sub.ucmm(1+N_add)], [0289] Hamilton_Z[2j+N.sub.ucmm(1+N_add)]) [0290] (ii-vi) when (2j+N.sub.ucmm(1+N_add))>N.sub.hamilton1 [0291] P_UCMM[j]=(Hamilton_X[2j+N.sub.ucmm(1+N_add)N.sub.hamilton], [0292] Hamilton_Y[2j+N.sub.ucmm(1+N_add)N.sub.hamilton], [0293] Hamilton_Z[2j+N.sub.ucmm(1+N_add)N.sub.hamilton]

[0294] Therefore, [0295] (i) when A_max=1 [0296] (i-i) when target_hamilton[i](N.sub.ucmm(0+N_add))2 [0297] target_UCMM_or_LCMM[i]+target_hamilton[i](N.sub.ucmm(0+N_add))

[0298] As a result of the above processing, when [0299] target_UCMM_or_LCMM[i]<0, [0300] target_UCMM_or_LCMM[i]+target_UCMM_or_LCMM[i]+N.sub.lcmm((i-i) end) [0301] (i-ii) when target_hamilton[i](N.sub.ucmm(0+N_add))<2-(0+N_add) [0302] target_UCMM_or_LCMM[i] [0303] target_hamilton[i](N.sub.ucmm(0+N_add))+ (0+N_add)+N.sub.lcmm [0304] ((i-ii) end) [0305] (ii) When A_max=2 [0306] (ii-i) when target_hamilton[i](N.sub.ucmm(1+N_add))2 [0307] target_UCMM_or_LCMM[i]target_hamilton[i](N.sub.ucmm(1+N_add))

[0308] As a result of the above processing, when [0309] target_UCMM_or_LCMM[i]<0, [0310] target_UCMM_or_LCMM[i]+target_UCMM_or_LCMM[i]+N.sub.lcmm((ii-i) end) [0311] (ii-ii) when target_hamilton[i](N.sub.ucmm(1+N_add))<2(1+N_add) target_UCMM_or_LCMM[i] [0312] target_hamilton[i](N.sub.ucmm(1+N_add))+ (1+N_add)+N.sub.lcmm ((ii-ii end)

[0313] When the target position of the control object i is a UCMM, target_UCMM_or_LCMM[i] for the case of LCMM is calculated first for a value after subtracting N.sub.hamilton from target_hamilton[i], and the value is divided by 2 to add N.sub.lcmm.

[0314] Subsequently, before the relationship between the value of target_inner[i] and the value of target_inner_before[i] is described, the operation of the control object unit used in the exchange process is defined. This is because the inner position of each control object cannot be discussed without the definition.

[0315] FIG. 13 shows an operation when a control object unit when it is a UCMM moves on LCMMs in the direction of a=1 and 3. FIG. 14 shows an operation when a control object unit when it is a UCMM moves on LCMMs in the direction of a=2 and 4 and moves on the LCMMs in the direction of a=5 and 6. If a UCMM at a certain control object unit position moves to an adjacent control object unit position, the position of each control object in the UCMM changes. The way of the change varies depending on the direction of movement. Functions indicating changes in the inner position are defined as fx.sup.+(iX), fx.sup.(iX), fy.sup.+(iX), fy.sup.(iX), fz.sup.+(iX), and fz.sup.(iX). The functions corresponds to operations when a=1, 3, 2, 4, 5, 6.

[0316] Specifically, in the operations shown in FIGS. 13 and 14,

fx.sup.+(i5)=i7

fx.sup.+(i6)=18

fx.sup.+(i7)=15

fx.sup.+(i8)=16

fx.sup.+(iX)=fx.sup.((iX)

fx.sup.+(fx.sup.+(iX))=fx.sup.(fx.sup.(iX))=fx.sup.+(fx.sup.(iX))=fx.sup.(fx.sup.+(iX))=iX

fy.sup.+(i5)=i6

fy.sup.+(i6)=i5

fy.sup.+(i7)=i8

fy.sup.+(i8)=i7

fy.sup.+(iX)=fy.sup.(iX)

fy.sup.+(fy.sup.+(iX))=fy.sup.(fy.sup.(iX))=fy.sup.+(fy.sup.(iX))=fy.sup.(fy.sup.+(iX))=iX

fz.sup.+(i5)=18

fz.sup.+(i6)=17

fz.sup.+(i7)=i6

fz.sup.+(i8)=i5

fz.sup.+(iX)=fz.sup.(iX)

fz.sup.+(fz.sup.+(iX))=fz.sup.(fz.sup.(iX))=fz.sup.+(fz.sup.(iX))=fz.sup.(fz.sup.+(iX))=iX

[0317] The features of the moving operations shown in FIGS. 13 and 14 are as follows.

[0318] (1) The inner position of a control object returns to the same position in the case of even-numbered movements in the same direction.

[0319] (2) The way of changing the inner position is the same with respect to movement in the parallel and opposite direction.

[0320] In addition to the above, the following properties are also provided.

fx.sup.+(fy.sup.+(iX))=fy.sup.+(fx.sup.+(iX))=fz.sup.+(iX)=fz.sup.(iX)

fx.sup.+(fz.sup.+(iX))=fz.sup.+(fx.sup.+(iX))=fy.sup.+(iX)=fy.sup.(iX)

fz.sup.+(fy.sup.+(iX))=fy.sup.+(fz.sup.+(iX))=fx.sup.+(iX)=fx.sup.(iX)

[0321] That is, the following (3) and (4) can be said.

[0322] (3) Inner position changes when movements in different directions are combined one by one are equal to inner position changes at the time of movement in a direction that is not included in the combination.

[0323] (4) Inner position changes when movements in different directions are combined one by one is the same even if the order of movements in a direction of movement included in the combination is changed.

[0324] From the above, the following properties are naturally satisfied.

fx.sup.(fy.sup.(iX))=fy.sup.(fx.sup.(iX))=fz.sup.+(iX)=fz.sup.(iX)

fx.sup.+(fy.sup.(iX))=fy.sup.(fx.sup.+(iX))=fz.sup.+(iX)=fz.sup.(iX)

fx.sup.(fy.sup.+(iX))=fy.sup.+(fx.sup.(iX))=fz.sup.+(iX)=fz.sup.(iX)

fx.sup.(fz.sup.(iX))=fz.sup.(fx.sup.(iX))=fy.sup.+(iX)=fy.sup.(iX)

fx.sup.+(fz.sup.(iX))=fz.sup.(fx.sup.+(iX))=fy.sup.+(iX)=fy.sup.(iX)

fx.sup.(fz.sup.+(iX))=fz.sup.+(fx.sup.(iX))=fy.sup.+(iX)=fy.sup.(iX)

fy.sup.(fz.sup.(iX))=fz.sup.(fy.sup.(iX))=fx.sup.+(iX)=fx.sup.(iX)

fy.sup.+(fz.sup.(iX))=fz.sup.(fy.sup.+(iX))=fx.sup.+(X)=fx.sup.(iX)

fy.sup.(fz.sup.+(iX))=fz.sup.+(fy.sup.(iX))=fx.sup.+(iX)=fx.sup.(iX)

[0325] By utilizing the above properties, for example, after a certain control object unit moves twice in the direction of a=1, moves once in the direction of a=2, moves three times in the direction of a=1, moves four times in the direction of a=6, moves twice in the direction of a=3, and moves three times in the direction of a=4, inner position change of a control object is calculated. The inner position of the control object which was at iX before movement has moved to

fy.sup.(fy.sup.(fy.sup.(fx.sup.(fx.sup.(fz.sup.(fz.sup.(fz.sup.(fz.sup.(fx.sup.+(fx.sup.+(fx.sup.+(fy.sup.+(fx.sup.+(fx.sup.+(iX)))))))))

after movement, and this formula is simplified as follows.

fy.sup.(fy.sup.(fy.sup.(fx.sup.(fx.sup.(fz.sup.(fz.sup.(fz.sup.(fz.sup.(fx.sup.+(fx.sup.+(fx.sup.+(fy.sup.+(fx.sup.+(fx.sup.+(iX)))))))))))))))=fy.sup.+(fy.sup.+(fy.sup.+(fx.sup.+(fx.sup.+(fz.sup.+(fz.sup.+(fz.sup.+(fz.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fy.sup.+(fx.sup.+(fx.sup.+(iX)))))=fy.sup.+(fy.sup.+(fy.sup.+(fy.sup.+(fz.sup.+(fz.sup.+(fz.sup.+(fz.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(iX)))))==fz.sup.+(fz.sup.+(fz.sup.+(fz.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(X)))))))))))=fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(fx.sup.+(iX)))))))=fx.sup.+(iX)

[0326] That is, the way of changing the inner position is determined as follows only by one point of whether movement is performed odd-number times or even-number times in directions parallel to the x-axis, y-axis, and z-axis in a movement route.

[0327] Move even-number times, even-number times, and even-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fX.sub.eveny.sub.evenz.sub.even(iX)=iX

[0328] Move even-number times, even-number times, and odd-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fX.sub.eveny.sub.evenz.sub.odd(iX)=fz.sup.+(iX)

[0329] Move even-number times, odd-number times, and even-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fx.sub.evenfy.sub.oddfz.sub.even(iX)=fy.sup.+(iX)

[0330] Move odd-number times, even-number times, and even-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fX.sub.oddfY.sub.evenfz.sub.even(iX)=fx.sup.+(iX)

[0331] Move even-number times, odd-number times, and odd-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fX.sub.eveny.sub.oddz.sub.odd(iX)=fy.sup.+(fz.sup.+(iX))=fx.sup.+(iX)

[0332] Move odd-number times, odd-number times, and even-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fX.sub.oddfy.sub.oddfz.sub.even(iX)=fx.sup.+(fy.sup.+(iX))=fz.sup.+(iX)

[0333] Move odd-number times, even-number times, and odd-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fx.sub.oddfy.sub.evenfz.sub.odd(iX)=fx.sup.+(fz.sup.+(iX))=fy.sup.+(iX)

[0334] Move odd-number times, odd-number times, and odd-number times in directions parallel to the x-axis, y-axis, and z-axis, respectively.

fX.sub.oddfy.sub.oddfz.sub.odd(iX)=fx.sup.+(fy.sup.+(fz.sup.+(iX)))=fz.sup.+(fz.sup.+(iX))=iX

[0335] In the present invention, the number of control object unit positions within the Hamilton cycle pH is an even number. If a UCMM is returned to the original position after one round of pH, it is easily derived from the above formulas that change in the inner position is the same as the position before round of pH. That is, since pH is a cycle, the numbers of times of movement in the positive and negative directions are identical in movements parallel to the x, y and z axes, and the numbers of times of movement in directions parallel to the x, y and z axes are all even numbers.

[0336] Subsequently, functions representing inner position changes when an LCMM moves to the position of an adjacent LCMM in the directions of a=1, 3, 2, 4, 5, 6 to become a UCMM are defined as fx.sup.+.sub.enter (iX), fx.sup..sub.enter (iX), fy.sup.+.sub.enter (iX), fy.sup..sub.enter (iX), fz.sup.+.sub.enter (iX), and fz.sup..sub.enter (iX), and functions representing inner position changes when a UCMM moves to the position of an adjacent void in the directions of a=1, 3, 2, 4, 5, 6 to become an LCMM are defined as fx.sup.+.sub.extract (iX), fx.sup..sub.extract (iX), fy.sup.+.sub.extract (iX), fy.sup..sub.extract (iX), fz.sup.+.sub.extract (iX), and fz.sup..sub.extract (iX). FIG. 15 shows operations in the case where an LCMM moves to the position of an adjacent LCMM in the direction of a=3 to become a UCMM and in the opposite case. In addition, FIG. 16 shows operations in the case where an LCMM moves to the position of an adjacent LCMM in the direction of a=1 to become a UCMM and in the opposite case. From FIGS. 15 and 16,

fx.sup.+.sub.enter(i1)=i5

fx.sup.+.sub.enter(i2)=i8

fx.sup.+.sub.enter(i3)=i6

fx.sup.+.sub.enter(i4)=i7

fx.sup..sub.enter(i1)=i7

fx.sup..sub.enter(i2)=i8

fx.sup..sub.enter(i3)=i5

fx.sup..sub.enter(i4)=i6

fx.sup.+.sub.extract(i5)=i3

fx.sup.+.sub.extract(i6)=i4

fx.sup.+.sub.extract(i7)=i1

fx.sup.+.sub.extract(i8)=i2

fx.sup..sub.extract(i5)=i1

fx.sup..sub.extract(i6)=i3

fx.sup..sub.extract(i7)=i4

fx.sup..sub.extract(i8)=i2

[0337] With respect to other directions, the following can be obtained by interpreting the directions of movement shown in FIGS. 15 and 16 with respect to the respective axes.

fy.sup.+.sub.enter(i1)=i8

fy.sup.+.sub.enter(i2)=i7

fy.sup.+.sub.enter(i3)=i6

fy.sup.+.sub.enter(i4)=i5

fy.sup..sub.enter(i1)=i8

fy.sup..sub.enter(i2)=i6

fy.sup..sub.enter(i3)=i5

f.sup..sub.enter(i4)=i7

fy.sup..sub.enter(i5)=i3

fy.sup.+.sub.extract(i6)=i2

fy.sup.+.sub.extract(i7)=i4

fy.sup.+.sub.extract(i8)=i1

fy.sup..sub.extract(i5)=i4

fy.sup..sub.extract(i6)=i3

fy.sup..sub.extract(i7)=i2

fy.sup..sub.extract(i8)=i1

fz.sup.+.sub.enter(i1)=i5

fz.sup.+.sub.enter(i2)=i7

fz.sup.+.sub.enter(i3)=i8

fz.sup.+.sub.enter(i4)=i6

fz.sup..sub.enter(i1)=i7

fz.sup..sub.enter(i2)=i6

fz.sup..sub.enter(i3)=i8

fz.sup..sub.enter(i4)=i5

fz.sup.+.sub.extract(i5)=i4

fz.sup.+.sub.extract(i6)=i2

fz.sup.+.sub.extract(i7)=i1

fz.sup.+.sub.extract(i8)=i3

fz.sup..sub.extract(i5)=i1

fz.sup..sub.extract(i6)=i4

fz.sup..sub.extract(i7)=i2

fz.sup..sub.extract(i8)=i3

[0338] As a matter of course, the following relationships are established.

fx.sup..sub.enter(fx.sup.+.sub.extract(iX))=fx.sup.+.sub.extract(fx.sup..sub.enter(iX))=iX

fx.sup.+.sub.enter(fX.sup..sub.extract(iX))=fx.sup..sub.extract(fx.sup.+.sub.enter(iX))=iX

fy.sup..sub.enter(fy.sup.+.sub.extract(iX))=fy.sup.+.sub.extract(fy.sup..sub.enter(iX))=iX

fy.sup.+.sub.enter(fy.sup..sub.extract(iX))=fy.sup..sub.extract(fy.sup.+.sub.enter(iX))=iX

fz.sup.+.sub.enter(fz.sup.+.sub.extract(iX))=fz.sup.+.sub.extract(fz.sup..sub.enter(iX))=iX

fz.sup.+.sub.enter(fz.sup..sub.extract(iX))=fz.sup..sub.extract(fz.sup.+.sub.enter(iX))=iX

[0339] By using the above functions, a relational expression between the value of target_inner[i] and the value of target_inner_before[i] can be obtained as will be described below.

[0340] When a control object unit including the target position of the control object i is an LCMM in M (target_UCMM_or_LCMM[i]<N).sub.lcmm, the first operation in the exchange process of the control object unit target_UCMM_or_LCMM[i] that is an LCMM in M is conversion into a UMCC, and then the UMCC moves by N.sub.hamilton+(N.sub.ucmm(2+N_add)2) steps when A_max=0, moves by N.sub.hamilton+N.sub.ucmm(0+N_add)2 steps when A_max=1, and moves by N.sub.hamilton+N.sub.ucmm(1+N_add)2 steps when A_max=2 on pH (the number of movements described here is obtained by subtracting one step from the number of steps of each movement for conversion into UCMM and re-conversion into LCMM although the control object unit that is an LCMM in M moves one round of pH during the exchange process and additionally moves by (N.sub.ucmm(2+N_add)2) steps when A_max=0, moves by N.sub.ucmm(0+N_add)2 steps when A_max=1, and moves by N.sub.ucmm(1+N_add)2 steps when Z_max=2.). Thereafter, it is finally converted into the LCMM. That is, if even/odd of the number of times of movement in the direction of movement at the time of the first conversion into the UCMM, the direction of movement at the time of the last re-conversion into the LCMM, and directions parallel to the x, y, and z-axes at the time of movement as the UCMM is determined, change in the inner position of the control object included in the control object unit target_UCMM_or_LCMM[i] between N and M can be calculated. Code for calculating the value of target_inner_before[i] when the control object unit including the target position of the control object i is an LCMM in M is [LCMM_inner_transform(i)] which is illustrated below.

[LCMM_inner_transform(i)]

[0341] (1) When the direction of movement to the next position P_start at the time of moving by tracing pH of an LCMM at the position of P_LCMM[target_UCMM_or_LCMM[i] in M is defined as a_start,

when a_start=1,f.sub.enter(iX)fx.sup.+.sub.enter(iX)

when a_start=2,f.sub.enter(iX)fy.sup.+.sub.enter(iX)

when a_start=3,f.sub.enter(iX)fx.sup..sub.enter(iX)

when a_start=4,f.sub.enter(iX)fy.sup..sub.enter(iX)

when a start=5,f.sub.enter(iX)fz.sup.+.sub.enter(iX)

when a_start=6,f.sub.enter(iX)fz.sup..sub.enter(iX)

are defined.

[0342] (2) When the reverse direction of the direction of movement to the next position P_end at the time of moving by tracing pH of an LCMM at the position of P_LCMM[target_UCMM_or_LCMM[i] in M in the reverse direction is defined as a_start,

when a_end=1,f.sub.extract(iX)fx.sup.+.sub.extract(iX)

when a_end=2,f.sub.extract(iX)fy.sup.+.sub.extract(iX)

when a_end=3,f.sub.extract(iX)fx.sup..sub.extract(iX)

when a_end=4,f.sub.extract(iX)fy.sup..sub.extract(iX)

when a_end=5,f.sub.extract(iX)fz.sup.+.sub.extract(iX)

when a_end=6,f.sub.extract(iX)fz.sup..sub.extract(iX)

are defined.

[0343] (3) When a function representing change in the inner position of a control object in a UCMM when the UCMM moves along the Hamilton cycle pH from P_start to P_end is defined as f.sub.mov(iX), and the numbers of times of movement in directions parallel to the x, y and z-axes are set to nx, ny, and nz, when nx, ny, and nz are an even number, an even number, and an even number, respectively,

f.sub.mov(iX)fX.sub.eveny.sub.evenz.sub.even(iX)=ix

when nx, ny, and nz are an even number, an even number, and an odd number, respectively,

f.sub.mov(iX)fX.sub.eveny.sub.evenz.sub.odd(iX)=fz.sup.+(iX)

when nx, ny, and nz are an even number, an odd number, and an even number, respectively,

f.sub.mov(iX)fx.sub.evenfy.sub.oddfz.sub.even(iX)=fy.sup.+(iX)

when nx, ny, and nz are an odd number, an even number, and an even number, respectively,

f.sub.mov(iX)+fz.sub.oddfy.sub.evenfz.sub.even(iX)=fx.sup.+(iX)

when nx, ny, and nz are an even number, an odd number, and an odd number, respectively,

f.sub.mov(iX)fx.sub.eveny.sub.oddz.sub.odd(iX)=fx.sup.+(iX)

when nx, ny, and nz are an odd number, an odd number, and an even number, respectively,

f.sub.mov(iX)fx.sub.oddfy.sub.oddfz.sub.even(iX)=fz.sup.+(iX)

when nx, ny, and nz are an odd number, an even number, and an odd number, respectively,

f.sub.mov(iX)fX.sub.oddfy.sub.evenfz.sub.odd(iX)=fy.sup.+(iX)

when nx, ny, and nz are an odd number, an odd number, and an odd number, respectively,

f.sub.mov(iX)fX.sub.oddfy.sub.oddfz.sub.odd(iX)=iX

are defined.

[0344] (4) When a function representing change in the inner position of a control object within the control object unit target_UCMM_or_LCMM[i] is defined as f.sub.perm_lcmm(iX) in the exchange process,

f.sub.perm_lcmm(iX)=f.sub.extract(f.sub.mov(f.sub.enter(iX)))

is provided.

When f.sub.perm_lcmm(iX)=target_inner[i],target_inner_before[i]iX

[0345] When the control object unit including the target position of the control object i is a UCMM in M (target_UCMM_or_LCMM[i]>N.sub.lcmm1), the first operation in the exchange process of the control object unit target_UCMM_or_LCMM[i] in M is movement on pH to a place where the UMCC is to be converted into an LCMM, and then the UMCC is converted into the LCMM. The number of steps of movement on pH to the place where the UCMM is to be converted to the LCMM is 3*(N.sub.ucmm1j)+1 when A_max=0, 3*(N.sub.ucmm1j)+1 when A_max=1, and 3*(N.sub.ucmm1j) when A_max=2 in the j-th UCMM. After converted into the LCMM, the LCMM stops for a while and re-converted into the UCMM. After re-conversion into the UCMM, the UCMM moves by N.sub.hamilton+ (N.sub.ucmm(2+N_add))(3*(N.sub.ucmm1j)+1)-2 steps when A_max=0, moves by N.sub.hamilton+N.sub.ucmm(0+N_add)(3*(N.sub.ucmm1j)+1)-2 steps when A_max=1, and moves by N.sub.hamilton+N.sub.ucmm(1+N_add)(3*(N.sub.ucmm1j))2 when A_max=2 on pH.

[0346] That is, if even/odd of the number of times of movement in the directions parallel to the x, y and z-axes at the time of moving as the UCMM before the first conversion into the LCMM, even/odd of the number of times of movement in the directions parallel to the x, y and z-axes at the time of moving as the UCMM after re-conversion into the UCMM, the direction of movement at the time of the first conversion into the LCMM, and the direction of movement at the time of re-conversion into the UCMM are determined, change in the inner position of a control object included in the control object unit target_UCMM_or_LCMM[i] between M and M can be calculated. Code for calculating the value of target_inner_before[i] when the control object unit including the target position of the control object i is a UCMM in M is [UCMM_inner_transform(i)] illustrated below.

[UCMM_inner_transform(i)]

[0347] (1) It is assumed that pre_move=3*(N.sub.ucmm1j)+1 when A_max=0, 1 and pre_move=3*(N.sub.ucmm1j) when A_max=2. When a function representing change in the inner position of the control object within the UCMM when it has moved by pre_move step along the Hamilton cycle pH to a position immediately before the UCMM is converted into an LCMM from P_UCMM[target_UCMM_or_LCMM[i]N.sub.lcmm] when 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move<N.sub.hamilton (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move]) when 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton]) is defined as f.sub.mov_pre(iX), and the numbers of times of movement in the directions parallel to the x, y and z-axes are set to nx, ny, and nz,

when nx, ny, and nz are an even number, an even number, and an even number, respectively,

f.sub.mov_pre(iX)fX.sub.eveny.sub.evenz.sub.even(iX)=ix

when nx, ny, and nz are an even number, an even number, and an odd number, respectively,

f.sub.mov_pre(iX)+fX.sub.eveny.sub.evenz.sub.odd(iX)=fz.sup.+(iX)

when nx, ny, and nz are an even number, an odd number, and an even number, respectively,

f.sub.mov_pre(iX)+fX.sub.evenfy.sub.oddfz.sub.even(iX)=fy.sup.+(iX)

when nx, ny, and nz are an odd number, an even number, and an even number, respectively,

f.sub.mov_pre(iX)+fx.sub.oddfy.sub.evenfz.sub.even(iX)=fx.sup.+(iX)

when nx, ny, and nz are an even number, an odd number, and an odd number, respectively,

f.sub.mov_pre(iX)fx.sub.eveny.sub.oddz.sub.odd(iX)=fx.sup.+(iX)

when nx, ny, and nz are an odd number, an odd number, and an even number, respectively,

f.sub.mov_pre(iX)fx.sub.oddfy.sub.oddfz.sub.even(iX)=fz.sup.+(iX)

when nx, ny, and nz are an odd number, an even number, and an odd number, respectively,

f.sub.mov_pre(iX)fX.sub.oddfy.sub.evenfz.sub.odd(iX)=fy.sup.+(iX)

when nx, ny, and nz are an odd number, an odd number, and an odd number, respectively,

f.sub.mov_pre(iX)fx.sub.oddfy.sub.oddfz.sub.odd(iX)=ix

are defined.

[0348] (2) when 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move<N.sub.hamilton (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move]) when 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_moveN.sub.hamilton]) When the direction of movement to the next position P_start when the UCMM at the position above has moved by tracing pH is defined as a_start,

when a start=1,f.sub.extract(X)fx.sup.+.sub.extract(iX)

when a start=2,f.sub.extract(iX)fy.sup.+.sub.extract(iX)

when a_start=3,f.sub.extract(iX)fx.sup..sub.extract(iX)

when a_start=4,f.sub.extract(iX)+fy.sup..sub.extract(iX)

when a_start=5,f.sub.extract(iX)fz.sup.+.sub.extract(iX)

when a_start=6,f.sub.extract(iX)fz.sup..sub.extract(iX)

are defined.

[0349] (3) When 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1<N.sub.hamilton (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1]) When 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1N.sub.hamilton (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1-N.sub.hamilton], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1N.sub.hamilton], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+1N.sub.hamilton])

[0350] When the direction of movement to the next position P_end when the LCMM at the position above has moved by tracing pH is defined as a_end,

when a_end=1,f.sub.enter(iX)fx.sup.+.sub.enter(iX)

when a_end=2,f.sub.enter(iX)fy.sup.+.sub.enter(iX)

when a_end=3,f.sub.enter(iX)fx.sup..sub.enter(iX)

when a_end=4,f.sub.enter(iX)fy.sup..sub.enter(iX)

when a_end=5,f.sub.enter(iX)fz.sup.+.sub.enter(iX)

when a_end=6,f.sub.enter(iX)fz.sup..sub.enter(iX)

are defined.

[0351] (4) On the assumption that, when A_max=0,

post_moveN.sub.hamilton+(N.sub.ucmm(2+N_add))(3*(N.sub.ucmm1j)+1)2 when A_max=1,

post_moveN.sub.hamilton+N.sub.ucmm(0+N_add)(3*(N.sub.ucmm1j)+1)2 when A_max=2,

post_moveN.sub.hamilton+N.sub.ucmm(1+N_add)(3*(N.sub.ucmm1j))2,

when a function representing change in the inner position of the control object within the UCMM when the UCMM has moved by post_move step along the Hamilton cycle pH from the position defined as, when 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+2<N.sub.hamilton, (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+2], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+2], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+2]) When 2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move2N.sub.hamilton (Hamilton_X[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+2N.sub.hamilton], Hamilton_Y[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+2N.sub.hamilton], Hamilton_Z[2(target_UCMM_or_LCMM[i]N.sub.lcmm)+pre_move+2N.sub.hamilton]), [0352] to P_UCMM[target_UCMM_or_LCMM[i]N.sub.lcmm] is defined as f.sub.mov_post(iX), and the numbers of times of movement in the directions parallel to the x, y and z-axes are set to nx, ny, and nz,
when nx, ny, and nz are an even number, an even number, and an even number, respectively,

f.sub.mov_post(iX)fx.sub.eveny.sub.evenz.sub.even(iX)=ix

when nx, ny, and nz are an even number, an even number, and an odd number, respectively,

f.sub.mov_post(iX)fz.sub.eveny.sub.evenz.sub.odd(iX)=fz.sup.+(iX)

when nx, ny, and nz are an even number, an odd number, and an even number, respectively,

f.sub.mov_post(iX)+fX.sub.evenfy.sub.oddfz.sub.even(iX)=fy.sup.+(iX)

when nx, ny, and nz are an odd number, an even number, and an even number, respectively,

f.sub.mov_post(iX)fz.sub.oddfy.sub.evenfz.sub.even(iX)=fx.sup.+(iX)

when nx, ny, and nz are an even number, an odd number, and an odd number, respectively,

f.sub.mov_post(iX)fx.sub.eveny.sub.oddz.sub.odd(iX)=fx.sup.+(iX)

when nx, ny, and nz are an odd number, an odd number, and an even number, respectively,

f.sub.mov_post(iX)fx.sub.oddfy.sub.oddfz.sub.even(iX)=fz.sup.+(iX)

when nx, ny, and nz are an odd number, an even number, and an odd number, respectively,

f.sub.mov_post(iX)fx.sub.oddfy.sub.evenfz.sub.odd(iX)=fy.sup.+(iX)

when nx, ny, and nz are an odd number, an odd number, and an odd number, respectively,

f.sub.mov_post(iX)fx.sub.oddfy.sub.oddfz.sub.odd(iX)=ix

are defined.

[0353] (5) When a function representing change in the inner position of the control object within the control object unit target_UCMM_or_LCMM[i] in the exchange process is defined as f.sub.perm_ucmm(iX),

f.sub.perm_ucmm(iX)=f.sub.mov_post(f.sub.enter(f.sub.extract(f.sub.mov_pre(iX))))

is provided.

[0354] When f.sub.perm_ucmm(iX)=target_inner[i], target_inner_before[i]-ix.

[0355] As a result, the algorithm of setting an exchange target position is as follows.

[Predict_Inner_Transform]

[0356] (1) The following calculation is performed for all control objects i.

[0357] When a control object unit including a target position of a control object i is an LCMM, [0358] (i) when A_max=0 [0359] (i-i) when target_hamilton[i](N.sub.ucmm(2+N_add))0 [0360] target_UCMM_or_LCMM[i]+target_hamilton[i](N.sub.ucmm(2+N_add)) [0361] (i-ii) target_hamilton[i](N.sub.ucmm(2+N_add))<(2+N_add) target_UCMM_or_LCMM[i] [0362] target_hamilton[i](N.sub.ucmm(2+N_add))+ (2+N_add)+N.sub.lcmm [0363] (ii) When A_max=1 [0364] (ii-i) when target_hamilton[i](N.sub.ucmm(0+N_add))2 target_UCMM_or_LCMM[i]+target_hamilton[i](N.sub.ucmm(0+N_add)) [0365] when target_UCMM_or_LCMM[i]<0, [0366] target_UCMM_or_LCMM[i]+target_UCMM_or_LCMM[i]+N.sub.lcmm((ii-i) end) [0367] (ii-ii) when target_hamilton[i](N.sub.ucmm(0+N_add))<2-(0+N_add) [0368] target_UCMM_or_LCMM[i] [0369] target_hamilton[i](N.sub.ucmm(0+N_add))+ (0+N_add)+N.sub.lcmm [0370] ((ii-ii end) [0371] (iii) when A_max=2 [0372] (iii-i) target_hamilton[i](N.sub.ucmm(1+N_add))2 [0373] when target_UCMM_or_LCMM[i]+target_hamilton[i](N.sub.ucmm(1+N_add)) target_UCMM_or_LCMM[i]<0, [0374] target_UCMM_or_LCMM[i]+target_UCMM_or_LCMM[i]+N.sub.lcmm ((iii-i) end) [0375] (iii-ii) when target_hamilton[i](N.sub.ucmm(1+N_add))<2(1+N_add) [0376] target_UCMM_or_LCMM[i] [0377] target_hamilton[i](N.sub.ucmm(1+N_add))+ (1+N_add)+N.sub.lcmm ((iii-ii) end)

[0378] When a control object unit including a target position of the control object i is a UCMM, target_UCMM_or_LCMM when the control object unit including the target position of the control object i is an LCMM is calculated, and target_UCMM_or_LCMM[i]-target_UCMM_or_LCMM[i]/2+N.sub.lcmm is defined.

[0379] (2) For all the control objects i, (2-1) UCMM_inner_transform(i) is executed when target_UCMM_or_LCMM[i]N.sub.lcmm, and (2-2) LCMM_inner_transform(i) is executed when target_UCMM_or_LCMM[i]<N.sub.lcmm.

[Position Exchange Process at Intermediate Position M]

[0380] FIGS. 17 to 27 show operations of the exchange process in the case of each value of A_max. The operations are mainly performed by UCMMs in the exchange process. UCMMs simultaneously move on LCMMs along the Hamilton cycle pH. The operations shown in FIGS. 17, 18 and 19 shows a process in which one UCMM having no LCMM at a control object unit position that is a movement destination thereof is converted into an LCMM, and one LCMM is converted into a UCMM such that no LCMM is present and a void is present at the previous position from that position in the Hamilton cycle pH in the case of A_max=0 (when N.sub.hamilton=N.sub.hamilton_min). By repeating the operations shown in FIGS. 17, 18 and 19 N.sub.ucmm times, conversion of all UCMMs into LCMMs is completed. Then, by further repeating the operations N.sub.lcmm-N.sub.ucmm times, conversion of all the LCMMs into UCMMs is terminated. Thereafter, by further repeating the operations N.sub.ucmm times, re-conversion of all the UCMMs into UCMMs is completed and the exchange process is terminated.

[0381] Similarly, the operations shown in FIGS. 20, 21 and 22 shows a process in which one UCMM having no LCMM at a control object unit position that is a movement destination thereof is converted into an LCMM, and one LCMM is converted into a UCMM such that no LCMM is present and a void is present at the previous position from that position in the Hamilton cycle pH in the case of A_max=1 (when N.sub.hamilton=N.sub.hamilton_min). By repeating the operations shown in FIGS. 20, 21, and 22 N.sub.ucmm times, conversion of all UCMMs into LCMMs is completed. Then, by further repeating the operations N.sub.lcmm-N.sub.ucmm times, conversion of all the LCMMs into UCMMs is terminated. Thereafter, by further repeating the operations N.sub.ucmm times, re-conversion of all the UCMMs into UCMMs is completed and the exchange process is terminated.

[0382] Similarly, the operations shown in FIGS. 23, 24, 25, 26, and 27 shows a process in which one UCMM having no LCMM at a control object unit position that is a movement destination thereof is converted into an LCMM, and one LCMM is converted into a UCMM such that no LCMM is present and a void is present at the previous position from that position in the Hamilton cycle pH in the case of A_max=2 (when N.sub.hamilton=N.sub.hamilton_min). By repeating the operations shown in FIGS. 23, 24, 25, 26, and 27 N.sub.ucmm times, conversion of all UCMMs into LCMMs is completed. Then, by further repeating the operations N.sub.lcmm-N.sub.ucmm times, conversion of all the LCMMs into UCMMs is terminated.

[0383] Thereafter, by further repeating the operations N.sub.ucmm times, re-conversion of all the UCMMs into UCMMs is completed and the exchange process is terminated.

[0384] During such an exchange process, while all control object units are converted into UCMMs and moves, the control objects included therein are moved into control objects (which have been converted into LCMMs at that time) including target positions thereof. In addition, all the control object units pass their positions through all other control object units converted into UCMMs while they are converted into LCMMs.

[0385] In the exchange process, the exchange operation of the position of each control object is executed only when the exchange operation of a control object is not executed in the adjacent UCMM in principle. That is, in the operation steps shown in FIGS. 17 to 27, at most two steps are required for all the UCMMs to complete the control object exchange operation at the positions thereof. The exception is (5) when A_max=0, (8) when A_max=1, and (8) when A_max=2. The reason why these operations are exceptional is that, although each UCMM normally exchanges the control object with an LCMM at the previous position from the control object unit position thereof in the Hamilton cycle pH, the control object unit converted into a UCMM at the latest time performs exchange of the control object with the LCMM at the previous position from the control object unit position in the Hamilton cycle pH in such an operation, and thus a control object is not connected even if an adjacent UCMM performs the control object exchange operation. Hereinafter, pseudo code of the exchange process at each value of A_max will be described.

[Permutation_M_M_A_max 0]

[0386] (1) The control object currently converted into a UCMM is defined as UCMM_NOW[j] (j=0, 1, 2, . . . , 2k_max1). It is assumed that j=0 for a control object which is converted into a UCMM at a position where it can reach a void position in the advancing direction with the smallest number of movement steps, and the value of j increases as the number of movement steps required to reach the void position in the advancing direction increases.

[0387] (2) (3) to (11) below are repeated N.sub.lcmm+N.sub.ucmm times.

[0388] (3) In each UCMM_NOW[j] where j is an even number, an exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCCM at the next position from each position in the Hamilton cycle pH and each UCCM_NOW[j] where j is an even number. At the same time, in each UCMM_NOW[j] where j is an odd number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation

[0389] Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number only in a case in which the actual exchange operation is not necessary (FIG. 17(1)).

[0390] (4) In each UCMM_NOW[j] where j is an odd-number, in a UCMM_NOW[j] in which the exchange operation is not executed in (3), the exchange operation

[0391] Position_Exchange_Fore(UCMM_NOW[j]) is executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number (FIG. 17(2)).

[0392] (5) All UCMMs are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 17(3)).

[0393] (6) In each UCMM_NOW (j) where j is an odd number, the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number. At the same time, in each UCMM_NOW[j] where j>0 and j is an even number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number only in a case in which the actual exchange operation is not necessary. In Position_Exchange_Fore( ) in UCMM_NOW[2k_max1], Position_Exchange_Aft( ) in UCMM_NOW[2k_max1] is executed only in a case in which there is no actual exchange operation (FIG. 18(4)).

[0394] (7) UCMM_NOW[0] is converted into an LCMM. At the same time, in each UCMM_NOW[j] where j>0 and j is an even-number, in UCMM_NOW[j] in which the exchange operation is not performed in (6), the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number. In a case in which Position_Exchange_Aft( ) in UCMM_NOW[2k_max1] is not executed in (6), Position_Exchange_Aft( ) in UCMM_NOW[2k_max1] is executed. UCMM_NOW[j]+UCMM_NOW[j+1] is set. UCMM_NOW[2k_max1] is set as a missing number (FIG. 18(5)).

[0395] (8) All UCMMs are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 18(6)).

[0396] (9) An LCMM at a position requiring the largest number of movement steps to reach a void position in the advancing direction along the Hamilton cycle pH is converted into a UCMM and set as UCMM_NOW[2k_max1]. At the same time, in each UCMM_NOW[j] where j is an even number, the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number. At the same time, in each UCMM_NOW[j] where j<2k_max1 and j is an odd number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number only in a case in which the actual exchange operation is not necessary (FIG. 18(7)).

[0397] (10) In each UCMM_NOW[j] where j<2k_max1 and j is an odd number, in UCMM_NOW[j] in which the exchange operation is not performed in (9), the exchange operation

[0398] Position_Exchange_Fore(UCMM_NOW[j]) is executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number (FIG. 19(8)).

[0399] (11) All UCMMs with j<2k_max1 are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 19(9)).

[Permutation_M_M_A_max_1]

[0400] (1) The control object currently converted into a UCMM is defined as UCMM_NOW[j] (j=0, 1, 2, . . . 2k_max1). It is assumed that j=0 for a control object which is converted into a UCMM at a position where it can reach the position of P_LCMM[N.sub.lcmm4] with the smallest number of movement steps through movement in the forward direction along pH, and the value of j increases as the number of movement steps required to reach the position of P_LCMM[N.sub.lcmm2] through movement in the forward direction along pH increases. The position of Position_Become_LCMMP_LCMM[N.sub.lcmm2] is set.

[0401] (2) (3) to (11) below are repeated N.sub.lcmm+N.sub.ucmm times.

[0402] (3) The LCMM at the position of Position_Become_LCMM is converted into a UCMM, and set as UCMM_NOW[2k_max]. The position of Position_Become_LCMM is shifted to the next position in the Hamilton cycle pH in the forward direction. In each UCMM_NOW[j] where j is an odd number, the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number. At the same time, in each UCMM_NOW[j] where j<2k_max and j is an even number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number only in a case in which the actual exchange operation is not necessary (FIG. 20(1)).

[0403] (4) In each UCMM_NOW[j] where j<2k_max and j is an even number, in a UCMM_NOW[j] in which the exchange operation is not executed in (3), the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number (FIG. 20(2)).

[0404] (5) All UCMMs with j<2k_max are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 20(3)).

[0405] (6) UCMM_NOW[0] is converted into an LCMM. In each UCMM_NOW (j) where j>0 and j is an even number, the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number. At the same time, in each UCMM_NOW[j] where j is an odd number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation

[0406] Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number only in a case in which the actual exchange operation is not necessary (FIG. 21(4)).

[0407] (7) In each UCMM_NOW[j] where j is an odd-number, in UCMM_NOW[j] in which the exchange operation is not performed in (6), the exchange operation

[0408] Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number. UCMM_NOW[j]-UCMM_NOW[j+1] is set. UCMM_NOW[2k_max] is set as a missing number (FIG. 21(5)).

[0409] (8) All UCMMs are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 21(6)).

[0410] (9) In each UCMM_NOW[j] where j is an odd number, the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number. At the same time, in each UCMM_NOW[j] where j is an even number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number only in a case in which the actual exchange operation is not necessary. At the same time, in Position_Exchange_Fore( ) in UCMM_NOW[2k_max1], Position_Exchange_Aft( ) in UCMM_NOW[2k_max1] is executed only in a case in which no actual exchange operation is performed (FIG. 21(7)).

[0411] (10) In each UCMM_NOW[j] where j is an even number, in UCMM_NOW[j] in which the exchange operation is not performed in (9), the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number. At the same time, only in a case in which Position_Exchange_Aft( ) in UCMM_NOW[2k_max1] is not executed in (9), Position_Exchange_Aft( ) in UCMM_NOW[2k_max1] is executed (FIG. 22(8)).

[0412] (11) All UCMMs are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 22(9)).

[Permutation_M_M_A_max 2]

[0413] (1) The control object currently converted into a UCMM is defined as UCMM_NOW[j] (j=0, 1, 2, . . . , 2k_max). It is assumed that j=0 for a control object which is converted into a UCMM at a position where it can reach the position of P_LCMM[N.sub.lcmm2] with the smallest number of movement steps through movement in the forward direction along pH, and the value of j increases as the number of movement steps required to reach the position of P_LCMM[N.sub.lcmm2] increases. The position of Position_Become_LCMMP_LCMM[N.sub.lcmm2] is set.

[0414] (2) (3) to (11) below are repeated N.sub.lcmm+N.sub.ucmm times.

[0415] (3) The LCMM at the position of Position_Become_LCMM is converted into a UCMM, and set as UCMM_NOW[2k_max+1]. The position of Position_Become_LCMM is shifted to the next position in the Hamilton cycle pH in the forward direction. The UCMM_NOW[0] is converted into an LCMM. In each UCMM_NOW (j) where j>0 and j is an even number, the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an even number.

[0416] At the same time, in each UCMM_NOW[j] where j<2k_max+1 and j is an odd number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number only in a case in which the actual exchange operation is not necessary (FIG. 23(1)).

[0417] (4) In each UCMM_NOW[j] where j<2k_max+1 and j is an odd number, in a UCMM_NOW[j] in which the exchange operation is not executed in (3), the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number. UCMM_NOW[j]+UCMM_NOW[j+1] is set. UCMM_NOW[2k_max+1] is set as a missing number (FIG. 24(2)).

[0418] (5) All UCMMs with j<2k_max are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 24(3)).

[0419] (6) In each UCMM_NOW[j] where j is an even number, an exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCCM at the next position from each position in the Hamilton cycle pH and each UCCM_NOW[j] where j is an even number. At the same time, in each UCMM_NOW[j] where j is an odd number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number only in a case in which the actual exchange operation is not necessary (FIG. 25(4)).

[0420] (7) In each UCMM_NOW[j] where j is an odd-number, in UCMM_NOW[j] in which the exchange operation is not performed in (6), the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number (FIG. 25(5)).

[0421] (8) All UCMMs are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 26(6)).

[0422] (9) In each UCMM_NOW[j] where j is an even number, an exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCCM at the next position from each position in the Hamilton cycle pH and each UCCM_NOW[j] where j is an even number. At the same time, in each UCMM_NOW[j] where j is an odd number, in Position_Exchange_Fore( ) in both UCMM_NOW[j1] and UCMM_NOW[j+1], the exchange operation Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number only in a case in which the actual exchange operation is not necessary. At the same time, in Position_Exchange_Fore( ) in UCMM_NOW[2k_max], Position_Exchange_Aft( ) in UCMM_NOW[2k_max] is executed only in a case in which no actual exchange operation is performed (FIG. 26(7)).

[0423] (10) In each UCMM_NOW[j] where j is an odd-number, in UCMM_NOW[j] in which the exchange operation is not performed in (9), the exchange operation

[0424] Position_Exchange_Fore(UCMM_NOW[j]) is simultaneously executed by the LCMM at the next position from each position in the Hamilton cycle pH and each UCMM_NOW[j] where j is an odd number. At the same time, only in a case in which Position_Exchange_Aft( ) in UCMM_NOW[2k_max] is not executed in (9), Position_Exchange_Aft( ) in UCMM_NOW[2k_max] is executed (FIG. 27(8)).

[0425] (11) All UCMMs are simultaneously moved in the forward direction along the Hamilton cycle pH by one step (FIG. 27(9)).

[Control Object Position Exchange Operation]

[0426] In the control object position exchange operation (the aforementioned Position_Exchange_Fore and Position_Exchange_Aft), the exchange operation changes depending on the positional relationship between a control object unit j which is a UCMM and a control object unit j to be exchanged which is an LCMM. FIGS. 28 to 52 show position exchange operations in the case where the direction of j.fwdarw.j (defined as Aex) is Aex=1, 2, and 5. FIGS. 53 to 92 show position exchange operations in the case where the direction of j.fwdarw.j is Aex=3, 4, and 6. In (1) of FIG. 69, control object units indicated by 2 and 3 are made transparent in order to indicate the position of a control object unit indicated with the right-upward diagonal stripes and 1. FIGS. 28 to 52 illustrates an example of the case of Aex=1. In the case of other exchange operations of Aex=2 and 5, the direction indicated as the right direction in the figure may be regarded as a direction of Aex=2 and 5, and control objects may be caused to perform the same operation. In this case, the number of a control object unit in which the exchange operation is actually performed is converted as shown in FIG. 107. FIGS. 53 to 92 illustrates an example of the case of Aex=3. In the case of other exchange operations of Aex=4 and 6, the direction indicated as the left direction in the figure may be regarded as a direction of Aex=4 and 6, and control objects may be caused to perform the same operation. In this case, the number of a control object unit in which the exchange operation is actually performed is converted as shown in FIG. 107.

[0427] In the present invention, since each LCMM is always on the Hamilton cycle pH, in order to maintain the connection of the entire robot structure, it is sufficient that connection between each LCMM position and two LCMMs present at both adjacent positions in the Hamilton cycle pH can be maintained. That is, in the exchange operation, it is sufficient that connection between two LCMMs to be exchanged and two LCMMs present at both adjacent positions in the Hamilton cycle pH can be maintained. In this sense, in exchange between control objects i at inner positions i5, 16, i7, and i8 within a UCMM to be exchanged and control objects i at inner positions i1, i2, and i3 in an LCMM, the exchange operation is not different depending on the direction in which a control object unit j at an adjacent position on the side of a control target unit j on which it is not j on pH is present when viewed from j (the control object units are arranged in the order of j, j, j in pH), whereas in exchange between the inner positions i5, i6, i7, and i8 within the UCMM to be exchanged and the inner position i4 within the LCMM, the exchange operation differs depending on the direction (Arx) in which a control object unit j at an adjacent position on the side of a control target unit j on which it is not j on pH is present when viewed from j.

[0428] In a case where the direction of j.fwdarw.j is Aex=1, 2, and 5, for example, exchange between a control objects i and i at the inner position i5 in a UCMM and i4 in an LCMM is as shown in FIG. 41 when j.fwdarw.j is the direction of Aex=1 and j.fwdarw.j is the direction of Arx=1, 2, and 5, as shown in FIG. 42 when j.fwdarw.j is the direction of Arx=4, and as shown in FIG. 43 when j.fwdarw.j is the direction of Arx=6. In a case where the positions of control objects i within the LCMM are i1, i2, and i3, the exchange operation corresponds to FIGS. 28, 32, and 37.

[0429] In a case where the direction of j.fwdarw.j is Aex=3, 4, and 6, for example, exchange between a control objects i and i at the inner position i5 in a UCMM and i4 in an LCMM is as shown in FIGS. 65 and 66 when j.fwdarw.j is the direction of Aex=3 and j.fwdarw.j is the direction of Arx=2 and 5, as shown in FIGS. 67 and 68 when j.fwdarw.j is the direction of Arx=3, as shown in FIGS. 69 and 70 when when j.fwdarw.j is the direction of Arx=4, and as shown in FIGS. 71 and 72 when j.fwdarw.j is the direction of Arx=6. For example, the exchange operation between the control object i in i5 within the UCMM and the control objects i in i1, i2, and i3 within the LCMM correspond to FIGS. 53, 58, 61.

[0430] The reason why the above-described case classification is necessary is that the control object at the position i4 within the control object unit j which is an LCMM has the only connecting plane in j of connection with the control object unit j at the positions adjacent thereto in the direction of a=3, 4 and 6. That is, the operation for maintaining the connection differs depending on the direction in which the control object in j in contact with the control object at the position i4 in j is present.

[Position_Exchange_Fore(UCMM_NOW[j_tmp])]

[0431] (1) A control object unit UCMM_NOW[j_tmp] is defined as a control object unit j. A control object unit which is an LCMM present at an adjacent position ahead of an LCMM at the same control object unit position as the control object unit j in the Hamilton cycle pH is defined as a control object unit j, and a control object unit which is an LCMM at an adjacent position ahead of the control object unit j in the Hamilton cycle pH is defined as a control object unit j. With respect to a control object i in j, in (i) a case in which target_UCMM_or_LCMM[i]>N.sub.lcmm1, and a control object unit j was a UCMM which was at the position of P_UCMM[target_UCMM_or_LCMM[i]N.sub.lcmm] at the start of an exchange process (at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) or (ii) a case in which target_UCMM_or_LCMM[i]<N.sub.lcmm, and the control object unit j was an LCMM which was at the position of P_LCMM[target_UCMM_or_LCMM[i]] at the start of the exchange process, processing proceeds to (2) having a control object whose inner position at the start of the exchange process (inner position at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) is target_inner_before[i], among the control objects in the control object unit j, as a control object i to be exchanged with the control object i (having a control object corresponding to Ori[i]=target_inner_before[i] defined in [All_Transformation] which will be described later as the control object i). In other cases, processing is finished.

[0432] (2) Processing proceeds to (3) if the direction of j.fwdarw.j is a=1, 2 and 5 and proceeds to (4) if the direction of j.fwdarw.j is a=3, 4 and 6.

[0433] (3) If the position of the control object i within the the control object unit j is i1, i2 and i3, the exchange operation is performed through the operations shown in FIGS. 28 to 40. If the position is i4, the exchange operation is performed through the operations shown in FIGS. 41 to 52 in the direction of j.fwdarw.j. The values of Ori[i] and Ori[i] are exchanged by the control objects i and i.

[0434] (4) If the position of the control object i within the control object unit j is i1, i2 and i3, the exchange operation is performed through the operations shown in FIGS. 53 to 64. If the position is i4, the exchange operation is performed through the operations shown in FIGS. 65 to 92 in the direction of j.fwdarw.j. The values of Ori[i] and Ori[i] are exchanged by the control objects i and i.

[0435] (5) As a result of the exchange operation of (3) or (4), with respect to the control object i which has moved into the control object unit j, in a case in which target_UCMM_or_LCMM[i]>N.sub.lcmm1, and the control object unit j was a UCMM which was at the position of P_UCMM[target_UCMM_or_LCMM[i]N.sub.lcmm] at the start of the exchange process (at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) or a case in which target_UCMM_or_LCMM[i]<N.sub.lcmm, and the control object unit j was an LCMM which was at the position of P_LCMM[target_UCMM_or_LCMM[i]] at the start of the exchange process, if the inner position of the control object i that was originally at the inner position in the UCMM after the main exchange operation of the control object i at the start of the exchange process (inner position at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) is not target_inner_before[i] (if the value of Ori[i] after exchanging the values in (3) or (4) is not target_inner_before[i]), Inner_Exchange(j, j) is executed to perform exchange with a control object i in the control object unit j whose inner position at the start of the exchange process is target_inner_before[i].

[Position_Exchange_Aft(UCMM_NOW[j_tmp])]

[0436] (1) A control object unit UCMM_NOW[j_tmp] is defined as a control object unit j. A control object unit which is an LCMM present at an adjacent position before an LCMM at the same control object unit position as the control object unit j in the Hamilton cycle pH is defined as a control object unit j, and a control object unit which is an LCMM at an adjacent position before the control object unit j in the Hamilton cycle pH is defined as a control object unit j. With respect to a control object i in j, in (i) a case in which target_UCMM_or_LCMM[i]>N.sub.lcmm1, and a control object unit j was a UCMM which was at the position of

[0437] P_UCMM[target_UCMM_or_LCMM[i]N.sub.lcmm] at the start of an exchange process (at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) or (ii) a case in which target_UCMM_or_LCMM[i]<N.sub.lcmm, and the control object unit j was an LCMM which was at the position of P_LCMM[target_UCMM_or_LCMM[i]] at the start of the exchange process, processing proceeds to (2) having a control object whose inner position at the start of the exchange process (inner position at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) is target_inner_before[i], among the control objects in the control object unit j, as a control object i to be exchanged with the control object i (having a control object corresponding to Ori[i]=target_inner_before[i] defined in [All_Transformation] which will be described later as the control object i). In other cases, processing is finished.

[0438] (2) Processing proceeds to (3) if the direction of j.fwdarw.j is a=1, 2 and 5 and proceeds to (4) if the direction of j.fwdarw.j is a=3, 4 and 6.

[0439] (3) If the position of the control object i within the control object unit j is i1, i2 and i3, the exchange operation is performed through the operations shown in FIGS. 28 to 40. If the position is i4, the exchange operation is performed through the operations shown in FIGS. 41 to 52 in the direction of j.fwdarw.j. The values of Ori[i] and Ori[i] are exchanged by the control objects i and i.

[0440] (4) If the position of the control object i within the control object unit j is i1, i2 and i3, the exchange operation is performed through the operations shown in FIGS. 53 to 64. If the position is i4, the exchange operation is performed through the operations shown in FIGS. 65 to 92 in the direction of j.fwdarw.j. The values of Ori[i] and Ori[i] are exchanged by the control objects i and i.

[0441] (5) As a result of the exchange operation of (3) or (4), with respect to the control object i which has moved into the control object unit j, in a case in which target_UCMM_or_LCMM[i]>N.sub.lcmm1, and the control object unit j was a UCMM which was at the position of

[0442] P_UCMM[target_UCMM_or_LCMM[i]N.sub.lcmm] at the start of the exchange process (at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) or a case in which target_UCMM_or_LCMM[i]<N.sub.lcmm, and the control object unit j was an LCMM which was at the position of P_LCMM[target_UCMM_or_LCMM[i]] at the start of the exchange process, if the inner position of the control object i that was originally at the inner position in the UCMM after the main exchange operation of the control object i at the start of the exchange process (inner position at the start of Permutation_M_M_A_max_0, Permutation_M_M_A_max_1, or Permutation_M_M_A_max_2) is not target_inner_before[i] (if the value of Ori[i] after exchanging the values in (3) or (4) is not target_inner_before[i]), Inner_Exchange(j, j) is executed to perform exchange with a control object i in the control object unit j whose inner position at the start of the exchange process is target_inner_before[i].

[0443] [Inner_Exchange] is required when a target position of a control object i that has newly entered the control object j is within j as a result of executing (3) and (4) of Position_Exchange_Fore and Position_Exchange_Aft. Only by executing (3) and (4) of Position_Exchange_Fore and Position_Exchange_Aft, i is within j, but it is not necessarily at the correct position within j. In this case, [Inner_Exchange] serves to move i to the correct position within j. [Inner_Exchange] is a stage before the position exchange process in M starts, and is provided in consideration of a case in which target positions of control objects in j are within j (that is, a case in which position exchange within a plurality of j is required). For processing of [Inner_Exchange], a control object within each control object remembers an inner arrangement among i1, i2, i3, 14, 15, 16, i7, and i8 before each control object starts circular movement within pH. The variable is defined as Ori[i]. At the time of executing Exchange, information of Ori[i] is exchanged between the control objects i and i to be exchanged at Position_Exchange_Fore and Position_Exchange_Aft(refer to (3) and (4) of Position_Exchange_Fore andPosition_Exchange_Aft).

[Inner_Exchange(j, j)]

[0444] (1) In a case in which there are control objects i having different inner positions indicated by Ori[i] and target_inner_before[i] among control objects i in a control object unit j, which have target positions within the control object unit j which is a UCMM, (2) is executed for one thereof. If not, processing is finished.

[0445] (2) A control object i corresponding to Ori[i]=target_inner_before[i] is selected from control objects i within the control object unit j that is a UCMM, and the control object i and the control object i are exchanged by the operations shown in FIGS. 93 to 98 when the direction of j.fwdarw.j is a=1, 2, and 5. When the direction of j.fwdarw.j is a=3, 4, and 6, the control object i and the control object i are exchanged by the operations shown in FIGS. 99 to 106. Processing returns to (1).

[0446] The inner position exchange operation within a control object unit in (2) is shown in FIGS. 93 to 106. FIGS. 93 to 106 also show examples of actual operations in the case where Aex=1 and 3. Similarly, in the case of the exchange operation with other values of Aex, the direction of j.fwdarw.j in the figure may be regarded as the direction of Aex, and a control object may be caused to perform the same operation. In this case, the number of a control object unit in which the exchange operation is actually performed is converted as shown in FIG. 107.

[Transformation process of M.fwdarw.G]

[0447] The present transformation process is basically obtained by temporally reverse-reproducing [transformation process of S.fwdarw.M] in which S has been exchanged with G and M has been exchanged with M [in the transformation process of G.fwdarw.M]. That is, homogeneous transformation from G to the intermediate position Mpre is performed by the existing 8-square homogeneous transformation method, and then [Mpre->M_Transform] which will be described later is executed for transformation from Mpre to M. An example of an existing 8-square homogeneous transformation method is the method described in PCT/JP2021/025458.

[0448] Similarly, for Mpre, for convenience in the exchange process of M.fwdarw.M, which will be described later, an 8-square control object position within Mpre is defined as P_Mpre[j]=(X_Mpre[j], Y_Mpre[j], Z_Mpre[j]) (j=0, 1, 2, . . . , j_max/21), it is numbered as P_Mpre[j]=P_Mpre[j+drift] on the assumption that driftN.sub.ucmm(2+N_add) when A_max=0, driftN.sub.ucmm(0+N_add) when A_max=1, and driftN.sub.ucmm(1+N_add) when A_max=2 (P_Mpre[j]=P_Mpre[j+drfitN.sub.hamilton] in (j+drfit N.sub.hamilton). The outline of transformation from Mpre to M is as follows.

[0449] (1) Each UCMM at a control object unit position from P_Mpre[j_max/21] to P_Mpre[j_max/21j_become_lcmm] is moved to fill a Hamilton cycle position which is blank in M Pre. The value of j_become_lcmm is N.sub.lcmmj_max/21, that is, k_max1 when A_max=0, k_max when A_max=1, and k_max when when A_max=2.

[0450] (2) UCMMs at control object unit positions of P_Mpre[N.sub.ucmm1] (=P_Mpre[j_max/21j_become_lcmm1]) to P_Mpre[0] are moved to predetermined UCMM positions in M.

[0451] Pseudo code is as follows.

[Mpre->M_Transform]

[0452] (1) In j=0 to j_become_lcmm, the UCMM at the control object unit position of P_Mpre[j_max/21j] sets a target position thereof to (Hamilton_X[N.sub.hamilton_min3j+drfit], Hamilton_Y[N.sub.hamilton_min3j+drfit], Hamilton_Z[N.sub.hamilton_min3j+drfit]) when A_max=0 and 1, and to (Hamilton_X[N.sub.hamilton_min4j+drfit], Hamilton_Y[N.sub.hamilton_min4j+drfit], Hamilton_Z[N.sub.hamilton_min4j+drfit]) when A_max=2, and moves on LCMMs in a direction in which the number of the position in pH increases along the Hamilton cycle pH until reaching a position adjacent to each target position in the Hamilton cycle pH. Thereafter, it is transformed and moved to LCMM to each target position. A movement start time difference between UCMMs at P_Mpre[j_max/21j] and P_Mpre[j_max/21(j+1)] is set to the number of time steps required for P_Mpre[j_max/21j] to transform and move to LCMMs.

[0453] (2) In j=0 to N.sub.ucmm1, the UCMM at the control object unit position of P_Mpre[N.sub.ucmm1j] sets a target position thereof to P_UCMM[N.sub.ucmm1j]=(Hamilton_X[2(N.sub.ucmm1j)+drfit], Hamilton_Y[2(N.sub.ucmm1j)+drfit], Hamilton_Z[2(N.sub.ucmm1-j)+drfit]), and moves on LCMMs in a direction in which the number of the position in pH increases along the Hamilton cycle pH until reaching each target position. A movement start time difference between UCMMs at P_Mpre[N.sub.ucmm1j] and P_Mpre[N.sub.ucmm1(j+1)] is set to the number of time steps required for each UCMM to move on LCMMs.

[0454] In summary, [transformation process of S.fwdarw.M] and [transformation process of G.fwdarw.M] are as follows.

[Transformation process of S.fwdarw.M]

[0455] (1) Homogeneous transformation from S to Mpre is performed using an existing 8-square homogeneous transformation method. An example of an existing 8-square homogeneous transformation method is the method described in PCT/JP2021/025458.

[0456] (2) [Mpre->M_Transform] is executed.

[Transformation process of G.fwdarw.M]

[0457] (1) Homogeneous transformation from G.fwdarw.Mpre is performed using an existing 8-square homogeneous transformation method. An example of an existing 8-square homogeneous transformation method is the method described in PCT/JP2021/025458.

[0458] (2) [Mpre->M_Transform] is executed. The position of each control object obtained as a result is set to target[i].

[Whole Transformation Process]

[0459] By combining the processes described above, in other words, by performing processing of [All_Transformation] which will be described below, the whole heterogeneous transformation process is completed.

[All_Transformation]

[0460] (1) Control objects are moved according to an operation history calculated in [Transformation process of S.fwdarw.M]. This processing is performed by a first movement planning unit 1 and a first movement unit 2 which will be described later.

[0461] (2) [Transformation process of G.fwdarw.M] is executed by a virtual robot to obtain operation history data. This processing is performed by a second movement planning unit 3.

[0462] (3) The control object unit inner position of each control object i at the intermediate position M is stored in a variable Ori[i]. Thereafter, [Position change process at intermediate position M] is executed, and each control object at the intermediate position M before exchange is moved to the intermediate position M after exchange. Specifically, [Permutation_M_M_A_max_0] is executed when A_max=0, [Permutation_M_M_A_max_1] is executed when A_max=1, and [Permutation_M_M_A_max_2] is executed when A_max=2. This processing is performed by an intermediate position exchange unit 4 which will be described later.

[0463] (4) Control objects are moved according to the operation obtained by reversely reproducing the operation history calculated in [Transformation process of G.fwdarw.M]. This processing is performed by a second movement unit 5 which will be described later.

Embodiment

[0464] An embodiment of the present invention will be described in detail below. Further, components with the same function are denoted by the same reference numerals in the diagrams, and overlapping explanations are omitted accordingly. First, an embodiment of a control device and method will be described.

[0465] As shown in FIG. 108, the control device includes the first movement planning unit 1, the first movement unit 2, the second movement planning unit 3, the intermediate position exchange unit 4 and the second movement unit 5.

[0466] The control method is realized, for example, by each constituent unit of the control device performing processing of step S1 to step S5 shown in FIG. 109 which will be described below.

[0467] Each constituent unit of the control device will be described below.

<First Movement Planning Unit 1>

[0468] The first movement planning unit 1 creates a first movement plan for moving each control object at an initial position S to an intermediate position M before exchange in control object units (step S1). The created first movement plan is output to the first movement unit 2.

[0469] For example, the first movement planning unit 1 creates the first movement plan by performing processing of [Transformation process of S.fwdarw.M] described above.

[0470] More specifically, the first movement planning unit 1 creates the first movement plan by performing processing of homogeneous transformation from the initial position S to Mpre and processing of homogeneous transformation from Mpre to the intermediate position M before exchange, which have been described above.

[0471] In this embodiment, processing is performed on the basis of a predetermined intermediate position M before exchange.

<First Movement Unit 2>

[0472] The first movement plan is input to the first movement unit 2.

[0473] The first movement unit 2 moves each control object at the initial position S to the intermediate position M before exchange in control object units according to the first movement plan (step S2).

[0474] The first movement unit 2 moves control objects in the control object units according to the method described in [Transformation process of S.fwdarw.M].

<Second Movement Planning Unit 3>

[0475] The second movement planning unit 3 creates a second movement plan for moving each control object assumed to be at a target position G to an intermediate position M after exchange in control object units (step S3). The created second movement plan is output to the intermediate position exchange unit 4 and the second movement unit 5.

[0476] For example, the second movement planning unit 3 creates the second movement plan by performing [Transformation process of G.fwdarw.M] described above.

[0477] In this embodiment, processing is performed on the basis of a predetermined intermediate position M after exchange.

<Intermediate Position Exchange Unit 4>

[0478] The first movement plan created by the first movement planning unit 1 and the second movement plan created by the second movement planning unit 3 are input to the intermediate position exchange unit 4.

[0479] The intermediate position exchange unit 4 moves each control object at the intermediate position M before exchange to a movement destination of each control object determined by the second movement plan among intermediate positions M after exchange (step S4).

[0480] For example, the intermediate position exchange unit 4 performs processing of [Position exchange process at intermediate position M] described above.

[0481] That is, the intermediate position exchange unit 4 moves a first type control object unit j along a Hamiltonian cycle, and in a case in which there is a movement destination of a control object constituting the first type control object unit j, determined by the second movement plan, among second type control object units adjacent to the first type control object unit j, repeats processing of exchanging the control object with the control object at the movement destination to move each control object moved by the first movement unit to the movement destination of each control object determined by the second movement plan among the intermediate positions M after exchange. In such processing, each control object unit moves all positions on the Hamilton cycle as the first type control object unit j.

[0482] As described above, a graph in which a control object unit at an intermediate position is defined as a node and a plane connecting two control object units in contact with each other is defined as an edge constitutes a part or the whole of the Hamilton cycle, and a combined control object unit and a second type control object unit are alternately disposed at the intermediate position along the Hamilton cycle.

<Second Movement Unit 5>

[0483] The second movement plan is input to the second movement unit 5.

[0484] The second movement unit 5 moves each control object at an intermediate position M after exchange to a target position G in control object units according to a plan obtained by temporally reversing the second movement plan (step S5).

[0485] The second movement unit 5 moves the control object in the control object units by the method described in [Transformation process of M-G].

[0486] The control device may include an intermediate position determination unit 6 indicated by a broken line in FIG. 108.

[0487] In this case, the intermediate position determination unit 6 determines the intermediate position M before exchange and the intermediate position M after exchange by performing processing of [M_Decision] described above. The intermediate position determination unit 6 may determine the intermediate position M before exchange and the intermediate position M after exchange by performing processing of [M_Additional_Decision] described above. The determined intermediate position M before exchange and intermediate position M after exchange are output to the first movement planning unit 1 and the second movement planning unit 3.

Modified Examples

[0488] While embodiments of the present invention have been described above, specific configurations are not limited to the embodiments and, needless to say, the present invention also includes appropriate modifications in design or the like having been made without departing from the spirit and the scope of the present invention.

[0489] The various types of processing described in the embodiments are not limited to being executed in a time series manner in the described order, and may be executed in parallel or individually in accordance with the processing capability of the device that executes the processing or as required.

[0490] Data may be directly exchanged between the constituent elements of the control device or may be exchanged via a storage unit which is not shown.

Program, Recording Medium

[0491] The processing of each unit of each device may be implemented by a computer, and in this case, the processing details of the functions that each device should have are described by a program. Then, various types of processing functions in each device are realized on the computer by causing this program to be read by a storage unit 1020 of the computer 1000 shown in FIG. 110 and operating an arithmetic processing unit 1010, an input unit 1030, an output unit 1040, a display unit 1060, and the like.

[0492] A program in which details of this processing are described can be recorded on a computer-readable recording medium. The computer-readable recording medium is, for example, a non-transitory recording medium, and specifically a magnetic recording device, an optical disc, and the like.

[0493] The program is distributed, for example, by sales, transfer, or lending of a portable recording medium such as a DVD or a CD-ROM on which the program is recorded. In addition, the distribution of the program may be performed by storing the program in advance in a storage device of a server computer and transferring the program from the server computer to another computer via a network.

[0494] The computer executing such a program first temporarily stores the program recorded in the portable recording medium or the program transferred from the server computer, for example, in an auxiliary recording unit 1050, which is its own non-transitory storage device. Then, when executing processing, the computer reads the program stored in the auxiliary recording unit 1050 serving as its own non-transitory storage device onto the storage unit 1020, and executes processing according to the read program. Alternatively, as another of executing the program, the computer may read the program directly from the portable recording medium onto the storage unit 1020, and execute processing according to the program, or the computer may sequentially execute processing according to the program received from the server computer every time the program is transferred thereto from the server computer.

[0495] Moreover, the above-described processing may be executed by a so-called application service provider (ASP) type service that implements a processing function only by an execution instruction and result acquisition without transferring the program from the server computer to the computer. Note that the program in the present embodiment includes information that is used for processing by an electronic computer and is equivalent to the program (data or the like that is not a direct command to the computer but has property that defines processing performed by the computer).

[0496] In addition, although the present device is configured by executing a predetermined program on the computer in this from, at least a part of the details of the processing may be implemented by hardware. For example, the first movement planning unit 1, the first movement unit 2, the second movement planning unit 3, the intermediate position exchange unit 4, the second movement unit 5, and the intermediate position determination unit 6 may be configured by a processing circuit.

[0497] In addition, modifications can be made as appropriate without departing from the gist of the present invention.

REFERENCE SIGNS LIST

[0498] 1 First movement planning unit [0499] 2 First movement unit [0500] 3 Second movement planning unit [0501] 4 Intermediate position exchange unit [0502] 5 Second movement unit [0503] 6 Intermediate position determination unit