JP6553000B2 - Control object position change control device, control object position change control method, program - Google Patents

Description

  The present invention relates to a technique for controlling actions of a plurality of control objects. For example, the present invention relates to a robot cooperative control technique in which a plurality of robots are moved in coordination from a formation of a row at a start position to avoid an obstacle and to obtain an action plan of each robot for forming a row at a target position.

  In recent years, researches for efficiently controlling a large number of autonomous mobile robots have been actively conducted. The contents of the mission are various, such as monitoring of places that people can not enter, transportation of goods, etc. However, there is a need for a technology to efficiently form squadrons by the coordinated operation of many robots, and research is actively conducted (For example, refer nonpatent literature 1). In order to realize efficient formation of formations by a large number of robots, it is important to plan in advance the arrangement, operation sequence, etc. of each robot. In such a plan, naturally, the existence of an obstacle and the shape of a path in a real environment in which a plurality of robots operate must be sufficiently considered.

  As one of the effective methods for performing such plan calculations, there are dynamic programming methods and reinforcement learning methods in the Markov decision process, and various studies have been conducted (see, for example, Non-Patent Document 2) ).

  Also, in the robot row control, the robot row control under the assumption that the robot moves as a whole in a state where the robots are in contact with each other, the relative positional relationship between the robots There is an advantage that the determination of the absolute position of each robot is possible, and an advantage that no additional equipment for position measurement is required, and such robots are also studied. For example, in the one shown in Non-Patent Document 3, the formation control from an arbitrary rectangular formation row to another rectangular formation row is shown.

  In addition, in a series of studies leading to the research shown in Non-Patent Document 4 and Non-Patent Document 5, tactic control that changes from one formation to another formation is shown.

  In the method shown in the research shown in Non-Patent Document 6, a plane shearing operation between a plurality of cube-shaped robots (an operation in which a robot slides on a contact surface while in contact with another robot) The robot's platoon deformation by is handled.

M. Shimizu, A. Ishiguro, T. Kawakatsu, Y. Masubuchi, “Coherent Swarming from Local Interaction by Exploiting Molecular Dynamics and Stokesian Dynamics Methods”, Proceeaings of the 2003 IEEE / RSJ International Conference on intelligent Robots and Systems, Las Veqas, pp.1614-1619, October 2003. Y. Wang, CWde Silva, “Multi-Robot Box-pushing: Single Agent Q-Learning vs. Team Q-Learning”, Proceedings of the 2006 IEEE / RSJ International Conference on Intelligent Robots and Systems, Beijing, China, pp .3694-3699, October 2006. A. Becker, G. Habibi, J. Werfel, M. Rubenstein, and J. McLurkin, “Massive Uniform Manipulation: Controlling Large Populations of Simple Robots with a Common Input Signal”, Proceedings of the IEEE / RSJ International Conference on Intelligent Robots and Systems, Japan, pp. 520-527, November, 2013. Stanton Wong1 and Jennifer Walter ”Deterministic Distributed Algorithm for Self-Reconfiguration of Modular Robots from Arbitrary to Straight Chain Configurations”, Proceedings of the 2013 IEEE International Conference on Robotics and Automation (ICRA), Karlsruhe, Germany, pp.537-543, May 6-10, 2013. Michael Rubenstein, Alejandro Cornejo, Radhika Nagpal, “Programmable self-assembly in a thousand-robot swarm”, SCIENCE, 2014, Vol. 345, Issue 6198, pp.795-799. H. Kawano, “Complete Reconfiguration Algorithm for Sliding Cube- shaped Modular Robots with Sliding Motion Primitive”, in Proc. 2015 IEEE / RSJ Int. Conf. Intelligent Robots and Systems, Hamburg, Germany, pp. 3276-3283, Sep. , 2015.

  However, the method of Non-Patent Document 1 controls the movement of the group robot using a method of incorporating hydrodynamic characteristics into robot movement, and has the advantage of enabling control with low computational load. It is not always possible to form a formation of any shape.

  In addition, as in the method of Non-Patent Document 2, when such a plan is performed using dynamic programming or reinforcement learning in the Markov decision process, a plurality of robots are required compared to using a single robot. When used, the time required for the calculation and the storage capacity of the computer increase exponentially with respect to the number of robots. The main cause is the enormous increase in the number of states in the Markov state space for search computation. Non-Patent Document 2 does not show a solution to the explosion problem in the Markov state space, in which the computational load increases exponentially with the increase in the number of robots in the verified reinforcement learning method.

  Further, both of the methods of Non-Patent Documents 1 and 2 require additional position measurement equipment.

  In addition, Non-Patent Document 3 takes into consideration the condition that the motion commands given to the robot at each time point are all in the same direction, and does not require additional position measurement equipment, but this is a barrier to its realization. I need the existence of things. In addition, the problem of the collapse of the formation caused by the movement error of each robot in one operation has not been solved.

  In the method of Non-Patent Document 4, conversion to a linear formation has to be performed once, and the restriction on the possible formation formation itself is large.

  In the method of Non-Patent Document 5, there are problems such as the fact that the starting formation and the target formation must share points, and that no obstacle is considered.

  In the method of Non-Patent Document 6, although the homogeneous position control of a system in which the position of each robot is not designated in the formation in consideration of the presence of an obstacle can be realized, the position of each robot is determined Heterogeneous formation control of the method specified in is not realized. Therefore, for example, each robot such as a robot equipped with a camera or a robot equipped with wheels has a different role, and controls the shape of a formation while arranging each robot at an appropriate position in the formation of a robot. It cannot be used. Therefore, there is a problem that all functions required for all robots must be implemented.

  In view of such a current situation, in the present invention, while considering the existence of a large number of robots, while maintaining the state in which the robots are in contact with each other, it is possible to set any other desired position from the formation of a row at any start position. As in the case of implementing Heterogeneous Corps train control by moving each robot to the individual target position after performing homogeneous Corps train transformation operation in an environment with obstacles to the formation of a squad formation in the case, before and after the start of exchange of robot positions It is an object of the present invention to provide a robot repositioning technology that can position each robot at an appropriate position within the robot array under the condition that the robot array is the same.

  In one embodiment of the present invention, M, N, and Q are each an integer of 2 or more, R is an integer of 2 or more, p is M × N × Q × R, and replacement is performed before the start of replacement. A control for replacing the positions of the control objects so that each of the p control objects is disposed at a designated position in the set under the condition that the set of positions after the end is the same. An object replacement control device, wherein a direction not parallel to the first direction is a second direction, a direction opposite to the first direction is a third direction, and a direction opposite to the second direction is a second direction. Four directions, a direction not parallel to the plane formed by the first direction and the second direction is the fifth direction, a direction opposite to the fifth direction is the sixth direction, and M × N × Q positions Each position constituting the set is in at least one of the first direction to the sixth direction. Adjacent to the other position, the set is an arbitrary shape of one group of R position units, and the control object is adjacent to the first in the three-dimensional space of the control object. One position, a second position adjacent in the second direction, a third position adjacent in the third direction, a fourth position adjacent in the fourth direction, and a fifth position adjacent in the fifth direction, adjacent in the sixth direction And the control target object is controlled to move to any one of the first to sixth positions on the three-dimensional space, and the control object is to be reached within the set. Assuming that the position is a target position, and the current position in the set of control objects is a current position, and the current position of the control object does not match the target position of the control object, the target from the current position Generate swap route to position A virtual path that occurs with the movement of the controlled object or moves in the direction opposite to the moving direction of the controlled object as a void, and two voids A void control unit for switching the control object at the current position and the control object at the target position along the replacement path using the two void generation units; When the unit generates a void, the controlled object moved to a position adjacent to the set is taken as the evacuation control object, and the evacuated control objects are returned to the original position in the set in which each existed. And a void eraser that erases the two voids.

  In one embodiment of the present invention, M, N, and Q are each an integer of 2 or more, R is an integer of 2 or more, p is M × N × Q × R, and replacement is performed before the start of replacement. A control for replacing the positions of the control objects so that each of the p control objects is disposed at a designated position in the set under the condition that the set of positions after the end is the same. An object replacement control device, wherein a direction not parallel to the first direction is a second direction, a direction opposite to the first direction is a third direction, and a direction opposite to the second direction is a second direction. Four directions, a direction not parallel to the plane formed by the first direction and the second direction is the fifth direction, a direction opposite to the fifth direction is the sixth direction, and M × N × Q positions Each position constituting the set is in at least one of the first direction to the sixth direction. Adjacent to the other position, the set is an arbitrary shape of one group of R position units, and the control object is adjacent to the first in the three-dimensional space of the control object. One position, a second position adjacent in the second direction, a third position adjacent in the third direction, a fourth position adjacent in the fourth direction, and a fifth position adjacent in the fifth direction, adjacent in the sixth direction And the control target object is controlled to move to any one of the first to sixth positions on the three-dimensional space, and the control object is to be reached within the set. Assuming that the position is a target position, and the current position in the set of control objects is a current position, and the current position of the control object does not match the target position of the control object, the target from the current position Generate swap route to position And a virtual existence that occurs with the movement of the controlled object or moves in the direction opposite to the moving direction of the controlled object as a void, and in a predetermined case, in the set A void generation unit for generating two voids, and a replacement control unit for replacing the control object at the current position and the control object at the target position along the replacement path using the two voids When the void generation unit generates a void, a control target object moved to a position adjacent to the set is used as a shunt control target object, and all control targets reach their respective target positions, And a final void eraser that erases the two voids by returning the evacuation control objects to their original positions in the set in which each was present, and the void generator generates a void. In the predetermined case, either the controlled object at the current position or the controlled object at the target position in the case where the void generation unit is executed for the first time or for the second time or later is the second case. This is when it coincides with two save control objects.

  According to the present invention, each robot can be placed at an appropriate position in the robot row by the surface shearing operation between the robots under the condition that the robot row before and after the start of the replacement of the robot position is the same.

The figure for demonstrating the movement of a robot. FIG. 2A is a view for explaining a set of start positions, and FIG. 2B is a view for explaining a set of target positions. The figure which shows a mode that one void which existed in a certain position moves to another position. The figure for demonstrating a robot unit. The figure for demonstrating the duty which a number of robots cooperate and move from the row formation state in a starting position, and perform row formation in a target position. The figure for demonstrating the restrictions of robot position switching control. The figure which shows the mode of each robot position replacement control. The figure which shows the appearance of the divided | segmented path | pass. The figure which shows the mode of the robot position exchange in a line element. The figure which shows the mode of the robot position exchange in a corner element. The figure which shows the variable used by Void_Move (the 1). The figure which shows the variable used by Void_Move (the 2). The figure which shows the example of the position where a retraction | saving robot can not maintain the connection to another robot. The functional block diagram of the action control system which concerns on 1st embodiment. The figure which shows the example of the processing flow (robot position switching control) of the action control system which concerns on 1st embodiment. The functional block diagram of the action control system which concerns on 2nd embodiment. The figure which shows the example of the processing flow (robot position switching control) of the action control system which concerns on 2nd embodiment.

  Hereinafter, embodiments of the present invention will be described. In the drawings used in the following description, the same reference numerals are given to constituent parts having the same functions and steps for performing the same processing, and redundant description will be omitted.

<First embodiment>
First, the theoretical background of the behavior control system and method will be described. Hereinafter, a case where the control target that is the target of behavior control is a robot will be described as an example, but the control target may be other than the robot as long as it can be a target of control.

[Problem setting]
A number of robots cooperate to move from the formation position at the start position while maintaining contact with each robot, and the task of forming the formation at the target position is, for example, as illustrated in FIG. The use of a cubic robot capable of moving by sliding contact surfaces is assumed. As shown in FIG. 2, this is realized by moving a plurality of robots from a start position to a target position in a room separated by walls (however, the walls are omitted in the figure).

  As for the robot, for example, as shown in FIG. 1, while maintaining the state in which the other robot is present in one of the six squares in the vertical and horizontal height direction (hereinafter also referred to as “upper, lower, left, right and fore)”. It shall be moved. This method has an advantage that one robot itself can accurately measure the movement amount of one operation by moving the distance for the size of one robot. Also, by measuring the relative position of adjacent robots sharing one plane, it is possible to easily know the position of each robot in the entire group of robots. For this reason, it is difficult to cause a problem that the formation is collapsed due to an error in the movement amount of the robot. In addition, it is possible to move a plurality of robots at the same time as connecting a plurality of robots.

  Note that the robot can know whether another robot is present at the next position, whether there is an obstacle, and whether or not the robot is at the target position.

  There are p robots (p ≧ 16 = 8 × 2) that perform the mission, and each robot can move in the XYZ axial direction in the three-dimensional space while sharing one or more faces with the adjacent robots. Each cube of FIG. 1 shows the position of each robot. Each cube can have only one robot. Each robot is assumed to be stationary if there are obstacles or other robots in the direction of movement. Note that a cubic space in which a robot can exist is also referred to as a mass or a lattice. In FIG. 2, the gray-filled squares indicate the positions where the robot is present, and the open squares surrounded by solid lines indicate the positions where the obstacles are present. The position where the robot of FIG. 2A is present indicates a set of start positions of the robot, and the position where the robot of FIG. 2B is present indicates a set of target positions of the robot. An area represented by a set of target positions is also called a target platoon area. In this way, each start position and each target position are adjacent to another start position and target position in at least one of the vertical and horizontal height directions, respectively, and the row shape at the start position and target position of the robot is one block respectively. Any shape.

[Coordinate setting of robot]
The initial position of each robot i (i is the robot number i = 0, 1, 2, 3,..., P-1) is set as (Xr0 [i], Yr0 [i], Zr0 [i]), and the target is Assuming that the position is (Xre [i], Yre [i], Zre [i]), this problem can be defined as that the robot placed at the initial position finds an action plan for moving to the target position. . Let G be a set of target positions (Xre [i], Yre [i], Zre [i]).

[Define mission space]
When i is a robot number, each state of the robot i (the position and action of the robot) is represented by discrete values. When the room is represented in a three-dimensional space consisting of an X, Y, Z orthogonal coordinate system, each position is represented by values in which the X axis, Y axis, and Z axis are respectively discretized. That is, the room (three-dimensional space) is divided by a lattice, and each lattice corresponds to each position. In each grid, “present / none” of the obstacle is set in advance.

[Define robot motion]
The action subject is each robot placed in the room. The action a of the robot i (i is a robot number) takes one of a total of seven types: stationary and movement of one lattice in the vertical and horizontal height directions. For example, if a∈ {0,1,2,3,4,5,6}
0: stationary
1: Move one grid in the positive X-axis direction in three-dimensional space
2: Move one grid in the positive Y-axis direction in three-dimensional space
3: Move one grid in the negative X-axis direction in three-dimensional space
4: Move one grid in the negative Y-axis direction in three-dimensional space
5: Move one grid in the positive Z-axis direction in three-dimensional space
6: Suppose that one grid is moved in the negative Z-axis direction in a three-dimensional space.

[Problems in search calculation]
The state space in such a mission environment has a state of the number of dimensions of the number of robots × 3, and the number of selectable actions exists by the number of robots (= 7 ways) of the number of robots. For example, if the number of robots is 50 and the number of grids in the vertical and horizontal height directions of the room is 20, the number of states becomes 20 to the 150th power, and the amount of resources required for search calculation becomes enormous. . Furthermore, each time the number of robots increases, the number of states increases 8000 times. As described in the [Problem Setting] section of this embodiment, when the constraint condition that the robots are in contact with each other is taken in, the search calculation must be performed in consideration of the mutual movement of the robots. It is difficult to reduce the amount of calculation, which is a big problem when using multiple robots.

[Characteristics of homogeneous platoon control in Non-Patent Document 6]
In the homogenous formation control in Non-Patent Document 6, the concept of void control is introduced as one of the measures for solving the above-described problem of calculation load. In addition, in order to overcome the problem of platoon deformation described in [Problem Setting], the concept of 8 mass robot units is also introduced.

  First, void control will be described. The term “void” as used herein refers to a gap that can be made to the original position after a certain robot moves to another position. In other words, a void is a virtual entity that moves in a direction opposite to the direction in which the robot moves. In such a group robot formation problem, the amount of search calculation explodes because it focuses on the movement of multiple robots, but if you change the viewpoint and focus on the movement of voids, the movement of many robots The problem of planning can be considered as a single void operation plan, which is suitable for reducing search calculation load. FIG. 3 shows how the void moves as the robot moves.

[Introduction of 8 mass robot units]
Furthermore, in Non-Patent Document 6, as shown in FIG. 4, a robot adjacent to eight field shapes is taken as one unit (robot unit), and the robot maintains the field shape robot unit while maintaining the field shape robot unit. Suppose you move. In other words, every eight robots constitute one robot unit, and each of the eight robots constituting one robot unit maintains a state adjacent to another robot constituting one robot unit in three directions. Do the move. This group of robot units is controlled to share a face with each other and to move while touching each other.

  As a reason for moving such eight robots as one unit, as long as the movement is performed in such a state, each robot unit is missing even if any one robot in each robot unit is missing. This is because it is not necessary to destroy the positional relationship of contacting each other on one surface. That is, this is because it leads to reducing the calculation load for considering the connection between robots in the determination of the movement of each robot that must maintain the formation of the formation. If the number of voids in each robot unit is one or less, voids may exist in the entire robot unit. Therefore, a plurality of voids may be present in parallel in the robot group at one time to make the robot It is also possible to speed up the formation deformation operation.

Here, it is assumed that a robot unit formed by eight robots is a unit of one mass (hereinafter, this unit is also referred to as “mass unit” or “position unit” in this embodiment), and one mass unit is one state Build a state space as When the position of the robot unit is (Xr_unit [j], Yr_unit [j], Zr_unit [j]) (j = 0,1,2, ... j_max-1), the robot belonging to the robot unit j is i1, i2, i3, i4, i5, i6, i7, i8
Xri1 = 2 × Xr_unit [j]
Yri1 = 2 × Yr_unit [j]
Zri1 = 2 × Zr_unit [j]
Xri2 = 2 × Xr_unit [j] + 1
Yri2 = 2 × Yr_unit [j]
Zri2 = 2 × Zr_unit [j]
Xri3 = 2 × Xr_unit [j]
Yri3 = 2 × Yr_unit [j] + 1
Zri3 = 2 × Zr_unit [j]
Xri4 = 2 × Xr_unit [j] + 1
Yri4 = 2 × Yr_unit [j] + 1
Zri4 = 2 × Zr_unit [j]
Xri5 = 2 × Xr_unit [j]
Yri5 = 2 × Yr_unit [j]
Zri5 = 2 × Zr_unit [j] + 1
Xri6 = 2 × Xr_unit [j] + 1
Yri6 = 2 × Yr_unit [j]
Zri6 = 2 × Zr_unit [j] + 1
Xri7 = 2 × Xr_unit [j]
Yri7 = 2 × Yr_unit [j] + 1
Zri7 = 2 × Zr_unit [j] + 1
Xri8 = 2 × Xr_unit [j] + 1
Yri8 = 2 × Yr_unit [j] + 1
Zri8 = 2 × Zr_unit [j] + 1
It is.

  Hereinafter, the total number p of robots is a multiple of 8. Also, assuming that the transformation of a set S of start positions of robots to a set G of target positions of robots is completed by the method of Non-Patent Document 6, each robot is designated in the set G of target positions. The problem of moving to a different position (heterogeneous robot position exchange control) remains. Hereinafter, the heterogeneous robot position switching control will be described.

  For reference, FIG. 5 shows an example of the transition state of the robot group when it is controlled by the method of Non-Patent Document 6 and is transformed from the set of start positions of FIG. 2A to the set of target positions of FIG. 2B. Note that the set of start positions and the set of target positions each have an arbitrary shape of one mass consisting of R (R = p / 8) position units.

[Heterogeneous robot position switching control]
Heterogeneous in which each robot i is arranged at the target position (Xre [i], Yre [i], Zre [i]) from the state where each robot i exists at an arbitrary position in the set G of target positions. The robot position replacement control method will be described below.

[Robot Relocation Control]
If the position of each robot j before execution of robot position change control is (Xrh [j], Yrh [j], Zrh [j]), the robot position change control is (Xrh [j], Yrh [j ], Zrh [j]) = (Xre [i], Yre [i], Zre [i]) to identify a set of i and j, and move robot i to the current position of robot j . That is, assuming that the movement destination robot position of the robot i is d (i), d (i) = j, and there is no exception to control to move all the robots i to the current position of the robot d (i) .

  The important thing in this robot position change control is that each robot position change must be performed without the robot being present in an area other than the area which could be occupied by the robot in the homogeneous row control of Non-Patent Document 6. is there. That is, in the present robot position switching control, the robot should not be moved to an area other than the combination of the start position set S, the path P and the target position set G of the robots before homogeneous row control.

  Note that the path P is a set of squares on the path where each robot has moved from the set S of start positions to the set G of target positions by the method of Non-Patent Document 6.

  At the start of this robot position change control, the entire robot has the same shape as G. Here, since G always has a surface of one robot unit in contact with P, let that surface be Ss. The robot unit position in P in contact with Ss is Ms (see FIG. 6). If the positions of all the robots can be interchanged within the space occupied only by G and Ms, it can be said that the robot position interchange control can be applied after any homogeneous robot platoon deformation control. Of course, in addition to the robot unit position Ms, when an open space that is in contact with the target position set G and is not occupied by an obstacle is secured for one robot unit (hereinafter referred to as such an open robot unit position). Mopen may perform robot position exchange control in a space occupied by a robot unit position Mopen other than the robot unit position Ms and a set G of target positions.

  Each robot i moves from the current position of the robot i to the position of the robot d (i), and the movement of the robot d (i) expelled by the robot i to the position where the robot i was originally is one unit. , Each individual robot position exchange control.

  In the robot position switching control, first, an arbitrary robot i is selected, and each robot position switching control is performed to replace the robot i with the position of the robot d (i), and then the robot d (i) is transferred to the robot d (d (d ( i)) Execute the individual robot position replacement control to replace the position of the robot, and then execute the individual robot position replacement control to replace the robot d (d (i)) with the position of the robot d (d (d (i))). It is performed by repeatedly executing each individual robot position exchange control in the form of This repetition is performed until i = d (d (d (d (... D (i))))) when each individual robot position replacing operation is started. Then, the robot position exchange control is completed by repeating the individual robot position exchange control repeatedly until there is no robot whose position has not been exchanged. The robot position change control procedure Robot_Position_Permutation shown in FIG. 7 is as follows.

[Robot_Position_Permutation]
(1) The variable p (i) = 0 is set for all robots i (p is a robot position exchanged determination flag). Set tp = 0 and execute Record_History (where tp is a time counter).
(2) Let p (i) = 1 for all robots i where i = d (i).
(3) Repeat (4) to (6) until p (i) = 1 for all i.
(4) Select the smallest i that satisfies p (i) = 0.
(5) Repeat step (6) unless i = d (i).
(6) The exchange source robot origin ← i and the exchange destination robot destination ← d (i) are set, and the Each_Robot_Position_Exchange is executed.

  The Record_History, which will be described later, is a process of recording the position of each robot i at a time point (current point) when the time counter is tp. Here, the position of each robot i at tp = 0, that is, the initial state is recorded.

  In addition, although each Robot_Position_Exchange is also described later, this is processing for performing individual robot position exchange control.

[Each robot position change control]
What is important in each robot position swap control is that the position of the other robot is guaranteed to remain unchanged, except that the position of the origin robot and the destination robot destination are swapped before and after the swap. It is that you are.

  In order to guarantee such an operation, in each robot position change control, first, two voids are first generated in G, and then the two generated voids are moved and supplied by the two voids. The position of the robot is changed using the gap space. Also, in order to generate two voids, control is performed to drive two robots in G out of G.

  Each individual robot position change control procedure Such_Robot_Position_Exchange is as follows.

[Each_Robot_Position_Exchange]
(1) Execute Calculate_Path_From_Origin_To_Destination.
(2) Execute Void_Generation.
(3) Execute Robot_Exchange.
(4) Execute Void_UnGeneration.

  In Calculate_Path_From_Origin_To_Destination of (1), a path connecting the position of the robot origin in G to the position of the robot destination is calculated (hereinafter referred to as swap path generation). In Void_Generation of (2), two voids are generated in G (hereinafter referred to as void generation). In (3) Robot_Exchange, the position of the robot origin and the position of the robot destination are interchanged (hereinafter referred to as interchange control). In Void_UnGeneration of (4), the two robots driven out of G by void generation are returned to the original position in G (hereinafter referred to as void elimination).

[Change path creation]
The replacement path generation processing procedure Calculate_Path_From_Origin_To_Destination is as follows.

[Calculate_Path_From_Origin_To_Destination]
(1) Execute Calculate_Perm_Manhattan.
(2) Execute Calculate_Perm_Path.
(3) Execute Divide_Path.

  Hereinafter, three processing procedures of Calculate_Perm_Manhattan, Calculate_Perm_Path, and Divide_Path will be described. First, Calculate_Perm_Manhattan will be described.

  Calculate_Perm_Manhattan is to calculate the Manhattan distance δp [i] of each robot i from the robot destination.

[Calculate_Perm_Manhattan]
(1) Prepare next_p [a] [i] at the position (Xr [i], Yr [i], Zr [i]) of each robot i in G, and prepare another_p [a] [i] in the direction of the adjacent action a. If there is a robot, it is assumed that next_p [a] [i] 、 1, and otherwise it is assumed that next_p [a] [i] ← 0.
(2) The Manhattan distance Δp [i] at the position of each robot i is initialized to a value s_max larger than the number of grids in G.
(3) Initialize the Manhattan distance δp [destination] of the position of the robot destination to 0.
(4) For all robots i and action a, when the value of next_p [a] [i] is not 0, the Manhattan distance δp [of robot j at the position moved from the position of robot i by action a Check j], and if the value obtained by adding 1 to the minimum value is smaller than the current δp [i], substitute that value into δp [i].
(5) Repeat (4) until there is no update of the δp [i] value in the process of (4) described above.

  Next, Calculate_Perm_Path will be described. Calculate_Perm_Path is for calculating a path from the robot origin to the robot destination.

[Calculate_Perm_Path]
(1) A variable storing the number of robots included in the path from the robot origin to the robot destination is set to trj_num, and the value is initialized to 0. The variable for storing the robot number in the path is p_trj [t] (t = 0 ...) and p_trj [0] = origin. Also, t = 0.
(2) When p_trj [t] = destination is not satisfied, the value of δp [j ′] among the adjacent robots j ′ moved by each action a from the robot p_trj [t] is δp [t] −1. Robot j ′ is selected and p_trj [t + 1] = j ′ is set. Let the action leading to the robot j 'be a' and let a_trj [t] = a '. Increment t.
(3) Repeat (2) until p_trj [t] = destination. When p_trj [t] = destination, the processing ends as trj_num = t + 1, a_trj [trj_num-1] = a_trj [trj_num-2].

  Finally, Divide_Path will be described. Divide_Path divides the path calculated by Calculate_Perm_Path for each linear component (see FIG. 8). In FIG. 8, the symbols for the line element 1, the line element 2, the corner element 1, the corner element 2, and the corner element 3 are omitted.

[Divide_Path]
(1) Storage variables of linear paths: path_perm_x [t], path_perm_y [t], path_perm_z [t]. Also, the corner number in the path and the variable storing the number are respectively corner [] and corner_num. path_perm_x [0] ← Xr [p_trj [0]], path_perm_y [0] ← Yr [p_trj [0]], path_perm_z [0] ← Zr [p_trj [0]], and perm_num ← 1, t ← 0, corner_num ← It is assumed that 0. Repeat (2) while t <trj_num-1.
(2) When a_trj [t] = a_trj [t + 1], path_perm_x [perm_num] ← Xr [p_trj [t + 1]], path_perm_y [perm_num] ← Yr [p_trj [t + 1]], path_perm_z [perm_num] ] ← Zr [p_trj [t + 1]], and perm_num and t are incremented. Otherwise, set corner [corner_num] ← perm_num and increment corner_num. After incrementing t, path_perm_x [perm_num] ← Xr [p_trj [t + 1]], path_perm_y [perm_num] ← Yr [p_trj [t + 1]], path_perm_z [perm_num] ← Zr [p_trj [t + 1] ] And increment perm_num.

[Void formation]
The two generated void positions are (void_perm_x [0], void_perm_y [0], void_perm_z [0]), (void_perm_x [1], void_perm_y [1], void_perm_z [1]), and the void is generated. Let the taken out robots be robots out_0 and out_1.

  Hereinafter, a void generation processing procedure Void_Generation for generating two voids in G will be described. Void_Generation is realized using Move_Module and Record_History described later. Move_Module (i, vx, vy, vz) moves the robot i in one of X, Y, and Z directions by a predetermined amount (vx, vy, vz), and Record_History is described above. As a result, the position of each robot i in the time counter tp is recorded.

[Void_Generation]
(1) Select one robot unit surface not touching another robot unit position or obstacle in G and set it as Ss. Let the robot unit with Ss be Ms. Let im [0], im [1], im [2], and im [3] be the four robots belonging to G that touch Ss (hereinafter referred to as Ss for simplicity). The direction in which Ss is facing (the direction of the normal of Ss that faces outward from the robot unit position Ms) is defined as. In addition, as takes the value of 1-6, and the meaning shall be based on [Definition of robot operation]. For example, as = 1 means the positive direction of the X axis in the three-dimensional space. (void_perm_x [0], void_perm_y [0], void_perm_z [0]), (void_perm_x [1], void_perm_y [1], void_perm_z [1]) are values outside G. Let t_void 0 0. Note that t_void is a variable used in Update_Void_Navigation described later.
(2) If the robot im [i '] belonging to Ss at a position opposite to the direction as as from the robot im [i'] is jm [i '], the robot im [i'], The robot out_0 and out_1 are selected by selecting ones in which neither jm [i '] is included in the path (path_perm_x [t], path_perm_y [t], path_perm_z [t]). The positions of the robots out_0 and out_1 are stored in variables (void_buffer_x [0], void_buffer_y [0], void_buffer_z [0]), (void_buffer_x [1], void_buffer_y [1], void_buffer_z [1]).
(3) The following control is performed on the robots out_0 and out_1 according to the value of as.
When as = 1:
(3.1) Execute Move_Module (out_0, 1, 0, 0), Move_Module (out_1, 1, 0, 0) and execute Record_History.
(3.2) If Zr [out_0]% 2 = 1,
Then, Move_Module (out_0, 0, 0, -1) is executed.
Execute Else, Move_Module (out_0, 0, 0, 1).
(3.3) Execute Record_History.
(3.4) Execute Move_Module (out_1, 1, 0, 0).
When as = 2:
(3.1) Execute Move_Module (out_0, 0, 1, 0), Move_Module (out_1, 0, 1, 0), and execute Record_History.
(3.2) If Xr [out_0]% 2 = 1,
Then, Move_Module (out_0, -1, 0, 0) is executed.
Execute Else, Move_Module (out_0, 1, 0, 0).
(3.3) Execute Record_History.
(3.4) Execute Move_Module (out_1, 0, 1, 0).
When as = 3:
(3.1) Execute Move_Module (out_0, -1, 0, 0), Move_Module (out_1, -1, 0, 0) and execute Record_History.
(3.2) If Zr [out_0]% 2 = 1,
Then, Move_Module (out_0, 0, 0, -1) is executed.
Execute Else, Move_Module (out_0, 0, 0, 1).
(3.3) Execute Record_History.
(3.4) Execute Move_Module (out_1, -1, 0, 0).
When as = 4:
(3.1) Execute Move_Module (out_0, 0, -1, 0) and Move_Module (out_1, 0, -1, 0) to execute Record_History.
(3.2) If Xr [out_0]% 2 == 1,
Then, Move_Module (out_0, -1, 0, 0) is executed.
Execute Else, Move_Module (out_0, 1, 0, 0).
(3.3) Execute Record_History.
(3.4) Execute Move_Module (out_1, 0, -1, 0).
When as = 5:
(3.1) Execute Move_Module (out_0, 0, 0, 1), Move_Module (out_1, 0, 0, 1) and execute Record_History.
(3.2) If Yr [out_0]% 2 == 1,
Then, Move_Module (out_0, 0, -1, 0) is executed.
Execute Else, Move_Module (out_0, 0, 1, 0).
(3.3) Execute Record_History.
(3.4) Execute Move_Module (out_1, 0, 0, 1).
When as = 6:
(3.1) Execute Move_Module (out_0, 0, 0, -1) and Move_Module (out_1, 0, 0, -1) to execute Record_History.
(3.2) If Yr [out_0]% 2 == 1,
Then, Move_Module (out_0, 0, -1, 0) is executed.
Execute Else, Move_Module (out_0, 0, 1, 0).
(3.3) Execute Record_History.
(3.4) Execute Move_Module (out_1, 0, 0, -1).
(4) Execute Record_History.
(5) (void_perm_x [0], void_perm_y [0], void_perm_z [0]), (void_perm_x [1], void_perm_y [1], void_perm_z [1]) to (void_buffer_x [0], void_buffer_y [0], void_buffer_ 0]), stores the values of (void_buffer_x [1], void_buffer_y [1], void_buffer_z [1]). That is, the positions of the two voids to be generated coincide with the positions of the robots out_0 and out_1 specified in (2).
(6) The robot out_0 position is (escape_cube_buffer_x [0], escape_cube_buffer_y [0], escape_cube_buffer_z [0]), the robot out_1 position is (escape_cube_buffer_x [1], escape_cube_buffer_y [1], escape_cube_buffer_z [1]) To ring. That is, (escape_cube_buffer_x [0], escape_cube_buffer_y [0], escape_cube_buffer_z [0]), (escape_cube_buffer_x [1], escape_cube_buffer_y [1], escape_cube_buffer_z [1]) stores the positions at which the robot out_0, out_1 is saved. Ru.

[Move_Module (i, vx, vy, vz)]
(1) The robot i is moved by vx in the X direction, vy in the Y direction, and vz in the Z direction. However, only one component of vx, vy, and vz is a non-zero value.
(2) When the positions of two voids (void_perm_x [0], void_perm_y [0], void_perm_z [0]), (void_perm_x [1], void_perm_y [1], void_perm_z [1]) have values in G, As the robot i moves, the position of the corresponding void is moved.

[Record_History]
(1) Store the current position of each robot i in (permutation_x [tp] [i], permutation_y [tp] [i], permutation_z [tp] [i]), and increment tp.
(2) Set movable_num ← 0. Note that movable_num is a variable used in Add_Movable described later.

Swap control
Control to swap the position of the robot origin and the position of the robot destination is
(α) Move the robot origin to the position of the robot destination.
(β) Move the robot destination to the original position of the robot origin.
Consists of two steps. With the movement of (α), robots other than robot origin and robot destination are forced to move, and their positions also change, but with (β) movement, all those positions are restored. Be

  As described above, paths divided by Divide_Path are as shown in FIG. Stored in p_trj [t] is the number of the t-th robot included in the path connecting the robot origin and the robot destination. Further, the t-th position of the path obtained by removing the robot at the corner from the path by Divide_Path is stored in (path_perm_x [t], path_perm_y [t], path_perm_z [t]). corner [j] is the start point number of the j + 1-th straight line portion.

The robot position stored in (path_perm_x [t], path_perm_y [t], path_perm_z [t]) can be divided into a line element, a final line element, and a corner element using corner [j] or the like.
(Line element j)
The robot position stored in (path_perm_x [t], path_perm_y [t], path_perm_z [t]) of t = 0 to corner [0] -1 when j = 0.
The robot position stored in (path_perm_x [t], path_perm_y [t], path_perm_z [t]) from t = corner [j-1] to corner [j] -1 when 0 <j <corner_num.
Robots stored in (path_perm_x [t], path_perm_y [t], path_perm_z [t]) of t = corner [j-1] to perm_num-2 when j = corner_num and corner [j] <perm_num-2 position.
(Final line element)
Robot position (corner element j) stored in (path_perm_x [t], path_perm_y [t], path_perm_z [t]) of t = perm_num-2 to perm_num-1
The robot position stored in (path_perm_x [t], path_perm_y [t], path_perm_z [t]) of t = corner [j] -1 to corner [j]. The first replacement control processing procedure Robot_Exchange_1, second The replacement control processing procedure of the robot Robot_Exchange_2 will be described. First, Robot_Exchange_1 will be described. Robot_Exchange_1 realizes the control to move the above (α) robot origin to the position of the robot destination, and the end position of each element in the line element, corner element, and final line element where the robot origin exists. It is done by exchanging the position of the robot and the robot origin. The actual control method is as follows.

[Robot_Exchange_1]
(1) With i_l, t 0 0, the following control is performed for all values of i_c of counters i_c = 0 to corner_num-1.
If t! = Corner [i_c] -1,
Then, (no robot origin at the start of the corner element)
Execute Line_Perm (i_l, 0) to swap the robot positions at the start and end positions of line element i_l.
Execute Corner_Perm (i_c, 0) and replace the position of the robot at the position of the start point and the end point of the corner element i_c. t ← corner [i_c]. Increment i_l.
Else, (The robot origin is already at the start of the corner element)
Execute Corner_Perm (i_c, 0) and exchange the position of the robot at the position of the start point and the end point of the corner element i_c. t ← corner [i_c].
// Separate and replace only the remaining 2 squares in the last part
(2) Execute the following control.
If corner [corner_num-1]! = Perm_num-1,
Then, If corner [corner_num-1]! = Perm_num-2,
Then,
Execute Line_Perm (i_l, 0).
Execute Last_Line_Perm to swap the robot positions at the start and end positions of the last line element.
Else,
Execute Last_Line_Perm to swap the robot positions at the start point and end point of the last line element.

  Note that although the second argument of Line_Perm and Corner_Perm is 0, this indicates a flag (_flg), and is set to 1 when Line_Perm and Corner_Perm are called in Robot_Exchange_2.

  Next, Robot_Exchange_2 will be described. Robot_Exchange_2 realizes the control to move the above-mentioned (β) robot destination to the position where the robot origin originated.In the line element and corner element where the robot destination exists, the robot destination is set to the start position of each element. This is done by swapping the position of a robot and a robot destination. The actual control method is as follows.

[Robot_Exchange_2]
(1) If corner [corner_num-1]! = Perm_num-1 && corner [corner_num-1]! = Execute perm_num-2, Then, Line_Perm (i_l, 1). Decrement i_l.
(2) The following control is executed for all the values of i_c of the counter i_c = corner_num-1 to 0.
(2.1) If i_c> 0 Then,
If corner [i_c-1]! = Corner [i_c] -1,
Then, (There is no robot destination at the end of the corner element)
If perm_num-1> corner [i_c], Then,
Execute Corner_Perm (i_c, 1).
Execute Line_Perm (i_l, 1).
Set t ← corner [i_c] and decrement i_l.
Else,
If perm_num-1> corner [i_c],
Then, (If the corner element is the last element, do not replace it on the return.)
Execute Corner_Perm (i_c, 1).
Let t corn corner [i_c].
Else,
If 0! = Corner [i_c] -1, Then,
If perm_num-1> corner [i_c], Then,
Execute Corner_Perm (0, 1).
Execute Line_Perm (0, 1).
Else,
If perm_num-1> corner [i_c], Then,
Execute Corner_Perm (0, 1).

  The exchange control procedure Robot_Exchange for integrating the above and exchanging the positions of all robots is processed as follows.

[Robot_Exchange]
(1) Execute Robot_Exchange_1.
(2) Execute Robot_Exchange_2.

  In Robot_Exchange_1 and Robot_Exchange_2, Line_Perm and Corner_Perm were used to replace robots in line elements and corner elements. The details will be described in [Robot Relocation at Line Elements] and [Robot Relocation at Corner Elements] below.

[Robot position change with line element]
The replacement of the robot position in the line element is performed as shown in FIG. 9 using a robot adjacent to the line element as a buddy robot (hereinafter also simply referred to as a buddy). The buddy is an adjacent robot in the Y direction when the line element is in the X-axis direction, an adjacent robot in the Z direction when the line element is in the Y-axis direction, or an X direction when the line element is in the Z-axis direction. Use the number of adjacent robots two less than the number of robots in the line element.

  At the start of robot position exchange within the line element, the positions of the two voids are moved to positions adjacent to the line element start position and the second position of the line element. The positions of two voids are also similar to the buddy, when the line element is in the X-axis direction, the adjacent position in the Y direction, when the line element is in the Y-axis direction, the adjacent position in the Z direction, and the line element is the Z axis If it is oriented, use two adjacent positions in the X direction. The in-line element robot, the void and the buddy robot all lie in the same plane. (In other words, they exist in the XY plane when the line element is in the X-axis direction, in the YZ plane when the line element is in the Y-axis direction, and in the ZX plane when the line element is in the Z-axis direction.

  Assuming that the number of robots in the line element is nm + 2, the exchange of the robot positions at the start position and the end position ends in 2 * nm + 6 exchange operations. Replacement of the robot position in the final line element is performed in the same manner when nm = 0. Once this replacement operation is performed, the position of the robot that was in the buddy position and the position of the robot in the line element other than the start point and end point are replaced. By performing the replacement operation again, these robot positions are restored to their original positions. Return to position. That is, in the control of (α) in which the robot origin moves to the position of the robot destination and in the control of (β) in which the robot origin moves to the position of the robot destination, replacement operations with the same line element are performed once each. Through the control of (α) and (β), there is no change in the position of the robot other than the start point position and the end point position. In the case of nm = 0, that is, in the case of replacement of the last line element, replacement control in the last line element is performed only by (α), but only the void position except for robot positions other than the start and end points There is no problem because there is not.

The process of replacement control with line elements is as follows.
[Line_Perm (i_l, _flg)]
(1) Line_Perm_By_Position (_s, _g, _flg) is executed with the start point position number of the line element i_l as _s and the end point position number as _g.

[Last_Line_Perm]
(1) Line_Perm_By_Position (perm_num-2 perm_num-1, _flg) is executed with _flg = 0.

[Line_Perm_By_Position (_s, _g, _flg)]
(1) It is assumed that direction 要素 1 when the direction of the line element is in the X direction, direction ← 2 when the direction of the line element is in the Y direction, and direction ← 3 when the direction of the line element is in the Z direction.
(2) Two void target positions at the start of replacement operation (l_x [0], l_y [0], l_z [0]) x (path_perm_x [_s], path_perm_y [_s], path_perm_z [_s]), (l_x [l] 1], l_y [1], l_z [1]) ← (path_perm_x [_s + 1], path_perm_y [_s + 1], path_perm_z [_s + 1]).
(3) The following is performed according to the value of the direction (corresponding to setting of the void target position according to the direction of the line element).
(3.1) When direction = 1:
If l_y [1] is an odd number, Then, l_y [0], l_y [1] is decremented. Set _p_l ← -1.
Increment Else, l_y [0], l_y [1]. Set _p_l ← 1.
When (3.2) direction = 2:
If l_z [1] is an odd number, Then decrement l_z [0], l_z [1]. Set _p_l ← -1.
Increment Else, l_z [0], l_z [1]. Set _p_l ← 1.
(3.3) When direction = 3:
If l_x [1] is an odd number, Then, l_x [0], l_x [1] is decremented. Set _p_l ← -1.
Increment Else, l_x [0], l_x [1]. Set _p_l ← 1.
(4) If _flg = 0, Then,
Execute Navigate_Void (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1]).
Else,
Execute Reverse_Void_To (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1]).
(5) Execute Before_Care (_s, _g, direction, _p_l).
(6) Rotation_in_Line (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], direction, _p_l) is executed.

  Note that Navigate_Void and Reverse_Void_To will be described later in [Void control], and Before_Care will be described later in [control of shunt robot].

[Rotation_in_Line (_s, _g, _x0, _y0, _z0, _x1, _y1, _z1, _d, _p_l)]
(1) Let index_rot [r] (r = 0, 1, ..., 2 * nm + 1) be a serial number set for the in-line element robot and buddy robot (see Fig. 9), r = nm to 2 * nm + 1 Set the value of index_rot [r] to the robot number in (path_perm_x [_s + (r-nm)], path_perm_y [_s + (r-nm)], path_perm_z [_s + (r-nm)]) (Corresponds to the robot serial number in the line element).
(2) When _vx ← 0, _vy ← 0, _vz ← 0, and _d = 1, the value of _p_l is added to _vy. When _d = 2, the value of _p_l is added to _vz. When _d = 3, the value of _p_l is added to _vx.
(3) Robots whose index_rot [r] values are (path_perm_x [_g-r] + _vx, path_perm_y [_g-r] + _ vy, path_perm_z [_g-r] + _vz) for r = 0 to nm-1 Set to the number (corresponds to the buddy robot serial number).
(4) When _d = 1, the Rotation_X_Line (_p_l) is executed. When _d = 2, the Rotation_Y_Line (_p_l) is executed. When _d = 3, the Rotation_Z_Line (_p_l) is executed.

  Hereinafter, the Rotation_X_Line, the Rotation_Y_Line, and the Rotation_Z_Line will be described with reference to FIG. For Add_Movable and Evacuating_Cube_Control, check whether the robot movement that you are trying to execute with Move_Module does not cause disconnection of the two save robots out_0 and out_1 from other robots, and change the save robot's position if it causes it. This realizes a function for avoiding disconnection. Details will be explained in [Control of retractable robot].

[Rotation_X_Line (_p_l)]
(1) Set _g_p_l ← 1 when the line element is in the positive direction. Set _g_p_l ← -1 when the line element is in the negative direction.
(2) Execute Add_Movable (index_rot [nm], 0, _p_l, 0). Execute Evacuating_Cube_Control.
(3) Execute Move_Module (index_rot [nm], 0, _p_l, 0). Execute Record_History (FIG. 9 operation (a)).
(4) Execute Add_Movable (index_rot [r], -_g_p_l, 0, 0) for all r of r = nm + 1 to 2 * nm + 1. Then execute Evacuating_Cube_Control.
(5) Execute Move_Module (index_rot [r], -_g_p_l, 0, 0) for all r of r = nm + 1 to 2 * nm + 1. Record_History is executed (operation (b) in FIG. 9).
(6) Execute Add_Movable (index_rot [nm], _g_p_l, 0, 0). Execute Evacuating_Cube_Control.
(7) Execute Move_Module (index_rot [nm], _g_p_l, 0, 0). Record_History is executed (FIG. 9, operation (c)).
(8) The following is repeated until the counter j = 1 to nm.
(8.1) Execute Add_Movable (index_rot [nm + j], 0, _p_l, 0).
Execute Add_Movable (index_rot [j-1], 0, -_p_l, 0).
Execute Evacuating_Cube_Control.
(8.2) Run Move_Module (index_rot [nm + j], 0, _p_l, 0).
Run Move_Module (index_rot [j-1], 0, -_p_l, 0).
Execute Record_History (FIG. 9, operation (d)).
(8.3) r = nm + j + 1 to 2 * nm + 1 for all r
Execute Add_Movable (index_rot [r], -_g_p_l, 0, 0).
At all r of r = 0 to j-1,
Execute Add_Movable (index_rot [r], -_g_p_l, 0, 0).
At all r of r = j to nm + j,
Execute Add_Movable (index_rot [r], _g_p_l, 0, 0).
Execute Evacuating_Cube_Control (movable_num).
(8.4) r = nm + j + 1 to 2 * nm + 1 for all r
Run Move_Module (index_rot [r], -_g_p_l, 0, 0).
at all r of r = 0 to j-1
Run Move_Module (index_rot [r], -_g_p_l, 0, 0).
at all r of r = j to nm + j
Execute Move_Module (index_rot [r], _g_p_l, 0, 0).
Execute Record_History (Operation (e) of FIG. 9).
(9) Execute Add_Movable (index_rot [nm], 0, -_p_l, 0). Execute Evacuating_Cube_Control.
(10) Execute Move_Module (index_rot [nm], 0, -_p_l, 0). Record_History is executed (operation (f) in FIG. 9).
(11) After executing Add_Movable (index_rot [r], _g_p_l, 0, 0) for all r of r = nm + 1 to 2 * nm, execute Evacuating_Cube_Control.
(12) Move_Module (index_rot [r], _g_p_l, 0, 0) is executed for all r of r = nm + 1 to 2 * nm, and then Record_History is executed (FIG. 9, operation (g)).

[Rotation_Y_Line (_p_l)]
(1) When the line element is in the positive direction, _g_p_ll1. Set _g_p_l ← -1 when the line element is in the negative direction.
(2) Execute Add_Movable (index_rot [nm], 0, 0, _p_l). Execute Evacuating_Cube_Control.
(3) Execute Move_Module (index_rot [nm], 0, 0, _p_l). Record_History is executed (operation (a) in FIG. 9).
(4) Execute Add_Movable (index_rot [r], 0, -_g_p_l, 0) for all r of r = nm + 1 to 2 * nm + 1. Then execute Evacuating_Cube_Control.
(5) Execute Move_Module (index_rot [r], 0, -_g_p_l, 0) for all r of r = nm + 1 to 2 * nm + 1. Execute Record_History (Operation (b) in FIG. 9).
(6) Execute Add_Movable (index_rot [nm], 0, _g_p_l, 0). Execute Evacuating_Cube_Control.
(7) Execute Move_Module (index_rot [nm], 0, _g_p_l, 0). Record_History is executed (FIG. 9, operation (c)).
(8) The following is repeated until the counter j = 1 to nm.
(8.1) Execute Add_Movable (index_rot [nm + j], 0, 0, _p_l).
Execute Add_Movable (index_rot [j-1], 0, 0, -_p_l).
Execute Evacuating_Cube_Control.
(8.2) Execute Move_Module (index_rot [nm + j], 0, 0, _p_l).
Run Move_Module (index_rot [j-1], 0, 0, -_p_l).
Execute Record_History (FIG. 9, operation (d)).
(8.3) r = nm + j + 1 to 2 * nm + 1 for all r
Execute Add_Movable (index_rot [r], 0, -_g_p_l, 0).
At all r of r = 0 to j-1,
Execute Add_Movable (index_rot [r], 0, -_g_p_l, 0).
At all r of r = j to nm + j,
Execute Add_Movable (index_rot [r], 0, _g_p_l, 0).
Execute Evacuating_Cube_Control (movable_num).
(8.4) r = nm + j + 1 to 2 * nm + 1 for all r
Execute Move_Module (index_rot [r], 0, -_g_p_l, 0).
At all r of r = 0 to j-1,
Execute Move_Module (index_rot [r], 0, -_g_p_l, 0).
For all r from r = j to nm + j
Execute Move_Module (index_rot [r], 0, _g_p_l, 0).
Execute Record_History. (FIG. 9 operation (e)).
(9) Execute Add_Movable (index_rot [nm], 0, 0, -_p_l). Execute Evacuating_Cube_Control.
(10) Execute Move_Module (index_rot [nm], 0, 0, -_p_l). Record_History is executed (FIG. 9, operation (f)).
(11) After executing Add_Movable (index_rot [r], 0, _g_p_l, 0) for all r of r = nm + 1 to 2 * nm, execute Evacuating_Cube_Control.
(12) Move_Module (index_rot [r], 0, _g_p_l, 0) is executed for all r of r = nm + 1 to 2 * nm, and then Record_History is executed (FIG. 9, operation (g)).

[Rotation_Z_Line (_p_l)]
(1) Set _g_p_l ← 1 when the line element is in the positive direction. When the line element is in the negative direction, _g_p_l -1 -1.
(2) Execute Add_Movable (index_rot [nm], _p_l, 0, 0). Execute Evacuating_Cube_Control.
(3) Execute Move_Module (index_rot [nm], _p_l, 0, 0). Execute Record_History (FIG. 9 operation (a)).
(4) Execute Add_Movable (index_rot [r], 0, 0, -_g_p_l) for all r of r = nm + 1 to 2 * nm + 1. After that, Evacuating_Cube_Control is executed.
(5) Execute Move_Module (index_rot [r], 0, 0, -_g_p_l) for all r of r = nm + 1 to 2 * nm + 1. Record_History is executed (operation (b) in FIG. 9).
(6) Execute Add_Movable (index_rot [nm], 0, 0, _g_p_l). Execute Evacuating_Cube_Control.
(7) Execute Move_Module (index_rot [nm], 0, 0, _g_p_l). Record_History is executed (operation (c) in FIG. 9).
(8) The following is repeated until the counter j = 1 to nm.
(8.1) Execute Add_Movable (index_rot [nm + j], _p_l, 0, 0).
Execute Add_Movable (index_rot [j-1], -_p_l, 0, 0).
Execute Evacuating_Cube_Control.
(8.2) Run Move_Module (index_rot [nm + j], _p_l, 0, 0).
Move_Module (index_rot [j-1], -_p_l, 0, 0) is executed.
Execute Record_History (FIG. 9, operation (d)).
(8.3) r = nm + j + 1 to 2 * nm + 1 for all r
Execute Add_Movable (index_rot [r], 0, 0, -_g_p_l).
At all r of r = 0 to j-1,
Execute Add_Movable (index_rot [r], 0, 0, -_g_p_l).
For all r from r = j to nm + j
Execute Add_Movable (index_rot [r], 0, 0, _g_p_l).
Execute Evacuating_Cube_Control (movable_num).
(8.4) r = nm + j + 1 to 2 * nm + 1 for all r
Run Move_Module (index_rot [r], 0, 0, -_g_p_l).
At all r of r = 0 to j-1,
Run Move_Module (index_rot [r], 0, 0, -_g_p_l).
At all r of r = j to nm + j,
Move_Module (index_rot [r], 0, 0, _g_p_l) is executed.
Execute Record_History (Operation (e) of FIG. 9).
(9) Execute Add_Movable (index_rot [nm], -_p_l, 0, 0). Execute Evacuating_Cube_Control.
(10) Execute Move_Module (index_rot [nm], -_p_l, 0, 0). Record_History is executed (FIG. 9, operation (f)).
(11) After executing Add_Movable (index_rot [r], 0, 0, _g_p_l) for all r of r = nm + 1 to 2 * nm, execute Evacuating_Cube_Control.
(12) After performing Move_Module (index_rot [r], 0, 0, _g_p_l) for all r of r = nm + 1 to 2 * nm, execute Record_History (Operation (g) in FIG. 9).

[Robot position change at corner element]
FIG. 10 shows an operation of exchanging the robot positions at the corner elements. One of the voids is in contact with both of the two robot positions belonging to the corner element, and the other void is in contact with the other void in the direction perpendicular to the plane to which the two robot positions belonging to the corner element belong . In the corner element replacement operation, the positions of the robots other than the replacement target robot do not change before and after the replacement operation. The robot repositioning process at the corner element is as follows.

[Corner_Perm (i_c, _flg)]
(1) _s ← corner [i_c] -1, _g ← corner [i_c].
(2) If path_perm_x [_s] = path_perm_x [_g], Then,
_d ← 1.
If path_perm_x [_s] is an odd number, Then, _p_l = -1, Else _p_l = 1.
If path_perm_y [_s] = path_perm_y [_g], Then,
_d ← 2.
If path_perm_y [_s] is odd, Then, _p_l = -1, Else _p_l = 1.
If path_perm_z [_s] = path_perm_z [_g], Then,
_d ← 3.
If path_perm_z [_s] is an odd number, Then, _p_l = -1, Else _p_l = 1.
(3) For the two void target positions (l_x [0], l_y [0], l_z [0]), (l_x [1], l_y [1], l_z [1]) Set as follows depending on the value.
When _d = 1:
(3.1) l_x [0] ← path_perm_x [_s], l_x [1] ← l_x [0] + _ p_l.
(3.2) The robot exists at the position (l_x [0], path_perm_y [_s], path_perm_z [_g]) or one of the two current void positions (void_perm_x [], void_perm_y [], void_perm_z []) If there is a character, let l_y [0] [path_perm_y [_s], l_z [0] ← path_perm_z [_g].
(3.3) If the value of l_y [0], l_z [0] is not set in (3.2), the robot exists at the position (l_x [0], path_perm_y [_g], path_perm_z [_s]) Alternatively, if one of two current void positions (void_perm_x [], void_perm_y [], void_perm_z []) exists, l_y [0] ← path_perm_y [_g], l_z [0] ← path_perm_z [_s ].
(3.4) Let l_y [1] ← l_y [0], l_z [1] ← l_z [0].
When _d = 2:
(3.1) l_y [0] ← path_perm_y [_s], l_y [1] ← l_y [0] + _ p_l.
(3.2) The robot exists at the position (path_perm_x [_s], l_y [0], path_perm_z [_g]) or one of the two current void positions (void_perm_x [], void_perm_y [], void_perm_z []) Is present, l_x [0] ← path_perm_x [_s], l_z [0] ← path_perm_z [_g].
(3.3) If the values of l_x [0] and l_z [0] are not set in (3.2), does the robot exist at the position (path_perm_x [_g], l_y [0], path_perm_z [_s]), Or, if one of the two current void positions (void_perm_x [], void_perm_y [], void_perm_z []) exists, l_x [0] ← path_perm_x [_g], l_z [0] ← path_perm_z [_s ].
(3.4) Let l_x [1] ← l_x [0], l_z [1] ← l_z [0].
When _d = 3:
(3.1) l_z [0] ← path_perm_z [_s], l_z [1] ← l_z [0] + _ p_l.
(3.2) The robot exists at the position (path_perm_x [_s], path_perm_y [_g], l_z [0]) or one of the two current void positions (void_perm_x [], void_perm_y [], void_perm_z []) If there exists a parameter, l_x [0] ← path_perm_x [_s], l_y [0] ← path_perm_y [_g].
(3.3) If the values of l_x [0] and l_y [0] are not set in (3.2), does the robot exist at the position (path_perm_x [_g], path_perm_y [_s], l_z [0]), Or, if one of the two current void positions (void_perm_x [], void_perm_y [], void_perm_z []) exists, l_x [0] ← path_perm_x [_g], l_y [0] ← path_perm_y [_s ].
(3.4) Let l_x [1] ← l_x [0], l_y [1] ← l_y [0].
(4) If _flg = 0, Then,
Execute Navigate_Void (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1]).
Else,
Reverse_Void_To (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1]) is executed.
(5) At_Corner (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l) is executed.

[At_Corner (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l)]
(1) When _d = 1, At_Corner_X (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l) Run.
When _d = 2, At_Corner_Y (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l) is executed.
When _d = 3, At_Corner_Z (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l) is executed.

[At_Corner_X (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l)]
(1) The robot number at position (path_perm_x [_s], path_perm_y [_s], path_perm_z [_s]) is i_s, and the position of the robot at position (path_perm_x [_g], path_perm_y [_g], path_perm_z [_g]) Let the number be i_g. (_sx, _sy, _sz) ((Xr [i_s], Yr [i_s], Zr [i_s]), (_gx, _gy, _gz) ((Xr [i_g], Yr [i_g], Zr [i_g]) and Do.
(2) Execute Add_Movable (i_s, 0, l_y [0] -_ sy, l_z [0] -_ sz) and execute Evacuating_Cube_Control.
(3) Execute Move_Module (i_s, 0, l_y [0] -_ sy, l_z [0] -_ sz). Execute Record_History (FIG. 10 operation (a)).
(4) Execute Add_Movable (i_s, _p_l, 0, 0). Execute Evacuating_Cube_Control.
(5) Execute Move_Module (i_s, _p_l, 0, 0). Execute Record_History (Operation (b) in FIG. 10).
(6) Execute Add_Movable (i_g, 0, l_y [0] -_ gy, l_z [0] -_ gz). Execute Evacuating_Cube_Control.
(7) Execute Move_Module (i_g, 0, l_y [0] -_ gy, l_z [0] -_ gz). Record_History is executed (operation (c) in FIG. 10).
(8) Execute Add_Movable (i_g, 0, _sy-l_y [0], _sz-l_z [0]). Execute Evacuating_Cube_Control.
(9) Execute Move_Module (i_g, 0, _sy-l_y [0], _sz-l_z [0]). Record_History is executed (operation (d) in FIG. 10).
(10) Execute Add_Movable (i_s, -_p_l, 0, 0). Execute Evacuating_Cube_Control.
(11) Execute Move_Module (i_s, -_p_l, 0, 0). Execute Record_History (FIG. 10, operation (e)).
(12) Execute Add_Movable (i_s, 0, _gy-l_y [0], _gz-l_z [0]). Execute Evacuating_Cube_Control.
(13) Execute Move_Module (i_s, 0, _gy-l_y [0], _gz-l_z [0]). Execute Record_History (Operation (f) in FIG. 10).

[At_Corner_Y (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l)]
(1) The robot number at position (path_perm_x [_s], path_perm_y [_s], path_perm_z [_s]) is i_s, and the position of the robot at position (path_perm_x [_g], path_perm_y [_g], path_perm_z [_g]) Let the number be i_g. (_sx, _sy, _sz) ← (Xr [i_s], Yr [i_s], Zr [i_s]), (_gx, _gy, _gz) ← (Xr [i_g], Yr [i_g], Zr [i_g]) Do.
(2) Execute Add_Movable (i_s, l_x [0] -_ sx, 0, l_z [0] -_ sz) and execute Evacuating_Cube_Control.
(3) Execute Move_Module (i_s, l_x [0] -_ sx, 0, l_z [0] -_ sz). Record_History is executed (operation (a) in FIG. 10).
(4) Execute Add_Movable (i_s, 0, _p_l, 0). Execute Evacuating_Cube_Control.
(5) Execute Move_Module (i_s, 0, _p_l, 0). Record_History is executed (operation (b) in FIG. 10).
(6) Execute Add_Movable (i_g, l_x [0] -_ gx, 0, l_z [0] -_ gz). Execute Evacuating_Cube_Control.
(7) Execute Move_Module (i_g, l_x [0] -_ gx, 0, l_z [0] -_ gz). Record_History is executed (operation (c) in FIG. 10).
(8) Execute Add_Movable (i_g, _sx-l_x [0], 0, _sz-l_z [0]). Execute Evacuating_Cube_Control.
(9) Execute Move_Module (i_g, _sx-l_x [0], 0, _sz-l_z [0]). Execute Record_History (FIG. 10, operation (d)).
(10) Execute Add_Movable (i_s, 0, -_p_l, 0). Execute Evacuating_Cube_Control.
(11) Execute Move_Module (i_s, 0, -_p_l, 0). Execute Record_History (FIG. 10, operation (e)).
(12) Execute Add_Movable (i_s, _gx-l_x [0], 0, _gz-l_z [0]). Execute Evacuating_Cube_Control.
(13) Execute Move_Module (i_s, _gx-l_x [0], 0, _gz-l_z [0]). Record_History is executed (operation (f) in FIG. 10).

[At_Corner_Z (_s, _g, l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1], _d, _p_l)]
(1) The robot number at the position (path_perm_x [_s], path_perm_y [_s], path_perm_z [_s]) is i_s, and the robot at the position (path_perm_x [_g], path_perm_y [_g], path_perm_z [_g]) Let the number be i_g. (_sx, _sy, _sz) ← (Xr [i_s], Yr [i_s], Zr [i_s]), (_gx, _gy, _gz) ← (Xr [i_g], Yr [i_g], Zr [i_g]) Do.
(2) Execute Add_Movable (i_s, l_x [0] -_ sx, l_y [0] -_ sy, 0) and execute Evacuating_Cube_Control.
(3) Execute Move_Module (i_s, l_x [0] -_ sx, l_y [0] -_ sy, 0). Record_History is executed (operation (a) in FIG. 10).
(4) Execute Add_Movable (i_s, 0, 0, _p_l). Execute Evacuating_Cube_Control.
(5) Execute Move_Module (i_s, 0, 0, _p_l). Execute Record_History (Operation (b) in FIG. 10).
(6) Execute Add_Movable (i_g, l_x [0] -_ gx, l_y [0] -_ gy, 0). Execute Evacuating_Cube_Control.
(7) Execute Move_Module (i_g, l_x [0] -_ gx, 0, l_y [0] -_ gy, 0). Execute Record_History (Operation (c) in FIG. 10).
(8) Execute Add_Movable (i_g, _sx-l_x [0], _sy-l_y [0], 0). Execute Evacuating_Cube_Control.
(9) Execute Move_Module (i_g, _sx-l_x [0], _sy-l_y [0], 0). Execute Record_History (FIG. 10, operation (d)).
(10) Execute Add_Movable (i_s, 0, 0, -_p_l). Execute Evacuating_Cube_Control.
(11) Execute Move_Module (i_s, 0, 0, -_p_l). Execute Record_History (FIG. 10, operation (e)).
(12) Execute Add_Movable (i_s, _gx-l_x [0], _gy-l_y [0], 0). Execute Evacuating_Cube_Control.
(13) Execute Move_Module (i_s, _gx-l_x [0], 0, _gy-l_y [0], 0). Record_History is executed (operation (f) in FIG. 10).

[Void control]
It is necessary to move the two void positions to the initial position at the start of the robot replacement in the next element when the robot position replacement in the line element or corner element is finished and the robot replacement in the next element is started. is there. While executing Robot_Exchange_1, the position of some robots changes as the void moves, but when Robot_Exchange_2 is executed, they are controlled so that they are restored. The control of the void is performed by the aforementioned Navigate_Void and Reverse_Void_To. The control of the void while executing Robot_Exchange_1 is performed by Navigate_Void, and the control of the void while executing Robot_Exchange_2 is performed by reversely reproducing the history data of the void operation recorded by Navigate_Void. The void movement path is set so as not to pass all positions (path_perm_x [], path_perm_y [], path_perm_z []) on the robot repositioning path.

[Navigate_Void (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1])]
(1) ((void_perm_x [0], void_perm_y [0], void_perm_z [0]) = (l_x [0], l_y [0], l_z [0]) && (void_perm_x [1], void_perm_y [1], void_perm_z [1]) = (l_x [1], l_y [1], l_z [1]) || ((void_perm_x [0], void_perm_y [0], void_perm_z [0]) = (l_x [1], l_y [) 1], l_z [1]) && (void_perm_x [1], void_perm_y [1], void_perm_z [1]) = (l_x [0], l_y [0], l_z [0])), that is, two When the void position does not match both of the two target positions (l_x [], l_y [], l_z [])), execute (2) and below.
(2) Execute Void_Manhattan and calculate the Manhattan distance of each robot position from the current void position.
(3) Execute Void_Move (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1]) to move the void.

  Void_Manhattan is to calculate the Manhattan distance δv [i] of each robot position from the current void position.

[Void_Manhattan]
(1) Prepare next_p [a] [i] at the position (Xr [i], Yr [i], Zr [i]) of each robot i in G, and prepare another_p [a] [i] in the direction of the adjacent action a. If there is a robot or one of two current void positions (void_perm_x [], void_perm_y [], void_perm_z []), then next_p [a] [i] ← 1 and in the other cases next_p [ a] [i] ← 0.
(2) The Manhattan distance Δv [i] at the position of each robot i is initialized to a value s_max larger than the number of grids in G.
(3) For all robots i and action a, when next_p [a] [i] = 1, examine the Manhattan distance δv [j] of robot j at the position moved from the position of robot i by action a When the value obtained by adding 1 to the minimum value is smaller than the current Δp [i], the value is substituted into Δv [i]. In addition, when there is a void at the position moved from the position of the robot i by the action a, 1 is substituted into Δv [i].
(4) In the process of (3) described above, (3) is repeated until there is no update of the δv [i] value.

  In Void_Move, the void is moved to the void target position in two cases (see FIGS. 11 and 12).

[Void_Move (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1])]
(1) When a robot exists in both of the void target positions (l_x [0], l_y [0], l_z [0]) and (l_x [1], l_y [1], l_z [1]), Among the robots, the larger one of the values of δv is _g_0, the smaller one is _g_1, and (2) to (7) are executed (for the explanation of each variable, see FIG. 11).
(2) A variable storing the number of robots included in the path leading from the robot_g_0 to the robot_g_1 to the current void position is set as trj_num, and the value is initialized to 2. The variable for storing the robot number in the path is p_trj [t] (t = 0,...), And p_trj [0] = _ g_0, p_trj [1] = _ g_1. Let t ← 2.
(3) When δv [p_trj [t-1]] is not 1, the value of δv [j '] is δv among the adjacent robots j' that have moved from robot p_trj [t-1] by action a. The robot j ′ that becomes [p_trj [t-1]] − 1 is selected, and p_trj [t] = j ′ is set. Increment t. Repeat (3). When δv [p_trj [t-1]] = 1, trj_num = t and the process ends.
(4) For all t from t = 2 to trj_num + 1, (_px [t], _py [t], _pz [t]) ← (Xr [p_trj [trj_num- (t-1)], Yr [p_trj [trj_num- (t-1)], Zr [p_trj [trj_num- (t-1)]]).
(5) If the void position (void_perm_x [0], void_perm_y [0], void_perm_z [0]) is adjacent to the position (_px [2], _py [2], _pz [2]), Then,
(_px [1], _py [1], _pz [1]) ((void_perm_x [0], void_perm_y [0], void_perm_z [0]),
(_px [0], _py [0], _pz [0]) ((void_perm_x [1], void_perm_y [1], void_perm_z [1]).
(6) If the void position (void_perm_x [1], void_perm_y [1], void_perm_z [1]) is adjacent to the position (_px [2], _py [2], _pz [2]), Then,
(_px [1], _py [1], _pz [1]) ((void_perm_x [1], void_perm_y [1], void_perm_z [1]),
(_px [0], _py [0], _pz [0]) ((void_perm_x [0], void_perm_y [0], void_perm_z [0]).
(7) Repeat the following at t = trj_num-1 to 0.
Repeat the following at j = 0-1.
(7.1) (_xd, _yd, _zd) ← (Xr [p_trj [t]], Yr [p_trj [t]], Zr [p_trj [t]]).
(7.2) Add_Movable (p_trj [t],
_px [(trj_num-1) -t + (1-j)] -_ px [(trj_num-1) -t + (2-j)],
_py [(trj_num-1) -t + (1-j)] -_ py [(trj_num-1) -t + (2-j)],
Execute _pz [(trj_num-1) -t + (1-j)] -_ pz [(trj_num-1) -t + (2-j)]).
Execute Evacuating_Cube_Control.
(7.3) Move_Module (p_trj [t],
_px [(trj_num-1) -t + (1-j)] -_ px [(trj_num-1) -t + (2-j)],
_py [(trj_num-1) -t + (1-j)] -_ py [(trj_num-1) -t + (2-j)],
Execute _pz [(trj_num-1) -t + (1-j)] -_ pz [(trj_num-1) -t + (2-j)]).
Execute Record_History.
(7.4) The action a of the robot p_trj [t] is updated with Update_Void_Navigation (_p_trj [t], a)
Record.
(8) When the robot exists only in one of the void target positions (l_x [0], l_y [0], l_z [0]), (l_x [1], l_y [1], l_z [1]) The robot is set to _g_0, and (9) to (15) are executed (for the explanation of each variable, see FIG. 12).
(9) The current void position that matches the void target position is stored in the buffer (_xd [0], _yd [0], _zd [0]), and the mismatched current void position is stored in the buffer ( _xd [1], _yd [1], _zd [1]).
(10) Add_Movable (_g_0, _xd [0] -Xr [_g_0], _yd [0] -Yr [_g_0], _zd [0] -Zr [_g_0]) is executed. Execute Evacuating_Cube_Control.
(11) Execute Move_Module (_g_0, _xd [0] -Xr [_g_0], _yd [0] -Yr [_g_0], _zd [0] -Zr [_g_0]). Execute Record_History.
(12) The operation a of the robot_g_0 is recorded by Update_Void_Navigation (_g_0, a).
(13) Add_Movable (_g_0, _xd [1] -Xr [_g_0], _yd [1] -Yr [_g_0], _zd [1] -Zr [_g_0]) is executed. Execute Evacuating_Cube_Control.
(14) Execute Move_Module (_g_0, _xd [1] -Xr [_g_0], _yd [1] -Yr [_g_0], _zd [1] -Zr [_g_0]). Execute Record_History.
(15) Record the action a of the robot _g_0 using Update_Void_Navigation (_g_0, a).

[Update_Void_Navigation (i, a)]
(1) Action a in the opposite direction to action a is a_inv.
(2) Set void_navi_dir [t_void] ← a_inv, void_navi_num [t_void] ← i.
(3) Increment t_void.
[Reverse_Void_To (l_x [0], l_y [0], l_z [0], l_x [1], l_y [1], l_z [1])]
(1) ((void_perm_x [0], void_perm_y [0], void_perm_z [0]) = (l_x [0], l_y [0], l_z [0]) && (void_perm_x [1], void_perm_y [1], void_perm_z [1]) = (l_x [1], l_y [1], l_z [1]) || ((void_perm_x [0], void_perm_y [0], void_perm_z [0]) = (l_x [1], l_y [) 1], l_z [1]) && (void_perm_x [1], void_perm_y [1], void_perm_z [1]) = (l_x [0], l_y [0], l_z [0])) (ie, two) Reverse_Void_Move is repeatedly executed until two void positions coincide with both of the two target positions (l_x [], l_y [], l_z []).

  In Reverse_Void_Move, the process of (2)-(4) performing the reverse playback of the void action history by the moving time step is executed. Note that the variables t_void and void_navi_dir [] are variables used in Update_Void_Navigation.

[Reverse_Void_Move]
(1) Decrement t_void.
(2)
When void_navi_dir [t_void] = 1:
Execute Add_Movable (void_navi_num [t_void], 1, 0, 0).
When void_navi_dir [t_void] = 3:
Execute Add_Movable (void_navi_num [t_void], -1, 0, 0).
When void_navi_dir [t_void] = 2:
Execute Add_Movable (void_navi_num [t_void], 0, 1, 0).
When void_navi_dir [t_void] = 4:
Execute Add_Movable (void_navi_num [t_void], 0, -1, 0).
When void_navi_dir [t_void] = 5:
Execute Add_Movable (void_navi_num [t_void], 0, 0, 1).
When void_navi_dir [t_void] = 6:
Execute Add_Movable (void_navi_num [t_void], 0, 0, -1).
(3) Execute Evacuating_Cube_Control.
(Four)
When void_navi_dir [t_void] = 1:
Execute Move_Module (void_navi_num [t_void], 1, 0, 0).
When void_navi_dir [t_void] = 3:
Execute Move_Module (void_navi_num [t_void], -1, 0, 0).
When void_navi_dir [t_void] = 2:
Execute Move_Module (void_navi_num [t_void], 0, 1, 0).
When void_navi_dir [t_void] = 4:
Execute Move_Module (void_navi_num [t_void], 0, -1, 0).
When void_navi_dir [t_void] = 5:
Execute Move_Module (void_navi_num [t_void], 0, 0, 1).
When void_navi_dir [t_void] = 6:
Execute Move_Module (void_navi_num [t_void], 0, 0, -1).
(5) Execute Record_History.

[Void removal]
In void elimination processing procedure Void_UnGeneration executed after the termination of Robot_Exchange, robots out_0 and out_1 that were saved outside G are returned into G. Before the execution of Void_UnGeneration, the position of the void has been returned to the position immediately after the void was generated. The robot's motion in void elimination is almost the reverse replay operation at the time of creation, but it is not always strictly the case because the position of the backup robot may change while executing Robot_Exchange. .

  Note that (escape_cube_buffer_x [0], escape_cube_buffer_y [0], escape_cube_buffer_z [0]), (escape_cube_buffer_x [1], escape_cube_buffer_y [1], escape_cube_buffer_z [1]) are the positions of robot out_0 that were evacuated in Void_Generation, respectively Is the position.

[Void_UnGeneration]
(1) Set the void position (void_perm_x [], void_perm_y [], void_perm_z []) to a value at any position outside G.
(2) (escape_cube_buffer_x [0], escape_cube_buffer_y [0], escape_cube_buffer_z [0]) is not at the robot out_0 position, (escape_cube_buffer_x [1], escape_cube_buffer_y [1], escape_cube_buffer_z [1]) is not equal to the robot out_1 position If this is the case, the following is executed to return the evacuation robot to the position at the time of void generation.
(2.1) as = 1 || When as = 3 (as is defined by Void_Generation):
If Yr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, 0, -1, 0).
Execute Move_Module (out_1, 0, -1, 0).
Execute Record_History.
Else,
Execute Move_Module (out_0, 0, 1, 0).
Execute Move_Module (out_1, 0, 1, 0).
Execute Record_History.
(2.2) as = 2 || When as = 4:
If Zr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, 0, 0, -1).
Execute Move_Module (out_1, 0, 0, -1).
Execute Record_History.
Else,
Execute Move_Module (out_0, 0, 0, 1).
Execute Move_Module (out_1, 0, 0, 1).
Execute Record_History.
(2.3) as = 5 || as = 6:
If Xr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, -1, 0, 0).
Execute Move_Module (out_1, -1, 0, 0).
Execute Record_History.
Else,
Execute Move_Module (out_0, 1, 0, 0).
Execute Move_Module (out_1, 1, 0, 0).
Execute Record_History.
(3) The retracting robot is stored in G by the following process.
(3.1) When as = 1:
Execute Move_Module (out_1, -1, 0, 0).
Execute Record_History.
If Zr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, 0, 0, -1).
Else,
Execute Move_Module (out_0, 0, 0, 1).
Execute Record_History.
Execute Move_Module (out_0, -1, 0, 0).
Execute Move_Module (out_1, -1, 0, 0).
Execute Record_History.
(3.2) When as = 2:
Execute Move_Module (out_1, 0, -1, 0).
Execute Record_History.
If Xr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, -1, 0, 0).
Else,
Execute Move_Module (out_0, 1, 0, 0).
Execute Record_History.
Execute Move_Module (out_0, 0, -1, 0).
Execute Move_Module (out_1, 0, -1, 0).
Execute Record_History.
(3.3) When as = 3:
Execute Move_Module (out_1, 1, 0, 0).
Execute Record_History.
If Zr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, 0, 0, -1).
Else,
Execute Move_Module (out_0, 0, 0, 1).
Execute Record_History.
Execute Move_Module (out_0, 1, 0, 0).
Execute Move_Module (out_1, 1, 0, 0).
Execute Record_History.
(3.4) When as = 4:
Execute Move_Module (out_1, 0, 1, 0).
Execute Record_History.
If Xr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, -1, 0, 0).
else,
Execute Move_Module (out_0, 1, 0, 0).
Execute Record_History.
Execute Move_Module (out_0, 0, 1, 0).
Execute Move_Module (out_1, 0, 1, 0).
Execute Record_History.
(3.5) When as = 5:
Execute Move_Module (out_1, 0, 0, -1).
Execute Record_History.
If Yr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, 0, -1, 0).
Else,
Execute Move_Module (out_0, 0, 1, 0).
Execute Record_History.
Execute Move_Module (out_0, 0, 0, -1).
Execute Move_Module (out_1, 0, 0, -1).
Execute Record_History.
(3.6) When as = 6:
Execute Move_Module (out_1, 0, 0, 1).
Execute Record_History.
If Yr [out_0]% 2 = 1, Then,
Execute Move_Module (out_0, 0, -1, 0).
Else,
Execute Move_Module (out_0, 0, 1, 0).
Execute Record_History.
Execute Move_Module (out_0, 0, 0, 1).
Execute Move_Module (out_1, 0, 0, 1).
Execute Record_History.

[Control of backup robot]
Before calling Move_Module processing that moves the robot while Robot_Exchange is running, check whether the robot movement that is going to be executed by that Move_Module does not cause disconnection of the two save robots out_0 and out_1 from other robots, In case of occurrence, the function of changing the position of the evacuation robot and avoiding disconnection is implemented by Add_Movable and Evacuating_Cube_Control as described above.

  The evacuation robot is always in contact with two robots, and is always in contact with the surface Ss. The movement of the evacuation robot is limited to the movement in the direction perpendicular to the direction in which the two robots are connected and perpendicular to as. Ss and as are defined in (1) of Void_Generation.

[Add_Movable (i, _vx, _vy, _vz)]
(1) A variable “movable_cubes []” that stores the number of the robot that is about to operate and a variable “movable_num” that stores the number of robots that are about to operate are set to “movable_cubes [movable_num] ← i”.
(2) Set the value of a variable that stores the moving direction of the robot that is about to operate. In other words, movable_vx [movable_num] ← _vx, movable_vy [movable_num] ← _vy, movable_vz [movable_num] ← _vz.
(3) Increment movable_num.

[Evacuating_Cube_Control]
(1) Check if there is a robot that is in contact with the robot out_0 or the robot out_1 in the opposite direction of the as (contacted via the surface Ss). If there is such a robot, check if all of the robot's numbers are included in the robot that is about to move (movable_cubes [im], im = 0,1,…, movable-1) Exit if there is nothing. If all of them are included, at most two robots that are in contact with one of the robots out_0 and out_1 and are included in the movable_num robots movable_cubes [] are taken as robots movable_cubes [im0] and movable_cubes [im1].
(2) For the robots movable_cubes [im0] and movable_cubes [im1], the robots movable_cubes [im0] and movable_cubes [im1] respectively (movable_vx [im0], movable_vy [im0], movable_vz [im0]), (movable_vx [im1] , movable_vy [im1], movable_vz [im1]), it is checked whether it is in contact with either the robot out_0 or out_1 even after moving by the vector amount. If at least one of the robot movable_cubes [im0] and movable_cubes [im1] is in contact, the process ends.
(3) Robots movable_cubes [im0], movable_cubes [im1], vectors (-movable_vx [im0], -movable_vy [im0], -movable_vz [im0]), (-movable_vx [im1], -movable_vy [im1], If there are robots belonging to movable_cubes [] that contact in the direction pointed to by -movable_vz [im1], make them robots movable_cubes [entail_im0] and movable_cubes [entail_im1], and for robots movable [im0] and robots movable_cubes [entail_im0] When the moving directions are the same, that is, (movable_vx [im0], movable_vy [im0], movable_vz [im0]) = (movable_vx [entail_im0], movable_vy [entail_im0], movable_vz [entail_im0]), the process ends. When the moving directions of the robot movable [im1] and the robot movable_cubes [entail_im1] are the same, that is, (movable_vx [im1], movable_vy [im1], movable_vz [im1]) = (movable_vx [entail_im1], movable_vy [entail_im1], movable_im1z ]).
(4) When there are only two robots on the surface Ss and their positional relationship is a diagonal position in Ss, those robots that are not in contact with the robot out_0 or out_1 Set it as tmp_move, and robot no_tmp_move the one that is in contact. The robot tmp_move is brought into contact with the robot no_tmp_move and moved one step to a position not in contact with the robots out_0 and out_1. (Example: When as = 1,3, if Zr [tmp_move] is an odd number, move 1 step in the Z negative direction). Execute Record_History.
(5) Perform the following save operation.
(5.1) When as = 1,3:
If Yr [out_0] is an odd number Then, robot out_0, out_1 move one step in the Y negative direction.
Else, move robots out_0 and out_1 one step in the Y positive direction
(5.2) When as = 2,4:
If Zr [out_0] is odd then, move robot out_0, out_1 one step in the Z negative direction.
Move Else, robot out_0, out_1 one step in the positive Z direction.
(5.3) When as = 5 and 6:
If Xr [out_0] is an odd number Then, move robot out_0, out_1 one step in the negative X direction.
Move Else, robot out_0, out_1 one step in X positive direction.
(6) Execute Record_History.
(7) If there is the robot tmp_move moved in (4), move the robot tmp_move by one step in the reverse direction of the operation in (4). Execute Record_History.

  Before_Care is a process that is called (in Line_Perm_By_Position) before robot position change in a line element. That is, also at the time of robot replacement in the line element, the save robot can maintain the connection to another robot (do not cause disconnection from another robot), and the save robot moves to a safe position. If at least one robot out_0, out_1 is not in contact with the position (unsafe position) shown in FIG. 13, it is safe. The robot out_0, out_1 stores the unsafe position in variables (bad_place_x [], bad_place_y [], bad_place_z []).

[Before_Care (_s, _g, _d, _p_l)]
(1) Define variables (bad_place_x [], bad_place_y [], bad_place_z []) and bad_num. bad_num ← 0.
(2) For all values of i = 0 to _g-s, perform the following.
(2.1) (bad_place_x [bad_num], bad_place_y [bad_num], bad_place_y [bad_num]) ← (path_perm_x [_s + i], path_perm_y [_s + i], path_perm_z [_s + i])
Increment bad_num.
(2.2)
When _d = 1: (line element is oriented in X)
(bad_place_x [bad_num], bad_place_y [bad_num], bad_place_y [bad_num]) ← (path_perm_x [_s + i], path_perm_y [_s + i] + _ pl, path_perm_z [_s + i]).
When _d = 2: (line element is in Y direction)
(bad_place_x [bad_num], bad_place_y [bad_num], bad_place_y [bad_num]) ← (path_perm_x [_s + i], path_perm_y [_s + i], path_perm_z [_s + i] + _pl).
When _d = 3: (Line element is in Z direction)
(bad_place_x [bad_num], bad_place_y [bad_num], bad_place_y [bad_num]) ← (path_perm_x [_s + i] + _pl, path_perm_y [_s + i], path_perm_z [_s + i])
(2.3) Increment bad_num.
(3) Check whether the robot out_0, out_1 is in contact with the position (bad_place_x [], bad_place_y [], bad_place_y []). If at least one of the robots out_0 and out_1 is not in contact, the process ends.
(4) The position of the robot out_0, out_1 in contact (bad_place_x [], bad_place_y [], bad_place_y []) is (bad_place_x [o_0], bad_place_y [o_0], bad_place_y [o_0]), (bad_place_x [o_1], bad_place_y Suppose that [o_1], bad_place_y [o_1]).
(5) Move the robots out_0 and out_1 to a safe place as follows.
(5.1) When as = 1 and 3:
When _d = 1 and 3: (Slide to a position where robot out_0, out_1 is not in contact with (bad_place_x [], bad_place_y [], bad_place_y []))
If Yr [out_0] is odd, Then,
Move robot out_0, out_1 one step in the negative Y direction.
Else,
Move robot out_0, out_1 one step in the positive Y direction.
When _d = 2: (Avoid all positions (a) to (f) in FIG. 13)
If nm> 0, Then, (Avoid positions (a), (c), (d), and (f) in FIG. 13).
If (o_0 = 2 * nm + 2 && o_1 = 2 * nm + 3) || (o_0 = 2 * nm + 3 && o_1 = 2 * nm + 2)
|| (o_0 = 0 && o_1 = 1) || (o_0 = 1 && o_1 = 0), Then,
If Yr [out_0] is odd, Then,
Move robot out_0, out_1 one step in the negative Y direction.
Else,
Move robot out_0, out_1 one step in the positive Y direction.
Else, (Avoid all except positions (d) and (f) in Figure 13)
If! ((O_0 = 0 && o_1 = 1) || (o_0 = 1 && o_1 = 0)) Then,
If Yr [out_0] is an odd number, Then,
Move robot out_0, out_1 one step in the negative Y direction.
Else,
Move robot out_0 and out_1 one step in the Y positive direction.
(5.2) When as = 2 and 4:
When _d = 1 and 2: (Slide to a position where robot out_0, out_1 does not touch (bad_place_x [], bad_place_y [], bad_place_y []))
If Zr [out_0] is odd, Then,
Move robot out_0, out_1 one step in the negative Z direction.
Else,
Move robots out_0 and out_1 one step in the Z positive direction.
When _d = 3: (Avoid positions (a) to (f) in FIG. 13)
If nm> 0, Then, (Avoid positions (a), (c), (d), and (f) in FIG. 13).
If (o_0 = 2 * nm + 2 && o_1 = 2 * nm + 3) || (o_0 = 2 * nm + 3 && o_1 = 2 * nm + 2)
|| (o_0 = 0 && o_1 = 1) || (o_0 = 1 && o_1 = 0), Then,
If Zr [out_0] is odd, Then,
Move robot out_0 and out_1 one step in the Z negative direction.
Else,
Move robot out_0, out_1 one step in the positive Z direction.
Else, (Avoid all except positions (d) and (f) in Figure 13)
If ((o_0 = 0 && o_1 = 1) || (o_0 = 1 && o_1 = 0)) Then,
If Zr [out_0] is odd, Then,
Move robot out_0, out_1 one step in the negative Z direction.
Else,
Move robots out_0 and out_1 one step in the Z positive direction.
(5.3) When as = 5 and 6:
When _d = 2 and 3: (Slide to a position where robot out_0, out_1 does not touch (bad_place_x [], bad_place_y [], bad_place_y []))
If Xr [out_0] is an odd number, Then,
Move robot out_0, out_1 one step in the negative X direction.
Else,
Move robot out_0, out_1 one step in X positive direction.
When _d = 1: (Avoid all the positions (a) to (f) in FIG. 13)
If nm> 0, Then (Avoid all positions (a), (c), (d) and (f) in FIG. 13)
If (o_0 = 2 * nm + 2 && o_1 = 2 * nm + 3) || (o_0 = 2 * nm + 3 && o_1 = 2 * nm + 2)
|| (o_0 = 0 && o_1 = 1) || (o_0 = 1 && o_1 = 0), Then,
If Xr [out_0] is an odd number, Then,
Move robot out_0, out_1 one step in the negative X direction.
Else,
Move robot out_0, out_1 one step in the positive X direction.
Else, (Avoid all except positions (d) and (f) in Figure 13)
If! ((O_0 = 0 && o_1 = 1) || (o_0 = 1 && o_1 = 0)) Then,
If Xr [out_0] is an odd number, Then,
Move robot out_0, out_1 one step in X negative direction.
Else,
Move robot out_0, out_1 one step in the positive X direction.
(6) Execute Record_History.

<Action control system 100 according to the first embodiment>
The behavior control system 100 according to the first embodiment is configured by the processes described above. The whole operation (homogeneous corps formation control and robot position change control) is summarized below.

(Homogeneous formation control)
(1) Using the method of Non-Patent Document 6, the homogeneous formation is deformed from the start position set S to the target position set G.

(Robot position exchange control)
(2) Execute robot position change control procedure (Robot_Position_Permutation). That is, for each robot, each individual robot position replacement control procedure (Each_Robot_Position_Exchange) is executed until the position of each individual robot reaches the target position.

  Hereinafter, a configuration for executing these processes will be described.

  FIG. 14 shows a functional block diagram of the action control system 100 according to the first embodiment, and FIG. 15 shows an example of robot position change control which is a part of the process flow of the action control system 100. As shown in FIG. 14, the behavior control system 100 includes a homogeneous row control device 900, a control target position exchange control device 120, a storage unit 140, a communication unit 150, and an input unit 160. The controlled object repositioning control device 120 includes the individual controlled object repositioning control unit 130, and the individual controlled object repositioning control unit 130 includes the interchanging path generation unit 131, the void generation unit 132, and the interchange control unit 133. And a void eraser 134.

  In the present embodiment, the behavior control system 100 controls the behavior of p (where p is any integer greater than or equal to 16 and is a multiple of 8) robots and one of p robots is controlled. Implemented above.

<Input unit 160>
A set S of p start positions S = {(Xr0 [0], Yrs [0]), (Xr0 [1], Yrs [1]), ..., (Xr0 [p-1], Yrs [p-1])} and a set of p target positions G = {(Xre [0], Yre [0]), (Xre [1], Yre [1]), ..., (Xre [p- 1], Yre [p-1])} are input and stored in the storage unit 140.

<Storage unit 140>
In the storage unit 140, positions of a set S of p start positions and a set G of p target positions input from the input unit 160 are stored. Of the information generated in the course of other processing, information that needs to be stored is stored as appropriate.

<Communication unit 150>
All robots, including the robot in which the behavior control system 100 is mounted, communicate with other robots adjacent in the vertical and horizontal directions on the three-dimensional plane (hereinafter also referred to as “six directions”) via the communication unit 150. It can communicate.

<Homogeneous formation control device 900>
Homogeneous corps train deformation is performed using the method of Non-Patent Document 6 from the set S of start positions to the set G of target positions.

<Control Object Position Replacement Control Device 120>
The control object position change control device 120 executes a robot position change control procedure Robot_Position_Permutation to control all the robots to reach the target position (S120).

<Each control object position replacement control unit 130>
Each individual control object position exchange control unit 130 performs each individual robot position exchange control processing procedure (Each_Robot_Position_Exchange) for the smallest i in which the position of the robot i does not match the destination robot position d (i) (not i = d (i)). ) (S130).

  The exchange path generation unit 131 executes the exchange path generation processing procedure Calculate_Path_From_Origin_To_Destination to generate an exchange path between the exchange source robot i and the exchange destination robot d (i) (S131). The exchange path between the robot i at the exchange source and the robot d (i) at the exchange destination is divided into a plurality of line elements, corner elements, and one final line element as shown in FIG.

  Prior to the replacement of the replacement-source robot i and the replacement-destination robot d (i), the void generation unit 132 executes the void generation processing procedure Void_Generation to generate two voids in the target position set G ( S132). As a result, the two robots out_0 and out_1 are saved outside G. Since the save robots out_0 and out_1 need to be finally returned to G, the positions of the two robots are (escape_cube_buffer_x [0], escape_cube_buffer_y [0], escape_cube_buffer_z [0]), (escape_cube_buffer_x [1 ], escape_cube_buffer_y [1], escape_cube_buffer_z [1]) are recorded (see (6) of Void_Generation).

  The exchange control unit 133 executes the exchange control processing procedure Robot_Exchange to exchange the robot i of the exchange source and the robot d (i) of the exchange destination (S133). First, the first exchange control procedure Robot_Exchange_1 is executed to move the robot i to the position of the robot d (i). At that time, replacement control (Line_Perm, Corner_Perm) is performed for each line element and corner element generated by dividing the replacement path. In the replacement process (Line_Perm, Corner_Perm) for each element, first execute Navigate_Void to move the two voids generated earlier to appropriate positions. In the case of a line element (Line_Perm), Before_Care is executed and the two retracting robots out_0 and out_1 are moved to positions that do not cause disconnection from other robots. After that, move the robot i by executing Move_Module and Record_History, but before moving the robot i, always execute Add_Movable and Evacuating_Cube_Control and disconnect the two evacuation robots out_0 and out_1 from other robots. Do not cause. In this way, the robot i is gradually brought closer to the position of the robot d (i). That is, with the execution of Add_Movable and Evacuating_Cube_Control, Move_Module and Record_History as one set, the robot i is brought closer to the position of the robot d (i).

  When the robot i reaches the position of the robot d (i), next, the second replacement control processing procedure Robot_Exchange_2 is executed, and the robot d (i) is moved to the position where the robot i has originated. The difference from Robot_Exchange_1 is that the order of the line element and the corner element in which the robot d (i) moves is reversed from the previous one, that Reverse_Void_To is executed instead of Navigate_Void in Line_Perm and Corner_Perm, Last_Line_Perm is executed There is no point.

  The Robot_Exchange process ends when the robot d (i) moves to the position where the robot i was originally located. By processing in this way, the positions of the other robots remain unchanged, except that the position of the replacement robot i and the position of the replacement robot d (i) are switched before and after the replacement of the robot i and the robot d (i). can do.

  Finally, the void elimination unit 134 executes the void elimination procedure Void_UnGeneration to respectively return the two robots out_0 and out_1 that were retracted outside G to the positions immediately before the void formation (S134).

  At each time step, it is determined whether or not all the robots have reached the target position (S135), and when all the robots have reached the target position, the processing is terminated. If not, continue processing.

The processes S130 to S135 described above are performed for each time step.
<Effect>
With such a configuration, the formation of a row from any formation position to a formation of formation at any other target position is hindered while keeping the robots in contact with each other while considering the existence of a large number of robots. Robot formation before and after the start of changing the position of the cube-shaped robot, as in the case where heterogeneous formation control is realized by moving each robot to an individual target position after performing a homogeneous formation deformation operation in a certain environment Under the same condition, each robot can be placed at an appropriate position in the robot array by an area shearing operation between robots at an execution time proportional to the square of the number of robots.

  As a result, each robot such as a robot equipped with a camera, a robot equipped with a wheel, etc. has different roles, and while arranging each robot at an appropriate position in the robot array, the shape of the array is exchanged before and after maintenance control It is possible to operate. Moreover, it is not necessary to implement all functions necessary for all robots.

<Modification>
In the present embodiment, each lattice (mass) is a cube, but may have another shape. The lattice is continuously arranged in the left-right direction, the up-down direction, and the front-rear direction. Also, each grid is adjacent to the other two grids in the left-right direction, adjacent to the other two grids in the top-bottom direction, and adjacent to the other two grids in the front-rear direction. In other words, each grid is adjacent to the other grid only in the same direction as the robot can move. Each grid may have any shape as long as this condition is satisfied. Also, “orthogonal” does not necessarily mean strictly “perpendicular to each other,” for example, each lattice may be a parallelepiped, and each lattice is adjacent to the other two lattices. One side may be the up-down direction and the other side may be the left-right direction.

  In other words, in the three-dimensional space, the controlled object is in a first direction (eg, right direction), a second direction (eg, upward direction) that is a direction not parallel to the first direction, or in a first direction A third direction (eg, left direction) opposite to the opposite direction, a fourth direction (eg downward) opposite to the second direction, a direction not parallel to a plane formed by the first direction and the second direction Can be moved in the fifth direction (for example, the forward direction) in the sixth direction, which is the opposite direction to the fifth direction, and from the current area (grid, mass) to the current area by one action control In contrast, it is controlled to move to any of the adjacent regions in the first direction, the second direction, the third direction, the fourth direction, the fifth direction, and the sixth direction. In this case, on the two-dimensional plane of the robot, a position adjacent to the first direction in the first direction is a first position, a position adjacent to the second direction in the second direction is a second position, and a position adjacent to the third direction in the third direction A position adjacent in the four directions may be referred to as a fourth position, a position adjacent in the fifth direction as a fifth position, and a position adjacent in the sixth direction as a sixth position.

  In the present embodiment, an example is shown in which the behavior control system 100 is mounted on one of the p robots, but behavior control may be performed on a control target on a computer.

  In this embodiment, the robot unit is composed of 8 robots of 2 × 2 × 2, but may be composed of M × N × Q robots. However, M, N, and Q are each an integer of 2 or more. The number of robots p is a multiple of 2 or more of the number of robots M × N × Q included in the robot unit. That is, p = M × N × Q × R, and R is any integer of 2 or more. When moving in such a state, as in the case of 2 × 2 × 2 robot units, even if any robot in the swarm of robots is missing, each robot is one for each other It is not necessary to break the positional relationship that touches the sides.

Of course, it is also possible to execute the control target object repositioning control device 120 that constitutes the behavior control system 100 alone. In this case, the set of positions before the start of replacement and the set of positions after the start of replacement are replaced under the same condition.
<Second embodiment>
When the save robot is not the robot to be replaced (that is, when the robot origin and destination to be replaced do not match any of the save robots out_0 and out_1), Void_Generation that is a void generation process can be omitted. Thereby, efficiency of processing can be achieved.

  The robot position replacement control processing procedure Robot_Position_Permutation and each robot position replacement control processing procedure Each_Robot_Position_Exchange of the first embodiment are changed to a robot position replacement control processing procedure Robot_Position_Permutation_2 and each robot position replacement control processing procedure Each_Robot_Position_Exchange_2, respectively.

[Robot_Position_Permutation_2]
(1) Set variable p (i) = 0 for all robots i. (P is a robot position exchanged determination flag). Set tp = 0 and execute Record_History (where tp is a time counter).
(2) Let p (i) = 1 for all robots i where i = d (i).
(3) Repeat (4) to (6) until p (i) = 1 for all i.
(4) Select the smallest i that satisfies p (i) = 0.
(5) Repeat the procedure (6) unless i = d (i).
(6) Execute each_Robot_Position_Exchange_2 with the replacement origin robot origin ← i and the replacement destination robot destination ← d (i).
(7) Execute Reverse_Void_To (void_buffer_x [0], void_buffer_y [0], void_buffer_z [0], void_buffer_x [1], void_buffer_y [1], void_buffer_z [1]) to execute Void_UnGeneration.

(Void_buffer_x [0], void_buffer_y [0], void_buffer_z [0]), (void_buffer_x [1], void_buffer_y [1], void_buffer_z [1]) stores the location of the save robot out_0, out_1 defined by Void_Generation Variable.
[Each_Robot_Position_Exchange_2]
(1) Execute Calculate_Path_From_Origin_To_Destination.
(2) When this process is executed for the first time, Void_Generation is executed. Reverse_Void_To (void_buffer_x [0], void_buffer_y [0], void_buffer_z [0], void_buffer_x [0], if the swap source robot origin or the swap destination robot destination matches with the save robot out_0 or out_1 for the second and subsequent executions. 1], void_buffer_y [1], void_buffer_z [1]), Void_UnGeneration, and Void_Generation.
(3) Execute Robot_Exchange.

<Behavior Control System 200 According to Second Embodiment>
The action control system 200 according to the second embodiment is configured by the robot position change control described above. The homogeneous formation control is the same as that of the behavior control system 100 according to the first embodiment.

  FIG. 16 shows a functional block diagram of the behavior control system 200 according to the second embodiment, and FIG. 17 shows an example of robot position replacement control which is a part of the process flow of the behavior control system 200. The behavior control system 200 includes, as shown in FIG. 16, a homogeneous row control device 900, a control target position change control device 220, a storage unit 140, a communication unit 150, and an input unit 160. That is, it is different from the behavior control system 100 according to the first embodiment in that it includes the control object position replacement control device 220 instead of the control object position replacement control device 120. The control object position replacement control device 220 includes each individual control object position replacement control unit 230 and a final void elimination unit 240. Each individual control target object position replacement control unit 230 includes a replacement path generation unit 131, a void generation unit 232, and a replacement control unit 133.

<Control Object Position Replacement Control Device 220>
The control object position change control device 220 executes the robot position change control procedure Robot_Position_Permutation_2 to control all the robots to reach the target position (S220).

<Each control object position replacement control unit 230>
Each individual object position replacement control unit 230 performs each individual robot position replacement control processing procedure (Each_Robot_Position_Exchange_2) for the smallest i in which the position of the robot i does not match the destination robot position d (i) (i = not i (d)). ) (S230).

  The exchange path generation unit 131 executes the exchange path generation processing procedure Calculate_Path_From_Origin_To_Destination to generate an exchange path between the exchange source robot i and the exchange destination robot d (i) (S131).

  Prior to the exchange of the robot i of the exchange source and the robot d (i) of the exchange destination, the void generation unit 232 checks whether it is the first process by the void generation unit 232, and if it is the first execution, the void generation process Procedure Void_Generation is executed, and in the case of the second and subsequent executions, if either the robot i to replace or the robot d (i) to replace with matches the save robot out_0, out_1, Reverse_Void_To (void_buffer_x [0], void_buffer_y [0], void_buffer_z [0], void_buffer_x [1], void_buffer_y [1], void_buffer_z [1]), Void_UnGeneration, and Void_Generation are sequentially executed (S232).

  The exchange control unit 133 executes the exchange control processing procedure Robot_Exchange to exchange the robot i of the exchange source and the robot d (i) of the exchange destination (S133).

  At each time step, it is determined whether or not all the robots have reached the target position (S135), and if all the robots have reached the target position, the final void removal process is performed to end the process. Run. Otherwise, the individual robot position replacement process is continued.

<Final void elimination unit 240>
The final void elimination unit 234 sequentially executes Reverse_Void_To (void_buffer_x [0], void_buffer_y [0], void_buffer_z [0], void_buffer_x [1], void_buffer_y [1], void_buffer_z [1]), and Void_UnGeneration. The two robots out_0 and out_1 are respectively returned to the positions immediately before void formation (S240).

The processes S230 to S240 described above are performed every time step.
<Other Modifications>
The present invention is not limited to the above-described embodiments and modifications. For example, the various processes described above are not only executed in time series according to the description, but may also be executed in parallel or individually as required by the processing capability of the apparatus that executes the processes. In addition, it can change suitably in the range which does not deviate from the meaning of this invention.

<Program and Recording Medium>
In addition, various processing functions in each device described in the above-described embodiment and modification may be realized by a computer. In that case, the processing content of the function that each device should have is described by a program. Then, by executing this program on a computer, various processing functions in each of the above devices are realized on the computer.

  The program describing the processing content can be recorded in a computer readable recording medium. As the computer readable recording medium, any medium such as a magnetic recording device, an optical disc, a magneto-optical recording medium, a semiconductor memory, etc. may be used.

  Further, this program is distributed, for example, by selling, transferring, lending, etc. a portable recording medium such as a DVD, a CD-ROM or the like in which the program is recorded. Furthermore, the program may be stored in a storage device of a server computer, and the program may be distributed by transferring the program from the server computer to another computer via a network.

  For example, a computer that executes such a program first temporarily stores a program recorded on a portable recording medium or a program transferred from a server computer in its own storage unit. When executing the process, this computer reads the program stored in its own storage unit and executes the process according to the read program. As another embodiment of this program, a computer may read a program directly from a portable recording medium and execute processing according to the program. Further, each time a program is transferred from the server computer to the computer, processing according to the received program may be executed sequentially. In addition, a configuration in which the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes processing functions only by executing instructions and acquiring results from the server computer without transferring the program to the computer It may be Note that the program includes information provided for processing by a computer that conforms to the program (such as data that is not a direct command to the computer but has a property that defines the processing of the computer).

  In addition, although each device is configured by executing a predetermined program on a computer, at least a part of the processing content may be realized as hardware.

DESCRIPTION OF SYMBOLS 100 Action control system 120 Control target object position replacement control apparatus 130 Individual control target object position replacement control part 131 Replacement path generation part 132 Void generation part 133 Replacement control part 134 Void elimination part 140 Storage part 150 Communication part 160 Input part 900 Homogeneous formation Control device 200 Behavior control system 220 Control object position replacement control device 230 Individual control object position replacement control unit 232 Void generation unit 240 Final void elimination unit

Claims (5)

Let M, N, and Q be either integers of 2 or more, R be any integer of 2 or more, p be M × N × Q × R, and the set of positions before and after the start of replacement is A control object replacement control device that switches the positions of the control objects so that each of the p control objects is arranged at a specified position in the set under the condition that they are the same. ,
The direction that is not parallel to the first direction is the second direction, the direction opposite to the first direction is the third direction, the direction opposite to the second direction is the fourth direction, the first direction and the first direction The direction that is not parallel to the plane formed by two directions is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and M × N × Q positions are one position unit, and the set Each of the positions is adjacent to another position in at least one of the first direction to the sixth direction, the set is formed in an arbitrary shape of a group of R position units,
The control object includes a first position adjacent in the first direction on the three-dimensional space of the control object, a second position adjacent in the second direction, a third position adjacent in the third direction, and a fourth direction. The fourth adjacent position, the fifth adjacent position in the fifth direction, the sixth adjacent position in the sixth direction, stand still, or any of the first to sixth positions in a three-dimensional space Shall be controlled to move,
The control object moves while maintaining a state in contact with another control object,
The position in the set that the control object should reach is the target position, and the current position in the set of the control object is the current position, and the current position of the control object is the control object A replacement path generation unit that generates a replacement path from the current position to the target position if the target position does not match the target position;
A void generation unit that generates a void as a virtual existence that occurs with the movement of the control object or moves in a direction opposite to the direction in which the control object moves, and generates two voids in the set;
A switching control unit for switching the control object at the current position and the control object at the target position along the replacement path using the two voids;
When the void generation unit generates a void, a control target object moved to a position adjacent to the set is used as a evacuation control target, and the evacuation control objects are the originals in the set in which each existed. A void erasing unit that erases the two voids by returning to the position,
Control object interchange control device. Let M, N, and Q be either integers of 2 or more, R be any integer of 2 or more, p be M × N × Q × R, and the set of positions before and after the start of replacement is A control object replacement control device that switches the positions of the control objects so that each of the p control objects is arranged at a specified position in the set under the condition that they are the same. ,
The direction that is not parallel to the first direction is the second direction, the direction opposite to the first direction is the third direction, the direction opposite to the second direction is the fourth direction, the first direction and the first direction The direction that is not parallel to the plane formed by two directions is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and M × N × Q positions are one position unit, and the set Each of the positions is adjacent to another position in at least one of the first direction to the sixth direction, the set is formed in an arbitrary shape of a group of R position units,
The control object includes a first position adjacent in the first direction on the three-dimensional space of the control object, a second position adjacent in the second direction, a third position adjacent in the third direction, and a fourth direction. The fourth adjacent position, the fifth adjacent position in the fifth direction, the sixth adjacent position in the sixth direction, stand still, or any of the first to sixth positions in a three-dimensional space Shall be controlled to move,
The controlled object moves while maintaining a state of being in contact with another controlled object,
The position in the set to be reached by the control object is the target position, the current position in the set of the control object is the current position, and the current position of the control object is the position of the control object. A replacement path generation unit that generates a replacement path from the current position to the target position if the target position does not match the target position;
A void that occurs with the movement of the controlled object, or a virtual entity moving in a direction opposite to the moving direction of the controlled object is a void, and in a predetermined case, generates two voids in the group A generation unit,
Using the two voids, a replacement control unit that replaces the control object at the current position and the control object at the target position along the replacement path;
When the void generation unit generates a void, the control target object moved to a position adjacent to the set is taken as the evacuation control target object, and all the control objects reach the respective target positions. A final void eraser that erases the two voids by returning the evacuation control objects to their original positions in the set where each existed,
In the predetermined case where the void generation unit generates a void, the void generation unit is executed for the first time, or a void is already generated as a result of the execution of the void generation unit. In the above, it is when the evacuation control object at the present time is the control object to be replaced this time ,
Control object interchange control device. Let M, N, and Q be either integers of 2 or more, R be any integer of 2 or more, p be M × N × Q × R, and the control object replacement control device is used before replacement starts Under the condition that the set of positions after the replacement is the same, the positions of the control objects are switched so that each of the p control objects is arranged at a specified position in the set. A control object replacement control method,
The direction that is not parallel to the first direction is the second direction, the direction opposite to the first direction is the third direction, the direction opposite to the second direction is the fourth direction, the first direction and the first direction The direction that is not parallel to the plane formed by two directions is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and M × N × Q positions are one position unit, and the set Each of the positions is adjacent to another position in at least one of the first direction to the sixth direction, the set is formed in an arbitrary shape of a group of R position units,
The control object is a first position adjacent in a first direction on a three-dimensional space of the control object, a second position adjacent in a second direction, a third position adjacent in a third direction, and a fourth direction The fourth adjacent position, the fifth adjacent position in the fifth direction, the sixth adjacent position in the sixth direction, stand still, or any of the first to sixth positions in a three-dimensional space Shall be controlled to move,
The controlled object moves while maintaining a state of being in contact with another controlled object,
The control object replacement control device sets a position in the set to be reached by the control object as a target position, a current position in the set of the control objects as a current position, and the control object If the current position of the control object does not match the target position of the control object, a replacement path generation step for generating a replacement path from the current position to the target position;
The control object replacement control device uses a virtual existence that occurs with the movement of the control object or moves in a direction opposite to the direction in which the control object moves as a void. A void generation step for generating a void;
The control object replacement control device replaces the control object at the current position and the control object at the target position along the replacement path using the two voids,
When the control object interchange control device generates a void in the void generation step, the control object moved to a position adjacent to the set is regarded as an evacuation control object, and each evacuation control object exists. Void elimination step of eliminating the two voids by returning to the original position in the set that had been
Control object replacement control method. Let M, N, and Q be either integers of 2 or more, R be any integer of 2 or more, p be M × N × Q × R, and the control object replacement control device is used before replacement starts Under the condition that the set of positions after the replacement is the same, the positions of the control objects are switched so that each of the p control objects is arranged at a specified position in the set. A control object replacement control method,
The direction that is not parallel to the first direction is the second direction, the direction opposite to the first direction is the third direction, the direction opposite to the second direction is the fourth direction, the first direction and the first direction The direction that is not parallel to the plane formed by two directions is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and M × N × Q positions are one position unit, and the set Each of the positions is adjacent to another position in at least one of the first direction to the sixth direction, the set is formed in an arbitrary shape of a group of R position units,
The control object includes a first position adjacent in the first direction on the three-dimensional space of the control object, a second position adjacent in the second direction, a third position adjacent in the third direction, and a fourth direction. The fourth adjacent position, the fifth adjacent position in the fifth direction, the sixth adjacent position in the sixth direction, stand still, or any of the first to sixth positions in a three-dimensional space Shall be controlled to move,
The controlled object moves while maintaining a state of being in contact with another controlled object,
The control object replacement control device sets a position in the set to be reached by the control object as a target position, a current position in the set of the control objects as a current position, and the control object A replacement path generation step of generating a replacement path from the current position to the target position if the current position of the target does not match the target position of the control object;
The controlled object replacement control device sets a virtual existence, which occurs with the movement of the controlled object, or moves in a direction opposite to the moving direction of the controlled object, as a void, and in a predetermined case, A void generating step for generating two voids therein,
A replacement control step of replacing the control object at the current position and the control object at the target position along the replacement path using the two voids;
When the control object interchange control device generates a void in the void generation step, the control object moved to a position adjacent to the set is regarded as a retraction control object, and all control objects are target positions. And a final void elimination step for eliminating the two voids by returning the evacuation control objects to their original positions in the set in which they were present,
The predetermined case of generating a void in the void generation step is the first execution of the void generation step or the case where a void is already generated as a result of the execution of the void generation step. In the above, it is when the evacuation control object at the present time is the control object to be replaced this time ,
Control object replacement control method.   A program for causing a computer to function as the controlled object replacement control device according to claim 1.