JP2016119040A - Behavior control system, and method and program thereof - Google Patents

Abstract

[PROBLEMS] To provide a robot coordination corps formation technology that can reduce the calculation time required for planned calculation and the storage capacity of a computer to as little as when handling a single robot while considering the existence of a large number of robots. provide. When a control object does not exist in a set of all target position units, the head control object is used when moving the p control objects arranged in the start position set to the target position set. If the column Gb is determined for the column Ga at a certain time using the value function so that the unit serves as the head of movement, and there is no control object in the set of all target position units, the head control object The operation of each control object is controlled so that M × N control objects are located at the unit position, and if the control object exists in the set of all target position units, Is included, but control is performed so that each control object moves to a position that is not included in the set of target positions. [Selection] Figure 23

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 for obtaining an action plan for each robot for moving a plurality of robots in a coordinated manner from a formation state at a start position, avoiding an obstacle, and forming a formation at a target position.

  In recent years, research has been actively conducted to efficiently control a large number of autonomous mobile robots. Their missions vary, such as monitoring places where people can't enter, transporting goods, etc., but technology is being sought for efficient formation of platoons through the coordinated operation of many robots. (For example, refer nonpatent literature 1). In order to realize efficient formation of a formation by a large number of robots, it is important to plan the arrangement and operation order of each robot in advance. In such a plan, as a matter of course, it is necessary to sufficiently consider the presence of obstacles and the shape of a route in an actual environment where a plurality of robots operate.

  As an effective method for performing such a plan calculation, there are a dynamic programming method and a reinforcement learning method in a Markov decision process, and various studies have been conducted (for example, see 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 The advantages of being able to determine the absolute position of each robot and the advantage of not requiring additional position measurement equipment are being studied. For example, in the non-patent document 3, the row control from an arbitrary rectangular shape row to another rectangular shape 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, the formation control that changes from one formation to another formation is shown.

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 IEE / 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.

  However, in the method of Non-Patent Document 1, the operation of the group robot is controlled using a method of incorporating the hydrodynamic characteristics into the robot operation, and there is an advantage that enables control with a low calculation 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 trying to perform such a plan using dynamic programming or reinforcement learning in the Markov decision process, a plurality of robots are used compared to the case of 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 verified reinforcement learning method increases the computational load exponentially as the number of robots increases.

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

  Non-Patent Document 3 considers the condition that the motion commands given to the robot at the respective times are in the same direction, and does not require any additional equipment for position measurement. We need the existence of things. Moreover, the problem of 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 must be performed once, and there is a great restriction on the possible formation operation itself.

  In the method of Non-Patent Document 5, there are problems that the starting row and the target row must share a point, and that obstacles are not considered.

  In view of such a current situation, in the present invention, while considering the existence of a large number of robots, it is possible to reduce the calculation time required for planned calculation and the storage capacity of the computer to a small one, and the robots are in contact with each other. Robot coordination formation technology that enables transformation operations from a formation state at any starting position to a formation state at any other target position in an environment with obstacles while maintaining the state as it is The purpose is to provide.

  In order to solve the above-described problem, according to one aspect of the present invention, the behavior control system is configured such that M and N are each an integer of 2 or more, p is an integer of M × N or more, Action control for moving the p control objects arranged in the set of start positions to a set of target positions including a predetermined entrance position is performed. The action control system has a direction that is not parallel to the first direction as a second direction, a direction opposite to the first direction as a third direction, a direction opposite to the second direction as a fourth direction, Each start position and each target position are adjacent to other start positions and target positions in at least one of the first to fourth directions, and the set of target positions and the set of start positions are each a set of arbitrary Forming a shape, the control object is a first position adjacent in the first direction on the two-dimensional plane of the control object, a second position adjacent in the second direction, a third position adjacent in the third direction, And it is assumed that the fourth position is adjacent in the fourth direction, and is controlled to move to any one of the first to fourth positions on the two-dimensional plane. Is one control object unit per M × N units The M × N control objects constituting one control object unit are adjacent to the other control objects constituting the control object unit in two or more directions, respectively, and from the set of target positions. A set of target position units composed of N × N position units is set, and 1 represents the appropriateness when the controlled object unit takes each action a at the current position s of the controlled object unit. Controlled based on individual value functions and controlled to move to a position unit consisting of N × N positions in any of the first to fourth directions on the two-dimensional plane. When there is no control object in the storage unit in which the value function is stored and the set of all target position units, a certain formation formed by a plurality of control object units is defined as Ga, and a plurality of control object units are formed. The other formation is Gb, and it exists in formation Gb and does not exist in formation Ga When the target unit is the head control target unit and the p control target objects arranged in the set of start positions are moved to the target position set, the head control target unit is assumed to be the head of the movement. In addition, if there is no control object in the set of movement target platoon determination and the set of all target position units that determine the platoon Gb for the platoon Ga at a certain time using the value function, the head control object Including an operation planning unit for each control object operation that controls the operation of each control object so that M × N control objects are located at the position of the object unit. When there is an object, each motion target motion planning unit is included in the set of target position units, but moves to a position that is not included in the set of target positions. Control.

  In order to solve the above-described problem, according to another aspect of the present invention, in the behavior control method, M and N are each an integer of 2 or more, and p is an integer of M × N or more. Then, behavior control for moving the p control objects arranged in the set of start positions to a set of target positions including a predetermined entrance position is performed. In the behavior 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, Each start position and each target position are adjacent to other start positions and target positions in at least one of the first to fourth directions, and the set of target positions and the set of start positions are each a set of arbitrary Forming a shape, the control object is a first position adjacent in the first direction on the two-dimensional plane of the control object, a second position adjacent in the second direction, a third position adjacent in the third direction, And it is assumed that the fourth position is adjacent in the fourth direction, and is controlled to move to any one of the first to fourth positions on the two-dimensional plane. Consists of one control object unit for each M × N units. The M × N control objects constituting one control object unit are adjacent to other control objects constituting the control object unit in two or more directions, and N from the set of target positions. X A set of target position units consisting of position units consisting of N positions, and one representing the appropriateness when the control object unit takes each action a at the current position s of the control object unit It is controlled on the basis of the value function, and is controlled to move to a position unit consisting of N × N positions in any of the first to fourth directions on the two-dimensional plane. When the movement planning unit for determining the movement target platoon does not have a control object in the set of all target position units, Ga is defined as a platoon formed by a plurality of control object units, and other control object units are formed. A control pair that exists in formation Gb and does not exist in formation Ga is Gb. When the object unit is a head control object unit and the p control objects arranged in the set of start positions are moved to the set of target positions, the head control object unit is the head of the movement. , The movement plan determining operation sequence step for determining the column Gb for the column Ga at a certain time using the value function, and the operation planning unit for each control object operation are controlled objects in a set of all target position units. When there is no object, the step of controlling the operation of each control object so that M × N control objects are located at the position of the head control object unit, and the operation planning unit for each control object operation When the control object exists in the set of all target position units, the operation planning step for each control object operation is included in the set of target position units but is not included in the set of target positions. Step for controlling each control object to move And including.

  In order to solve the above problems, according to another aspect of the present invention, the behavior control system sets M, N, and Q to any one of integers of 2 or more, and sets R to any of integers of 24 or more. , P is M × N × Q × R, and behavior control is performed for moving p control objects arranged in the set of start positions to a set of target positions including a predetermined entrance position. The action control system has a direction that is not parallel to the first direction as a second direction, a direction opposite to the first direction as a third direction, a direction opposite to the second direction as a fourth direction, The direction that is not parallel to the plane formed by the first direction and the second direction is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and one of M × N × Q positions Each start position and each target position are adjacent to other start positions and target positions in at least one of the first direction to the sixth direction, and the set of target positions and the set of start positions are An arbitrary shape of a group of R position units is formed, and the control object is a first position adjacent in the first direction on the three-dimensional space of the control object, and a second position adjacent in the second direction. In the third direction, in the third direction, in the fourth direction The fourth position adjacent to each other, the fifth position adjacent in the fifth direction, the sixth position adjacent in the sixth direction, and either stationary or any of the first to sixth positions in the three-dimensional space It is assumed that the control objects of p units are configured as one control target unit for each M × N × Q units, and M × N × constituting one control target unit. Each of the Q control objects is adjacent to another control object constituting the control object unit in three or more directions, and the control object unit performs each action in the current position unit of the control object unit. It is controlled based on a single value function that represents the appropriateness when it is taken, and is stationary, or consists of N × N × Q positions in any of the first to sixth directions in a three-dimensional space. It is assumed that it is controlled to move to a position unit, a storage unit for storing a value function, and a plurality of A convoy that consists of control object units is Ga, another convoy that consists of multiple control object units is Gb, a control object unit that exists in the convoy Gb and does not exist in the convoy Ga is a head control object unit, When moving the p control objects arranged in the set of start positions to the set of target positions, the gamut Ga at a certain time using a value function so that the head control object unit takes the lead in the movement. Control unit movement control unit so that M × N × Q control objects are positioned at the position of the head control object unit. The value function is obtained using a Manhattan distance from a certain position unit to a position unit including a predetermined entrance position.

  In order to solve the above-mentioned problem, according to another aspect of the present invention, the behavior control method is such that M, N, and Q are each an integer of 2 or more, and R is an integer of 24 or more. , P is M × N × Q × R, and behavior control is performed for moving p control objects arranged in the set of start positions to a set of target positions including a predetermined entrance position. In the behavior 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 direction that is not parallel to the plane formed by the first direction and the second direction is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and one of M × N × Q positions Each start position and each target position are adjacent to other start positions and target positions in at least one of the first direction to the sixth direction, and the set of target positions and the set of start positions are An arbitrary shape of a group of R position units is formed, and the control object is a first position adjacent in the first direction on the three-dimensional space of the control object, and a second position adjacent in the second direction. , Third position adjacent in the third direction, in the fourth direction 4th position in contact, 5th position adjacent in 5th direction, 6th position adjacent in 6th direction, stationary or moved to any of first to sixth positions in 3D space The control objects of p units constitute one control object unit for each M × N × Q units, and M × N × Q units that constitute one control object unit. The control object is adjacent to other control objects constituting the control object unit in three or more directions, and the control object unit takes action in the current position unit of the control object unit. A position unit that is controlled based on a single value function that represents the appropriateness of time and is stationary, or consists of N × N × Q positions in any of the first to sixth directions in a three-dimensional space. The movement planning unit for determining the movement target platoon is controlled by a plurality of controls. Gait is a formation that consists of object units, Gb is another formation that consists of multiple control object units, and control object units that exist in formation Gb but do not exist in formation Ga are head control object units. When moving p control objects arranged in a set of positions to a set of target positions, a value function is used to move to the formation Ga at a certain time so that the head control object unit takes the lead of the movement. On the other hand, the movement plan step for determining the movement group for determining the row Gb and the movement planning unit for each movement of the control target object are M × N × Q control target objects at the position of the head control target unit. Thus, the value function is obtained by using a Manhattan distance from a certain position unit to a position unit including a predetermined entrance position.

  According to the present invention, while considering the existence of a large number of robots, it is possible to reduce the calculation time required for the planned calculation and the storage capacity of the computer to a small one and maintain the state where the robots are in contact with each other. However, it is possible to perform a deformation operation in an environment with an obstacle from a formation state at an arbitrary starting position to a formation state at another arbitrary target position.

The figure for demonstrating the movement of a robot. The figure for demonstrating the mission which many robots move from the formation formation state in a starting position in cooperation, and form formation at a target position. The figure for demonstrating the movement of a robot. The figure for demonstrating a tail robot and a head robot. The figure which shows a mode that one void which was in the position of a head robot moves to the position of a tail robot. The figure for demonstrating a robot unit. The figure for demonstrating the target formation area G and the target formation area unit GU. The figure for demonstrating the mission which many invariant type robots cooperate and move from the formation formation state in a starting position, and form a formation in a target position. The figure for demonstrating formation Ga and formation Gb. The figure for demonstrating formation Ga and formation Gb. FIG. 11A is a diagram for explaining mode 1 of each robot motion determining motion plan, and FIG. 11B is a diagram for explaining mode 1 of each robot motion determining motion plan. FIG. 12A is a diagram for explaining mode 1 of each robot motion determining motion plan, and FIG. 12B is a diagram for explaining mode 1 of each robot motion determining motion plan. FIG. 13A is a diagram for explaining mode 1 of each robot motion determining motion plan, and FIG. 13B is a diagram for explaining mode 1 of each robot motion determining motion plan. FIG. 14A is a diagram for explaining mode 1 of each robot motion determining motion plan, and FIG. 14B is a diagram for explaining mode 1 of each robot motion determining motion plan. The figure for demonstrating the mode 1 of each robot operation | movement determination operation plan. The figure for demonstrating robot order calculation processing Robot_Joretu_Decision. The figure for demonstrating the mission which many invariant type robots cooperate and move from the formation formation state in a starting position, and form a formation in a target position. The figure for demonstrating the mission which many invariant type robots cooperate and move from the formation formation state in a starting position, and form a formation in a target position. FIG. 5 is a diagram for explaining a mission in which a large number of invariant robots cooperate to move from a formation state at a start position and form a formation at a target position, and shows a state in which a target area unit GU is filled. Figure. The figure for demonstrating the conditions 1. FIG. The figure for demonstrating the mission which many invariant type robots cooperate and move from the formation formation state in a starting position, and form a formation in a target position. FIG. 6 is a diagram for explaining a mission in which a large number of invariant robots cooperate to move from a formation state at a start position and form a formation at a target position, and illustrates a state in which a target area G is filled . . The functional block diagram of the action control system which concerns on 1st embodiment. The figure which shows the example of the processing flow of the action control system which concerns on 1st embodiment. The figure which shows the example in case each lattice is a rhombus. The figure for demonstrating the movement of a robot. FIG. 27A is a diagram for explaining a set of start positions, and FIG. 27B is a diagram for explaining a set of target positions. The figure for demonstrating a tail robot and a head robot. The figure which shows a mode that one void which was in the position of a head robot moves to the position of a tail robot. The figure for demonstrating a robot unit. The figure for demonstrating void movement control. The functional block diagram of the action control system which concerns on 2nd embodiment. The figure which shows the example of the processing flow of the action control system which concerns on 2nd embodiment. The figure for demonstrating the mission which many robots move from the formation formation state in a starting position in cooperation, and form formation at a target position.

  Hereinafter, embodiments of the present invention will be described. In the drawings used for the following description, constituent parts having the same function and steps for performing the same process are denoted by the same reference numerals, and redundant description is omitted.

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

[Problem settings]
A number of robots cooperate to move from the formation state at the start position while maintaining the state in which each robot is in contact, and the task of forming the formation at the target position is as shown in FIG. Assuming the use of a square-type robot that can move by sliding the adjacent sides, as shown in FIG. 2, a plurality of robots can be moved from the start position to the target position in a room separated by walls. It is realized by movement.

  For example, as shown in FIG. 1, the robot moves while maintaining the state in which another robot exists in one of the four squares around the robot. This method has an advantage that one robot itself can accurately measure the movement amount of one operation by moving the distance corresponding to the size of one robot. Also, by measuring the relative positions of adjacent robots that share one side, the position of each robot in the entire group of robots can be easily known. 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. Further, as shown in FIG. 3, it is possible to move a plurality of robots at the same time as if a plurality of robots are connected. In FIG. 3, when transforming from platoon A to platoon B and when transforming from platoon D to platoon E, the two robots move simultaneously as if they were connected. It is assumed that the robot can know whether another robot is present at the adjacent position, whether there is an obstacle, and whether the robot is on the target position. For example, it is assumed that any robot can communicate with other robots existing in the mass around the robot, and at least one robot is equipped with GPS, or at least one robot does not move in one action control. In this case, each robot can easily know its absolute position by communicating with an adjacent robot with reference to a robot with GPS or a robot that has not moved. Alternatively, if the absolute position of at least one robot is known at the start position, it can be used to know the absolute position of each robot at each time without GPS.

  The robots that perform the mission are p units (p is any integer of 2 or more, for example, p ≧ 50), and each robot shares one or more sides with an adjacent robot, and the XY axis in a two-dimensional plane. It is possible to move in the direction (in this example, the four directions on the drawing up / down / left / right). However, p robots form one group. There can be only one robot in each grid. Each robot is assumed to be stationary if there are obstacles or other robots in the direction of movement. In FIG. 2, a grid in which R is described indicates a position where the robot exists, and a grid in which O is described indicates a position where an obstacle exists. An area surrounded by a thick broken line indicates a set of start positions, and an area surrounded by a thick dashed line is an area represented by a set G of target positions (hereinafter, this area is referred to as “target row area”). G ”), and an area surrounded by a thick solid line indicates an entrance position Pe of a target platoon area G to be described later. In this way, each start position and each target position are adjacent to other start positions and target positions in at least one of the vertical and horizontal directions, respectively, and the formation at the start position and the target position of the robot is a lump. Any shape.

[Robot coordinate settings]
The initial position (start position) of each robot i (i is the robot number i = 0,1,2,3 ,,, p-1) is (Xr0 [i], Yr0 [i]) and the target position Is (Xre [i], Yre [i]), this problem can be defined as finding an action plan for the robot placed at the start position to move to the target position.

[Definition of mission space]
When simply applying the Markov state transition model to such a problem, the Markov state space is the position of the robot i (Xr [i], Yr [i]), i composed of i actions a. Each state (robot position and action) is represented by discrete values. When a room is represented by a two-dimensional plane composed of an orthogonal coordinate system of X and Y, each position is represented by a discrete representation of the X axis and the Y axis. That is, as shown in FIG. 2, the room (two-dimensional plane) is divided by a grid, and each grid corresponds to each position. In each grid, “present / none” of the obstacle is set in advance.

[Definition of robot motion]
The action subject is each robot arranged in the room. The action a [i] of the robot i takes one of a total of five types, that is, stationary and movement of one lattice in the vertical and horizontal directions. For example, a [i] ∈ {0,1,2,3,4}
0: stationary
1: Move by one grid in the direction in which the X coordinate value increases on the two-dimensional plane (to the right in Fig. 2)
2: Move one grid in the direction of increasing Y-coordinate value on the two-dimensional plane (downward in Fig. 2)
3: Move one grid in the direction of decreasing X-coordinate value on the two-dimensional plane (leftward in Fig. 2)
4: Suppose that one grid moves in the direction in which the Y coordinate value decreases on the two-dimensional plane (upward in Fig. 2).

[Problems in search calculation]
The Markov state space in such a mission environment has a state of the number of dimensions of the number of robots × 2, and the number of selectable actions exists by the number of robot actions (= 5). For example, if the number of robots is 50 and the number of grids in the vertical and horizontal directions of the room is 20, the number of states becomes 20 to the 100th power, and the amount of resources required for the search calculation becomes enormous. Each time the number of robots increases by one, the number of states will increase 400 times.

  As explained in [Problem Setting], even if the constraint condition that robots are in contact with each other is incorporated, it is difficult to reduce the fundamental amount of calculation, which is a big problem when using multiple robots. .

  Specifically, for example, in the problem of guiding a large number of robots to a plurality of target positions, even though a route for reaching one position can be obtained by search calculation, it is possible to determine which target for each robot. The problem is whether to allocate the position. If this target position allocation is not successful, a robot that has reached the target position early will stay in a position that hinders the movement of the robot that comes later, making it difficult to form a robot platoon as a whole. End up. In order to avoid such a situation, considering how to allocate the target position to each robot by searching, there is a way to allocate to the target position by the factorial of the number of robots. The load on the robot increases dramatically with the number of robots.

  In addition, the search calculation when considering the search calculation for the robots to move while sharing one side with each other also takes into account the mutual movement of each robot. On the other hand, it increases exponentially.

[Introduction of two action plans]
Therefore, in this embodiment, as one of the measures for solving these calculation load problems, the search calculation for determining the robot motion is divided into two. Here, as a preparation for this, a robot forming a certain column Ga considers Gb as the shape of the next column to be formed. Between the formations Ga and Gb, there are robots that exist in the formation Ga and that do not exist in the formation Gb, and robots that exist in the formation Gb and do not exist in the formation Ga (FIG. 4). reference). The former is a tail robot and the latter is a head robot. In the present embodiment, the formation Ga and the formation Gb are defined so that the robot at the position of the head robot is the first robot in the movement of the robot group and the tail robot is the last robot in the movement. To do.

  Based on this definition, the first search calculation shows that the group of robots that form the formation Ga is selected as the next formation Gb in order to move to the target position while avoiding obstacles. This is an operation plan calculation for deciding whether it is okay (hereinafter also referred to as “movement plan for movement target column determination”). This search calculation is actually a calculation for determining which robot of the formation Ga is selected as the robot moving to the head robot position and the tail robot in the formation Ga.

  The second search calculation is an action plan calculation (hereinafter referred to as "each robot operation") that determines the operation of each robot when transforming from formation Ga to formation Gb while maintaining the positional relationship where the robots are in contact with each other. It is also called “operation plan”. In effect, for the head robot and tail robot that have already been determined by the movement plan for determining the destination platoon, the robot is expelled from the position of the tail robot and the robot is guided to the position of the head robot in the platoon Gb. Search calculation.

  Search calculation using dynamic programming is used for both the former and the latter, but here, the dynamic calculation method in the Markov decision process is used in the search calculation for determining the head robot. Further, the determination of the former tail robot and the latter search calculation use a dynamic programming method such as a Dijkstra method using information on the adjacent relationship between the robots. Note that the value function Q (s, a) (details will be described later) used for determining the former head robot is calculated in advance before the group of robots starts moving from the start position. The real former head robot using Q (s, a) is performed in real time while moving the decision robot. The latter search calculation and the determination of the tail robot using it are also performed in real time while the robot is moving.

[Two types of void control]
In order to reduce the calculation load of these two search calculations, this embodiment introduces the concept of void control. First, the term “void” as used herein refers to a gap that can be restored to the original position after a robot has moved 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 planning problem can be thought of as a single void motion plan. For this reason, introducing the concept of void control is suitable for reducing the search calculation load in the group formation problem of group robots.

  First, consider the behavior of the head robot that acts as the head of the movement of the robot group in the movement plan for the movement target column determination. In this embodiment, it is assumed that one entrance position Pe is provided in the target platoon area G, and the head robot cannot enter the target platoon area G from other positions. In addition, all robots that have once entered the target platoon area G will never be able to leave the target platoon area G again. Under this condition, the robot routing problem until the head robot outside the target row area G reaches Pe can be obtained by solving the search problem for guiding one robot to the entrance position Pe. The obtained solution may be used for selection and guidance of the head robot. Regarding the movement of the head robot in the target row area G, the same is done for the guidance of the void, focusing on the movement of the void. That is, the desired behavior of the head robot in the target platoon area G is that the head robot appropriately moves away from the entrance position Pe and fills the target platoon area G while being scattered in each place in the target platoon area G. Is to go. If this is seen as the movement of the void, each time the robot enters the target platoon area G from the entrance position Pe, the void goes out of the target platoon area G from the entrance position Pe accordingly. At this time, it is an ideal action that all the voids in the target platoon area G move toward the single entrance position Pe. In other words, in order to guide the head robots in the target platoon area G so as to be properly scattered in the target platoon area G, search calculation is performed for each void located in the target platoon area G to reach the entrance position Pe. What is necessary is just to make it implement | achieve by moving a head robot so that the motion of the void calculated | required in that way may be carried out. With this concept, the operation load (calculation of the value function Q (s, a)) for the robots at all positions to move toward the entrance position Pe only needs to be performed once. Less.

  Next, consider that the robot group that maintains the formation Ga transforms into the formation Gb. At this time, the movement of the robot group from the formation Ga to the formation Gb can be regarded as a process in which one void at the position of the head robot moves to the position of the tail robot (FIGS. 4 and 4). 5). Such a motion of the void can be calculated by a motion plan of one void with the position of the head robot as the start position and the position of the tail robot as the goal position, and the calculation load is small. As a constraint condition for the movement of the void to be considered in this calculation, it is only necessary to provide a restriction that the robot follows the position where the robot exists when the void moves.

[Introduction of 4 mass robot units]
Further, in the present embodiment, as shown in FIG. 6, four robots adjacent to the rice field are defined as one unit (hereinafter also referred to as “robot unit”), and the robot is a rice field robot. Move while maintaining the unit. In other words, every four robots constitute one robot unit, and each of the four robots constituting one robot unit maintains a state of being adjacent to another robot constituting one robot unit in two directions. Move. This group of robot units is controlled so as to share one side and move while contacting each other.

  The reason why such four robots are moved as one unit is that, as long as the robot moves in such a state, each robot will be able to This is because it is not necessary to destroy the positional relationship that touches on one side. That is, this is because the calculation load for considering the connection between the robots is reduced in each robot operation plan.

  That is, the movement plan for the movement destination platoon determination described above is performed for the movement of a group made up of four robots. The head robot and tail robot described above are in units of head robot and tail robot each composed of four robots. Each motion plan for robot operation guides the robot to four robot positions included in the head robot unit, and searches and calculates an operation for driving off the four robots from the robot included in the tail robot unit position.

Here, it is assumed that four squares corresponding to the robot units formed by the four robots are one square unit (hereinafter also referred to as “mass unit”), and a state space is formed with one square unit as one state. In other words, when the position of the robot unit is (Xr_unit [j], Yr_unit [j]) (j = 0,1,2, ... j_max-1), the robots belonging to that robot unit are i1, i2, i3 , i4,
Xr [i1] = 2 × Xr_unit [j]
Yr [i1] = 2 × Yr_unit [j]
Xr [i2] = 2 × Xr_unit [j] + 1
Yr [i2] = 2 × Yr_unit [j]
Xr [i3] = 2 × Xr_unit [j]
Yr [i3] = 2 × Yr_unit [j] + 1
Xr [i4] = 2 × Xr_unit [j] + 1
Yr [i4] = 2 × Yr_unit [j] + 1
It is. If the total number of robots p is not a multiple of 4, there will be fractional robots, but all of these robots will be rounded down in the movement plan for moving to the target team (not present) In the motion plan for each robot operation, it is treated as a member of the tail robot unit.

  A set of target positions for determining a head robot in units of robots is defined as GU (hereinafter also referred to as “target unit area unit GU”). The target platoon area unit GU is composed of mass units in which four robot positions are united in the same manner as the robot unit. As shown in FIGS. 7 and 8, the masses constituting the target platoon area unit GU are the target units. It is set so as not to protrude in the convoy area G. At this time, there may be a robot target position that belongs to the target platoon area G but does not belong to the target platoon area unit GU. It is assumed that the target formation area G satisfies the following two conditions. (1) The portion where the target row area G protrudes from the target row area unit GU is included in the mass unit adjacent to the target row area unit GU (see FIG. 7). (2) The portion where the target row area G protrudes from the target row area unit GU is not an L-shape that protrudes like a hook shape (see FIG. 7). In this way, in order to set the target platoon area G and the target platoon area unit GU, is the total number of robot units used in the movement platoon determination action plan equal to the number of robot units in the target platoon area unit GU? More than that. Therefore, although the number of robot target positions belonging to the target platoon area G but not belonging to the target platoon area unit GU may exceed four, the present embodiment can be used even in such a case. If the robots are filled in all the target platoon area units GU, the movement plan for the movement platoon determination is not performed thereafter. Thereafter, an operation for filling the robot in a target position that does not belong to the target platoon area unit GU but belongs to the target platoon area G is calculated by each robot movement determination operation plan.

[MDP state space for action plan for determining the target team]
The Markov state space for search calculation in the movement plan for determining the movement target platoon is composed of only one state variable for each robot. That is,
State variable s = (Xr_unit, Yr_unit), action variable a∈ {0,1,2,3,4}
It is. For selection and guidance of the head robot unit, action determination is performed using one value function Q (s, a) with this state variable as an argument. The calculation of the value function Q (s, a) shall be done in advance of the task using dynamic programming. When the entrance position unit including the entrance position Pe is PeU (see FIG. 8) and the calculation is performed by dynamic programming, the reward value is high when the head robot unit moves to the entrance position unit PeU. The value 1 is given and the others are given 0 reward.

In other words, the state transition probability and reward value setting in the Markov state space necessary for calculating the value function Q (s, a) are determined by assuming that the state has moved from s to s ′ by action a. Is P (s' | s, a), for example, as an example of the setting method
(1) When s is not an obstacle and s' is the unit of mass of the destination of action a,
P (s' | s, a) ← 1
(2) When s is not an obstacle and s' is not a unit of mass for the destination of action a,
P (s' | s, a) ← 0
(3) When s is an obstacle and s' = s,
P (s' | s, a) ← 1
(4) When s is an obstacle and not s' = s,
P (s' | s, a) ← 0
It is set like this. In addition, when even one obstacle is included in the mass unit, the state s of the robot unit is set as the obstacle. For reward R,
If s '= Pe U then R (s', s, a) ← r_plus
Else If (s is in GU and s 'is out of GU) then R (s', s, a) ← -r_minus
Else If (s is out of GU and s' is in GU and s' = not PeU) then R (s', s, a) ← -r_minus
Else R (s', s, a) ← 0
It is. r_minus and r_plus are both positive values, but it is desirable that r_minus> 10 x r_plus. If the condition that the head robot unit does not enter the obstacle, can not enter the target platoon area unit GU other than the entrance position unit PeU, and can not be exited from within the target platoon area unit GU, transition is possible Probability and reward setting method is not limited to this. Since the robot unit in all the mass units only needs to perform the motion plan (calculation of the value function Q (s, a)) for the movement toward the entrance position unit PeU, the calculation load is dramatic as described above. Less. Moreover, since the number of square units is a quarter of the number of squares, the number of states is reduced and the calculation load is reduced.

  Normally, when the head robot unit in each state s performs action selection using Q (s, a), the value of the value function Q (s, a) is maximized in each state s. If action a is selected, but the value function Q (s, a) is calculated with the conditions set forth above, the head robot unit outside the target platoon area unit GU is also within the target platoon area unit GU. Both the robot units move toward the entrance position unit PeU. Therefore, in this embodiment, it is assumed that an action is selected according to the following rules. This action policy is defined as action policy Policy_G.

(Action Policy Policy_G)
(1) When s is within GU, the head robot unit is an action that does not move to the position of other robot units or the position of an obstacle, and does not go out of the GU, and Q ( An action that minimizes Q (s, a) is selected from actions a that satisfy s, a) <Q (s, 0). If there is no such action, action a = 0 (still) is selected.
(2) When s is outside GU, the head robot unit is an action that does not move to the position of another robot or an obstacle, and satisfies Q (s, a)> Q (s, 0) Select the action that maximizes Q (s, a) among the actions a. If there is no such action, action a = 0 (still) is selected.

  In this way, the head robot unit that has once entered the GU according to (1) moves to a position in the GU as far as possible from the entrance position unit PeU as far as possible. On the other hand, according to (2), the head robot unit outside the GU moves toward the entrance position unit PeU and can take an action to enter the GU from the entrance position unit PeU. Also, collisions with other robots and obstacles can be avoided. In addition, in (1), when there are two or more actions a that satisfy the condition, if the destination robot unit moved by the action a is not in contact with a robot unit other than the source robot unit, such robot unit Give priority to action a moving to.

(Head determination process Head_Robot_Decision)
Using the above value function Q (s, a) and action policy Policy_G, the method of determining the head robot unit of the row Gb to which the group of robots constituting the row Ga should move next is as follows. is there. This process is also referred to as a head determination process Head_Robot_Decision.
(1) For each robot unit j in the GU, the minimum value Qmin (j) of Q (s, a) in all actions a at the position s of the robot unit j is calculated.
(2) For each robot unit j in the GU, ranking is performed in ascending order of Qmin (j).
(3) For each robot unit j outside the GU, the maximum value Qmax (j) of Q (s, a) in all actions a at the position s of the robot unit j is calculated.
(4) For each robot unit j outside the GU, ranking is performed in descending order of Qmax (j).
(5) Add the number of robot units in the GU to the rank value of each robot unit j outside the GU.
(6) Set the variable head_num ← 0.
(7) Select the robot unit j at the head_num position of the rank value calculated in (6) above, and set j_head ← j. The behavior a_head of the robot unit j_head is calculated by the behavior policy Policy_G. If a_head = 0 is not satisfied, the robot unit j_head is selected as the robot unit that moves to the head robot unit position. The position where the robot unit j_head is moved by the action a_head is set as the head robot unit position, and the head robot unit is set as j_new. When a_head = 0, increment head_num and repeat (7).

  In the above processing, when the robot unit exists only outside the GU, the robot unit is as close to PeU as possible, or when there is a robot unit within the GU, the robot unit with the smallest Q_min (j) value The action selected by the action policy Policy_G is selected as a head robot unit that is not stationary.

(Robot unit group order determination processing Unit_Joretu_Decision)
Next, a method for determining the tail robot unit position will be described. First, how far each robot unit is from the head robot unit is calculated. This calculation can be performed by a dynamic programming method such as the Dijkstra method. The method used in this embodiment will be described below as an example. This process is also referred to as a robot unit group order determination process Unit_Joretu_Decision.
(1) For each robot unit, check the number of the robot unit adjacent in the four directions of up, down, left and right. When the robot unit j_next is adjacent to the movement direction of the action a of the robot unit j, the value of the next_u [a] [j] variable is set to j_next (next_u [a] [j] ← j_next). When there is no robot, the value of the next_u [a] [j] variable is set to j_max (next_u [a] [j] ← j_max). However, j_max is the number of robot units.
(2) The value of the ordinal variable value Joretu [Xr_unit] [Yr_unit] at each position in the state space (Xr_unit, Yr_unit) is initialized to j_max (Joretu [Xr_unit] [Yr_unit] ← j_max).
(3) The order variable value of the robot unit j_head is initialized to the value of Joretu [Xr_unit [j_head]] [Yr_unit [j_head]] to j_min (Joretu [Xr_unit [j_head]] [Yr_unit [j_head]] ← j_min) . However, the value of j_min is, for example, j_min = 0.
(4) Joretu [Xr_unit [next_u [a] [j]]] [when the value of next_u [a] [j] is not j_max for all actions a of each robot unit j other than the robot unit j_head Check the value of Yr_unit [next_u [a] [j]]], and if the minimum value plus 1 is smaller than the current Joretu [Xr_unit [j]] [Yr_unit [j]] Is assigned to Joretu [Xr_unit [j]] [Yr_unit [j]] (Joretu [Xr_unit [j]] [Yr_unit [j]] ← Joretu [Xr_unit [next_u [a] [j]] [Yr_unit [next_u [ a] [j]]] + 1).
(5) Repeat (4) until Joretu value is no longer updated in the process of (4). By this processing, the order variable value Joretu [Xr_unit [j]] [Yr_unit [j]] of the robot unit j located at a position away from the robot unit j_head is updated so as to become a larger value (see FIG. 9). In addition, the numerical value in the parenthesis of FIG. 9 represents an ordinal variable value Joretu [Xr_unit [j]] [Yr_unit [j]].

(Tail robot decision processing Tail_robot_Decision)
The robot unit group order determination process Joretu_Decision is completed, and the robot unit at the position where Joretu [Xr_unit [j]] [Yr_unit [j]] is maximized is defined as the tail robot unit j_tail. The process for determining the tail robot unit is also referred to as a tail robot determination process Tail_robot_Decision. In the above processing, the robot unit farthest from the head robot unit is set as the tail robot unit.

(Operation plan processing Next_Formation_Decision)
The above process is summarized, and the movement plan determination operation plan process Next_Formation_Decision is performed as follows.
(1) The head determination process Head_Robot_Decision is performed.
(2) Perform the order determination process Unit_Joretu_Decision in the robot unit group.
(3) Tail robot determination processing Tail_robot_Decision is performed.
(4) After the robot unit j_head performs the action a_head, a new head robot unit j_new is set at the moved position, and the tail robot unit position can be specified in (3). The robot unit at the tail robot position j_tail is deleted from Ga, and the head robot unit j_new is added to the formation Ga to form a formation Gb (see FIG. 9).

[Simplified action plan process for determining the destination column]
Note that the movement plan determination operation plan process Next_Formation_Decision may be simplified as follows.
(1) At present, the robot unit position where the four robots are accommodated is specified and set as an element of the robot unit of the formation Ga.
(2) The head determination process Head_Robot_Decision is performed.
(3) After the robot unit j_head performs the action a_head, a new head robot unit j_new is set at the position after the movement, and the robot unit column composed of the head robot unit j_new and the robot unit j_head is defined as the column Gb. (See FIG. 10). A group of robots not included in the convoy Gb is referred to as a tail robot group G_tail. At this time, it has not been determined which robot included in the tail robot group G_tail is to be deleted.

  In each robot motion determination motion plan to be described later, the robot unit j_head and the head robot unit j_new are not directly used for the calculation and may be omitted. Instead, the robot unit buried by the four robots is identified each time in the process (1) in the simplified movement plan determination process.

[Operation plan for determining each robot operation]
Since the robot unit j_head and the head robot unit j_new are determined in the movement plan for determining the movement target column, and the next column Gb is determined, the movement from the current column Ga to the next column Gb is realized by the movement of each robot. Search calculation is performed in each robot motion determination motion plan.

  First, in each robot motion determination motion plan, fractional robots that do not belong to any robot unit in the formation Gb are specified, and those robots belong to the tail robot group G_tail (see FIG. 10).

  In this embodiment, since the robot group moves while maintaining the robot unit of four robots as a set, when considering the connection maintenance of each robot when performing void control, the tail robot The unit j_tail (as described above, the tail robot unit in each robot motion determination motion plan is a fractional robot that does not belong to any robot unit) and even the movement of voids near the head robot unit j_new Other than that, there is no need to consider where the void is in the robot group.

In each robot motion determination motion plan, the following two modes exist.
Mode 1: GU is not filled with robots.
Mode 2: When GU is filled with robots.
(Mode 1)
First, the operation of each robot motion determination motion plan when the mode 1 GU is not satisfied by the robot will be described.

  First, of the robots belonging to the robot unit j_head, the two robots in contact with the head robot unit j_new are designated as robots i_move_11 and i_move_21 (see FIG. 11), and the movement directions of the robots i_move_11 and i_move_21 and the action a_head are reversed. The robots in contact with the directions are referred to as robots i_move_12 and i_move_22, respectively. If the robot i_move_11, i_move21 belongs to the head robot unit j_new and there is a robot that touches in the direction of action a_head, the robots are set to i_move_101, i_move_201, respectively, and the direction of action a_head at the position of robot i_move_101, i_move201 If there is a robot at the position where it touches, i_move_102 and i_move_202 are assigned to the robots, respectively. The operation in mode 1 is performed according to the following procedure.

(Procedure 1) When both of the robots i_move_101 and i_move102 exist (see FIG. 11, the robots i_move_101 and i_move_102 indicated by broken lines in FIG. 11), go to the procedure 7. In other cases, when the robot i_move_101 exists (see FIG. 12A), the robot i_move_11, the robot i_move12, and the robot i_move101 are moved in the a_head direction (see FIG. 12B). In other cases, when the robot i_move_101 does not exist (FIG. 13A), the robot i_move_11 and the robot i_move12 are moved in the a_head direction (FIG. 13B).

(Procedure 2) The void generated in the procedure 1 (the position where the robot i_move12 was originally) is set as a position void_end (see FIGS. 12B and 13B).

(Procedure 3) By filling the position void_end with a robot other than the robot i_move_11 and robot i_move12, the robot farthest from the position void_end among the robots belonging to the tail robot group G_tail is Move closer to the minute position void_end. For example, the transition is made from FIG. 13B to FIG. 14A.

(Procedure 4) When the robot i_move_101 or the robot i_move_102 exists (see FIGS. 12 and 13, the robot i_move_102 indicated by a broken line in FIG. 13 exists), go to the procedure 7. If neither exists (see FIG. 14A), the robot i_move_11, the robot i_move12, and the “robot in contact with the robot i_move12 in the direction opposite to the moving direction of the action a_head” are moved in the a_head direction (see FIG. 14B).

(Procedure 5) The void generated in the procedure 4 (the position where the robot i_move12 was generated before the execution of the procedure 1) is set as a position void_end.

(Procedure 6) By filling the position void_end with a robot other than the robot i_move_11 and robot i_move12, the robot farthest from the position void_end among the robots belonging to the tail robot group G_tail is Move closer to the minute position void_end.

  As described above, the lower mass of the head robot unit j_new is filled with the robot by the procedure 1 to the procedure 6. A similar process is performed in steps 7 to 12, and the upper square of the head robot unit j_new is filled with the robot. Since the same process may be performed on the upper square of the head robot unit j_new, the illustration is omitted.

(Procedure 7) When both the robots i_move_201 and i_move202 exist (see FIG. 11), the operation plans for determining robot operations in mode 1 are terminated. This means that the head robot unit j_new is filled with 4 robots.

  In other cases, when the robot i_move_201 exists, the robot i_move_21, the robot i_move22, and the robot i_move201 are moved in the a_head direction. In other cases, when the robot i_move_201 does not exist, the robot i_move_21 and the robot i_move22 are moved in the a_head direction.

(Procedure 8) The void generated in the procedure 7 (position where the robot i_move22 was originally) is set as a position void_end.

(Procedure 9) By filling the position void_end with robots other than the robots i_move_21 and i_move22, the robot belonging to the tail robot group G_tail, the robot farthest away from the position void_end from the current position is 1 Move closer to the void position void_end.

(Procedure 10) When the robot i_move_201 or the robot i_move_202 exists, the process ends. If neither exists, the robot i_move_21, the robot i_move22, and the “robot in contact with the robot i_move22 in the direction opposite to the movement direction of the action a_head” are moved in the a_head direction.

(Procedure 11) The void generated in the procedure 10 (the position where the robot i_move22 was created before the execution of the procedure 7) is set as a position void_end.

(Procedure 12) By filling the position void_end with robots other than the robots i_move_21 and i_move22, the robot belonging to the tail robot group G_tail, the robot farthest away from the position void_end from the current position is 1 Move closer to the void position void_end.

  When the robot unit j_head is positioned at the head of the movement of the robot unit group, there is usually no other robot in the head robot unit j_new (in other words, four robots i_move_101, i_move_102 shown by broken lines in FIG. 11). , i_move_201, i_move202 does not exist), but depending on the starting position row (see FIG. 15), in the moving direction of the robot unit j_head, any one of at most 3 of the robots i_move_101, i_move_102, i_move_201, i_move202 that do not constitute a robot unit There may be one. In that case, the robots i_move_101, i_move_102, i_move_201, i_move202 are taken in as a part of the head robot unit by performing the steps 1 to 12. In other words, if at least three of robot i_move_101, i_move_102, i_move_201, i_move202 exist, the four robots i_move_11, robot i_move_12, robot i_move_21, and robot i_move_22 that constitute the robot unit j_head are used as the head robot unit j_new. And at least three of the existing robots i_move_101, i_move_102, i_move_201, i_move202, and four robots i_move_11, robot i_move_12, robot i_move_21, and robot i_move_22 (replenish the missing parts) ) Constitute a head robot unit j_new. For example, in the case of FIG. 15, the robot i_move_201, i_move202 and the robot i_move_11, robot i_move_12 constitute the head robot unit j_new.

  Among the above processes, procedures 3, 6, 9, and 12 are common processes. Hereinafter, this processing is also referred to as void control processing Robot_Void_Control, and this processing will be described.

(1) The i_tail value when this processing Robot_Void_Control was executed last time is stored in the variable pre_i_tail (pre_i_tail ← i_tail). If this is the first time that this process is executed, pre_i_tail ← −1.

(2) Calculate how far each robot is from the position void_end. Hereinafter, this processing is also referred to as robot order calculation processing Robot_Joretu_Decision. In the robot order calculation process Robot_Joretu_Decision, an order variable value Joretu [Xr] [Yr] at each position is calculated. The robot order calculation process Robot_Joretu_Decision will be described later.

(3) (a) When pre_i_tail is a value other than -1 (when this processing is performed for the second time or later), the robot pre_i_tail belongs to the position of the robot unit to which the previous time step belonged. If there is a robot outside G, select the robot that is farthest from void_end (the robot with the largest joretu value) and set it as the robot i_tail (the number of the selected robot is i_tail Assigned to). (b) When pre_i_tail is a value other than -1, no robot belongs to the position of the robot unit to which the robot pre_i_tail belonged one step ago, and there are four robots in the robot unit position. If there is a robot unit position that is not filled with, the robot that is in such a robot unit, is outside G, and is farthest from the void_end among them (the robot that has the highest joretu value) Is selected as robot i_tail. By performing the selection as shown in (b), a robot unit filled with four robots is configured, and the number of robots that are not included in the robot unit is less than four. (c) When pre_i_tail is a value other than -1, no robot belongs to the position of the robot unit to which robot pre_i_tail belonged one time step before, and no other four robots are filled If there is no robot unit position, select the robot belonging to the tail robot group G_tail that is far from void_end among the robots outside G (the robot with the highest joretu value) i_tail. (d) When pre_i_tail is -1 (when this processing is performed for the first time), among the robots belonging to the tail robot group G_tail, those that are outside G but farthest from void_end (joretu The robot having the largest value is selected as a robot i_tail. For example, FIG. 16 shows an example in which the robots i_move_11 and i_move_12 are moved in the a_head direction in the procedure 1 of mode 1 in the state of FIG. 11, the void exists at the position void_end, and the robot i_tail is set.

(4) The following position void_start is obtained using the robot i_tail. It is possible to move 2 squares or more in the same direction by tracing the adjacent robot from the position of the robot i_tail, and the robot unit to which the robot that has moved 2 squares or more belongs is not the robot unit j_head, but within 4 Look for a direction that satisfies the condition that two robots belong. An action moving in the same direction as that direction is a_tail (see FIG. 16). Subsequently, the robot unit number j_start to which the robot that has moved two squares or more in the direction of the action a_tail belongs is specified. In other words, two or more robots are adjacent to each other in the same direction d from the position of the robot i_tail, and in that direction d, the robot i_tail is at a square (two or more positions away). When the robot unit to which any one of the adjacent robots belongs is not the robot unit j_head and the condition that four robots belong to the condition, the action to move in the direction d is a_tail To do. The above-mentioned condition (a condition that two or more robots that are located at two or more positions away from the robot i_tail belong continuously, are not robot units j_head, and four robots belong to them) The robot unit number j_start that satisfies the condition is specified. Since there can be a plurality of robot units that satisfy the above conditions, an arbitrary robot unit can be specified as the robot unit j_start.

From the action a_tail and the position of the robot unit j_start (Xr_unit [j_start], Yr_unit [j_start]), the position void_start is set as follows.
When a_tail = 1: The X coordinate of void_start is 2 × Xr_unit [j_start] +1, and the Y coordinate is Yr [i_tail].
When a_tail = 2: The X coordinate of void_start is Xr [i_tail], and the Y coordinate is 2 × Yr_unit [j_start] +1.
When a_tail = 3: The X coordinate of void_start is 2 × Xr_unit [j_start], and the Y coordinate is Yr [i_tail].
When a_tail = 4: The X coordinate of void_start is Xr [i_tail], and the Y coordinate is 2 × Yr_unit [j_start].

(5) The movement path of the void from the position void_start to the position void_end is calculated. Hereinafter, this processing is also referred to as void path calculation processing Void_Trajectory_Decision.

(6) Follow the void movement path calculated in (5) from void_end to _void_start and fill the void. Hereinafter, this processing is also referred to as void movement processing Void_Motion.

  In order to maintain the connection state of the robot when the robot belonging to the tail robot unit is moved, the process (4) is described as follows: “The position of the void is a robot included in the robot unit adjacent to the tail robot unit. The position of the robot in contact with the tail robot unit must not be considered. Therefore, the control system controls the behavior of the p robots so that no void exists at the position of the robot in contact with the tail robot unit among the robots included in the robot units adjacent to the tail robot unit. As described above, in each robot operation plan, the fractional robot i_tail in FIG. 16 is treated as a robot belonging to the tail robot unit. In FIG. 16, when the void uses the movement path NG, the robot i_tail is no longer adjacent to the robot in the vertical and horizontal directions, and all of the p robots cannot form one group, and the robots are connected to each other. It cannot be maintained. Therefore, control is performed so that the void at the position void_end is once moved to the position void_start and then moved to the position of the robot i_tail at a stroke. By performing such behavior control, all the p robots form one group, and the connection between the robots can be maintained. Hereinafter, robot order calculation processing Robot_Joretu_Decision, void path calculation processing Void_Trajectory_Decision, and void movement processing Void_Motion for realizing such control will be described.

(Robot order calculation processing Robot_Joretu_Decision)
The robot order calculation processing Robot_Joretu_Decision can use the Dijkstra method or the like. For example:

(1) For each robot, check the number of the robot that is adjacent in the four directions. When the robot i_next exists adjacent to the movement direction of the action a of the robot i, the value of the next [a] [i] variable is set to i_next. When there is no robot, the value of the next [a] [i] variable is set to p (representing the number of robots).

(2) The value of the ordinal variable value Joretu [Xr] [Yr] at each position in the state space (Xr, Yr) is initialized to p (Joretu [Xr] [Yr] ← p).

(3) The value of the ordinal variable value Joretu at the position of void_end is set to 0 (Joretu [Xr] [Yr] ← 0). Furthermore, the value of the ordering variable value Joretu of the positions of all the robots moved by the action a_head immediately before executing this process is initialized to -1. In addition, the robot unit to which it belongs is initialized to -1 for the ordering variable value Joretu of the position of the robot that is not filled with four robots. Further, the Joretu value of the robot position adjacent in the opposite direction of the action a_tail from the position of void_start is set to -1.

(4) The value of next [a] [j] is not p for all actions a of each robot i, except for the position of void_end and the position of the robot that is adjacent to the movement direction of action a_head from void_end Joretu [Xr [next [a] [i]]] [Yr [next [a] [i]]] and Joretu [Xr [next [a] [i]]] [Yr [next If the value of [a] [i]]] is not -1 and the minimum value plus 1 is less than the current Joretu [Xr [i]] [Yr [i]] , Assign the value to Joretu [Xr [i]] [Yr [i]] (Joretu [Xr [i]] [Yr [i]] ← Joretu [Xr [next [a] [i]]] [Yr [next [a] [i]]] + 1).

(5) Repeat (4) until Joretu value is no longer updated in the process of (4).

  By this process, (a) the position of all robots moved by action a_head, (b) if the robot unit to which the robot belongs is not filled with 4 robots, other robots belonging to that robot unit The position of the robot, (c) excluding the position of the robot that is adjacent to the position of void_start in the opposite direction of action a_tail, and the order variable value Joretu [Xr [i]] [Yr [i]] that is away from the position void_end Updated to be a value. The numerical values in the square brackets in FIG. 16 indicate examples of values of the ordinal variable value Joretu when there is no update.

(Void path calculation processing Void_Trajectory_Decision)
The void path calculation process Void_Trajectory_Decision is as follows.

(1) Position void_start is the first position of void trajectory (X, Y) = (void_trj_x [h], void_trj_y [h]) (h = 0,1,2,3...).
(2) Set orbital number h_trj ← 0.
(3) From the current void trajectory position (void_trj_x [h_trj], void_trj_y [h_trj]), among the robots i that are adjacent in all directions, the order value Joretu [Xr [i]] [ Yr [i]] is other than -1 and the position of robot i smaller than Joretu [void_trj_x [h_trj]] [void_trj_y [h_trj]] is the next void trajectory position (void_trj_x [h_trj + 1], void_trj_y [h_trj + 1]). At this time, the same action number as the movement direction of the void is stored in the void action history a_void [h_trj]. Increment h_trj.
(4) Repeat (3) until the current void trajectory position is equal to the position void_end.

By this processing, a void path from the position void_end to the position void_start is calculated.
(Void_Motion)
The void movement process Void_Motion is, for example, as follows. A robot moving in the same direction is moved at once along the calculated void trajectory. Of course, you may move one unit at a time without moving it at once.

(1) Set h_trj_buffer ← h_trj-1.
(2) Decrement h_trj and store the value of a_void [h_trj] in a_void_buffer.
(3) If h_trj = 0 is not satisfied, h_trj is decremented and it is determined whether a_void [h_trj] = a_void_buffer. If a_void [h_trj] = a_void_buffer, (3) is repeated. Otherwise (when a_void [h_trj] ≠ a_void_buffer), the void trajectory (void_trj_x [h_trj_buffer], void_trj_y [h_trj_buffer]) to (void_trj_x [h_trj + 1], void_trj_y [h_trj + 1]) Move all robots with action values stored in a_void_buffer and go to (4). By this process, the robot moving in the same direction is moved at a time. When h_trj = 0, the robot in the position from void trajectory (void_trj_x [h_trj_buffer], void_trj_y [h_trj_buffer]) to (void_trj_x [0], void_trj_y [0]) is the action value stored in a_void [0] Move to go to (5).
(4) Increment h_trj and return to (1).
(5) All robots that are adjacent to the robot i_tail in the direction of the action a_tail and reach the position void_start are moved by the action a_tail. In addition, this movement needs to move all together, not one by one. By this process, the void at the position void_start is moved to the position of the robot i_tail at once, and the robot adjacent to the robot i_tail is prevented from being lost.

  Until the GU is filled with the robot, after the movement planning process Next_Formation_Decision for determining the movement destination platoon, the process of moving the robot using mode 1 (procedure 1 to procedure 12) is repeated (see FIGS. 8 and 17 to 19). ). When GU is satisfied with the robot, it shifts to mode 2.

(Mode 2)
Next, the operation of each robot motion determination motion plan when the mode 2 GU is satisfied by the robot will be described.

(Select i_start)
In mode 2, the head robot unit is not used when selecting the head robot. The number of the first robot is i_start. The start_select [i] variable is a variable for storing the number of times the robot i is selected as the first robot, and is initialized to 0 before the robot starts moving (start_select [i] ← 0).

  First, the first robot i_start when the processing of this mode 2 is executed in the previous step is adjacent to the moving direction a_start of the robot i_start in the previous step from the position after the movement in the previous step. If there is a “position that does not belong to GU but belongs to G and does not have any other robot”, robot i_start is continuously selected as the first robot. Increment start_select [i_start].

If not, the robot i that has not been selected as the first robot so far, and that is adjacent to the "position that does not belong to GU and belongs to G, where no robot exists" Thus, when the action to move to the adjacent target position is a_start, the robot that does not satisfy the following condition 1 is selected as the first robot i_start. Increment start_select [i_start]. The robot i_start is preferentially selected from those belonging to the entrance position unit PeU to the target position. (When the number of robots remaining outside G decreases to 4 or less, if i_start is selected from the entry position unit PeU, the robot unit j_start calculated in step 3 in mode 2 dictated by robot i_start (This is because the present embodiment cannot cope with such a case.)
Condition 1: For a robot i, there are three positions belonging to G that do not belong to GU among the positions of robot units adjacent to robot unit j to which the robot belongs in the direction of action a_start. There are two or more positions that are not adjacent to the unit j.

FIG. 20 shows an example satisfying the condition 1. Note that the robot i ₁ of the robot unit j ₁ in FIG. On the other hand, since the robots i ₂ and i ₃ belonging to the robot unit j ₂ in FIG. 20 do not satisfy the condition 2 (there is only one position that is not adjacent to the robot unit j), they can be selected.

The operation in mode 2 is as follows.
(Procedure 1) When the robot i_start is selected for the second time (start_select [i_start] = 2), the robot i_start, the robot i_start, and the robot a_start are adjacent to each other, and the robot a_start is the opposite direction. To move the adjacent robot in the a_start direction. When the robot i_start is selected for the first time, the robot i_start, the robot i_start, and the action a_start are moved in the direction opposite to the a_start direction. Note that since the portion where the target row area G protrudes from the target row area unit GU is assumed to be included in the mass unit adjacent to the target row area unit GU, start_select [i_start] is 1 or 2.
(Procedure 2) The void generated in Procedure 1 (the original position of the robot that moved at the end in Procedure 1) is defined as a position void_end.
(Procedure 3) By filling the position void_end with a robot other than the robot moved by action a_start in step 1, among the robots belonging to the tail robot unit i_tail, the robot farthest from the position void_end Move closer to the position void_end by 1 square from the position.

  Procedure 3 is the same as mode 1.

  The above processing is repeated until the robot is filled in G (see FIGS. 19, 21, and 22).

<Action control system 100 according to the first embodiment>
The behavior control system 100 according to the first embodiment summarizes the overall operation configured by the processes described above.

(1) The value function Q (s, a) used for the movement plan for determining the movement target column is calculated by the dynamic programming method of MDP.
(2) At the start position, specify the robot unit position where the four robots are housed, and set it as an element of Ga robot unit.
(3) Repeat (4) and (5) below until the robot is filled in all G.
(4) If the GU is not filled with a robot, the movement plan determining movement plan process Next_Formation_Decision is executed. Do nothing if filled.
(5) When the GU is not filled with a robot, mode 1 of each robot motion determination motion plan process is executed. If GU is filled with robot, execute mode 2.

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

  FIG. 23 is a functional block diagram of the behavior control system 100 according to the first embodiment, and FIG. 24 shows an example of the processing flow. As shown in FIG. 23, the behavior control system 100 includes an operation planning unit 110, a behavior selection unit 120, an adjacent state determination unit 124, a position update unit 123, a position determination unit 126, a storage unit 140, and communication. Part 150 and input part 160. The action selection unit 120 includes a movement platoon determination operation planning unit 121 and each control target object operation planning unit 122.

  Hereinafter, a case where the control target to be controlled is a robot will be described as an example. Of course, the control object may be other than the robot as long as it can be a control target.

  In the present embodiment, the behavior control system 100 controls the behavior of p robots and is mounted on one of the p robots. Note that the p-1 robot on which the behavior control system 100 is not mounted also includes the communication unit 150 and the adjacent state determination unit 124.

<Operation Planning Unit 110>
The motion planning unit 110 calculates the value of the value function Q (s, a) in advance by dynamic programming before starting the mission action of the robot (S110) and stores it in the storage unit 140. Here, the calculation of the motion planning unit 110 may be replaced with reinforcement learning (eg, Q learning) using one robot unit. If the value function Q (s, a) is calculated by a separate device and stored in the storage unit 140 in advance before starting the robot's mission behavior, the behavior control system 100 includes the motion planning unit 110. Not necessary.

  Note that the calculation of the value function Q (s, a) is as described in [MDP state space for movement plan for movement target column determination].

<Input unit 160>
The input unit 160 includes an initial position (Xr0 [i], Xr0 [i]) 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.

  Note that the target position includes a predetermined entrance position Pe. Information about the entrance position Pe is also input from the input unit 160 and stored in the storage unit 140.

<Storage unit 140>
It is assumed that the storage unit 140 stores a value function Q (s, a) for each of the combinations of the position s and aε {0,1,2,3,4}. The range that can be taken by s is all the coordinates where the robot unit j in the region on the target two-dimensional plane can exist.

  It is assumed that the reward r (s) at each position s is also stored in the storage unit 140. Information about the reward r (s) at each position s is input from the input unit 160, for example.

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

<Action selection unit 120>
The action selection unit 120 extracts the value function Q from the storage unit 140.

  The action selection unit 120 controls the p robots by the method described in the above method (s120).

  The action selection unit 120 first identifies the robot unit position where the four robots are accommodated from the positions of the p robots, and sets it as the robot unit included in the formation Ga. Although the position of each robot is required, the initial position (Xr0 [i], Xr0 [i]) of each robot is input via the input unit 160 and stored in the storage unit 140 as described above. What is necessary is just to use what was calculated | required in the position determination part 126 mentioned later and memorize | stored in the memory | storage part 140 about the position of each robot after moving.

  The action selection unit 120 compares the position of each robot obtained by the position determination unit 126 and stored in the storage unit 140 with the target platoon area unit GU, and whether or not the target platoon area unit GU is all filled with robots. Is determined (s120-1). For the target platoon area unit GU and the entrance position unit PeU, the set G and the entrance position Pe of p target positions may be extracted from the storage unit 140, and may be obtained from the set G and the entrance position Pe. You may use what was used when calculating | requiring (s, a).

  If not filled, the movement plan determining action planning unit 121 of the action selecting unit 120 uses the value function Q (s, a) to determine the movement plan determining movement plan Next_Formation_Decision (or simplification). (S121), the head robot unit serves as the head of the movement when moving the p robots arranged in the set of start positions to the set of target positions. Thus, the position of the head robot unit is output.

  If not filled, each motion target motion planning unit 122 of the behavior selection unit 120 receives the position of each head robot unit and performs mode 1 of each robot motion motion plan (s122-1). A control signal is sent to each robot so that the four robots are positioned at the position of the head robot unit. Each robot behaves according to the control signal.

  When it is filled, each motion target motion planning unit 122 of the action selection unit 120 performs mode 2 of each robot motion motion plan (s122-2), does not belong to the target area unit GU, and does not belong to the target area. Select a robot that is adjacent to a target position that belongs to G and does not exist. The tip of the target position that does not belong to the target area unit GU and belongs to the target area G (maximum 2 squares ahead of the robot position) ), A control signal is sent to each robot so that the robot moves. Each robot behaves according to the control signal. For example, the action selection unit 120 collates the target area G and the target area unit GU stored in the storage unit 140, and obtains a target position that does not belong to the target area unit GU but belongs to the target area G in advance. From the position of each robot after movement, a robot that does not belong to the target area unit GU but is adjacent to the position where the robot does not exist at the target position belonging to the target area G may be selected.

  In addition, in mode 1, the process of filling the head robot unit determined in one movement plan determination action plan process Next_Formation_Decision is performed in mode 1, and in mode 2, the robot is moved to the target area unit. A process of moving to the tip of the target position belonging to the target area G (maximum 2 squares) not belonging to the GU is performed.

  In the action policy Policy_G used in the head determination process Head_Robot_Decision performed in the movement plan process Next_Formation_Decision (or simplified movement plan process for determination of the movement target party sequence), the position and obstacle of each robot unit Although an object position is required, the position of each robot unit can be acquired as described above. As for the position of the obstacle, the position of the obstacle used when learning the value function Q (s, a) may be used, or the determination result determined by the adjacent state determination unit 124 described later is used. You may use what is obtained.

<Location update unit 123>
For each i = 0, 1,..., P−1, the position update unit 123 performs the action determined by the action selection unit 120 at the current position (Xr [i], Yr [i]) of the i-th robot. Calculates the position (Xr '[i], Yr' [i]) after movement (after action) of the robot when executed, and stores the calculated (Xr '[i], Yr' [i]) The position of the i-th robot stored in 140 is updated (S125). In other words, the position update unit 123 calculates a position assumed when the robot behaves (hereinafter also referred to as “assumed position”) based on the action determined by the action selection unit 120 and updates the position of the robot. Stored in the storage unit 140. Specifically, s8 (update of position) in FIG. 10 is performed.

<Adjacent state determination unit 124>
The adjacent state determination unit 124 determines whether there is an obstacle or another robot at adjacent positions in the top, bottom, left, and right on the two-dimensional plane of the robot (S121), and stores the determination result in the storage unit 140. To do.

  Note that, as described above, the p-1 robot on which the behavior control system 100 is not mounted also includes the communication unit 150 and the adjacent state determination unit 124. Therefore, each robot i can determine whether there is an obstacle or another robot in its up / down / left / right direction in the adjacent state determination unit 124 and output the determination result to the behavior control system 100 via the communication unit 150. it can. The behavior control system 100 receives the determination result from each robot i via the communication unit 150 and stores it in the storage unit 140 together with the determination result of the adjacent state determination unit 124 included in the behavior control system 100. In addition, the p robots always have other robots in adjacent positions (4 directions) of each robot, and the group formed by the adjacent robots is a lump, so each robot i is connected via the communication unit 150. The p-1 determination results can be transmitted to the behavior control system 100 directly or via another robot. In addition, the behavior control system 100 can transmit a control signal so as to execute the selected behavior to each robot i directly or via another robot via the communication unit 150. In addition, other information can be transmitted and received between the p robots.

  Even if the robot is controlled to move, it may not be able to move as controlled by the action selection unit 120 due to some trouble (the presence of an obstacle that could not be detected, equipment failure, etc.). On the other hand, the position of the robot that did not move is the same as before the control. Therefore, by controlling so that at least one robot does not move, the actual state of the robot controlled to move using the determination result by the adjacent state determination unit 124 based on the position of the robot that did not move is used as a reference. The position after acting (hereinafter also referred to as “post-behavior position”) (Xr "[i], Yr" [i]) can be obtained. If at least one robot such as GPS is equipped with GPS, the post-movement position can be obtained in the same manner with reference to the robot.

<Position determination unit 126>
The position determination unit 126 obtains a post-behavior position using the determination result of the adjacent state determination unit 124, and determines a post-behavior position (Xr "[i], Yr" [i]) and an assumed position (Xr '[i], It is determined whether or not Yr ′ [i]) matches (S126). If they do not match, it is considered that the robot controlled to move could not move as controlled due to some trouble. In this case, at least one of the post-behavior position (Xr "[i], Yr" [i]) and the assumed position (Xr '[i], Yr' [i]) may be corrected. Various methods can be considered as the correction method. For example, all the robots that have moved may be instructed to return to the pre-control position, and the post-behavior position (Xr "[i], Yr" [i]) may be corrected, or the assumed position (Xr '[i], Yr' [i]) may be corrected according to the post-action position (Xr "[i], Yr" [i]).

  At each time step, it is determined whether or not all robots are in G (S127). If all robots are in G, the task is terminated. If not, continue the mission.

  For example, in the target position arrival determination unit (not shown), the post-action position (Xr "[i], Yr" [i]) ∈ output from the position determination unit 126 for each i = 0, 1,. It is determined whether or not G, and if (Xr "[i], Yr" [i]) ∈ G for all i, the mission is terminated. If (Xr ″ [i], Yr ″ [i]) εG is not satisfied for at least one i, the behavior selection unit 120 is controlled to be executed again.

  The processes s120 to s127 described above are performed for each time step.

<Effect>
With such a configuration, as many Markov state spaces as necessary for one robot unit are prepared, and using it, the action policy for each robot at each position is calculated using dynamic programming, By using the strategy, you can acquire an obstacle formation algorithm corresponding to an arbitrary formation shape and an arbitrary obstacle shape in the mission environment for the robot group, and keep many robots in contact with each other. You can get a formation algorithm for. That is, the calculation load is not proportional to the factorial of the number of robots, and a self-position coordinate definition type formation formation algorithm can be obtained with a low plan calculation load that can be executed in real time. Moreover, since an absolute position can be acquired by determining a relative position with respect to a stationary robot, no additional position measurement equipment is required. Or, since the absolute position can be obtained by determining the relative position of the robot with at least one GPS or the robot whose position is defined in the start state, all robots have GPS etc. It is not necessary to have.

  In addition, by controlling in units of robots, even if one of the robots in the group of robots is missing, the robots do not lose the positional relationship that they touch each other on one side. It is also difficult for the formation to collapse due to an error in the amount of movement of the robot.

<Modification>
In the present embodiment, each lattice (mass) is a square, but may have other shapes. The lattice is continuously arranged in the left-right direction and the up-down direction. Each lattice is adjacent to the other two lattices in the left-right direction and adjacent to the other two lattices in the vertical direction. In other words, each grid is adjacent to other grids only in the same direction that the robot can move. Each lattice may have any shape as long as this condition is satisfied. Further, “orthogonal” does not necessarily mean strictly “vertically intersecting”. For example, as shown in FIG. 25, each lattice may be a rhombus, and each lattice is the other two lattices. One of the adjacent directions may be the vertical direction and the other is the horizontal direction. In this case, the vertical direction and the horizontal direction are orthogonal to each other.

  In other words, the control object is in the first direction (for example, the right direction), the second direction (for example, the upward direction) that is not parallel to the first direction, and the first direction on the two-dimensional plane. On the other hand, it is possible to move in the third direction (for example, the left direction) opposite to the second direction, and in the fourth direction (for example, the downward direction) opposite to the second direction. Control is performed so that the current area is moved to one of the adjacent areas in the first direction, the second direction, the third direction, and the fourth direction from the grid. In this case, on the two-dimensional plane of the robot, the position adjacent in the first direction is the first position, the position adjacent in the second direction is the second position, the position adjacent in the third direction is the third position, Positions that are adjacent in the four directions are the fourth position, positions that are adjacent to the first position in the second direction are the fifth positions, positions that are adjacent to the second position in the third direction are the sixth positions, and positions that are adjacent to the third position are the fourth direction May be referred to as the seventh position, and the position adjacent to the fourth position in the first direction as the eighth position.

  In the present embodiment, the example in which the behavior control system 100 is mounted on one of the p robots has been shown, but behavior control may be performed on a control target on a computer. In that case, unless a trouble occurs intentionally, the controlled object moves as controlled, so the assumed position (Xr '[i], Yr' [i]) and the post-movement position (Xr "[i], Yr "[i]) matches. In such a state, an ideal action plan for each control object i may be performed. The actual robot is made to execute the action plan until the mission obtained as a result is completed. The real robot includes a communication unit 150 and an adjacent state determination unit 124. After each action is completed, the adjacent state is determined, the post-action position is obtained using the determination result, and the post-action position (Xr "[i] , Yr "[i]) and the assumed position (Xr '[i], Yr' [i]) are determined to match. If they do not match, it is considered that the robot controlled to move could not move as controlled due to some trouble. Subsequent processing may be the same as in the first embodiment, or other processing may be performed. With such a configuration, it is possible to detect at least that movement was not possible as controlled.

  In this embodiment, one position determination is performed for one action control. However, when a plurality of robots are moved in one action control, each robot is moved each time it is moved. It is good also as a structure which performs determination.

  In the present embodiment, the robot unit is composed of four 2 × 2 robots, but may be composed of M × N robots. However, M and N are each an integer of 2 or more. Note that the number of robots p is greater than or equal to the number of robots M × N included in the robot unit. Even when moving in such a state, as in the case of a 2 × 2 robot unit, even if one of the robots in the group of robots is missing, each robot is on one side of each other. There is no need to break the positional relationship that touches. If the number of M × N is increased, the number of patterns that can be acted on in learning of the value function Q (s, a) is reduced, so that the amount of calculation of learning of the value function Q (s, a) is reduced. However, in the learning of the value function Q (s, a), if at least one obstacle is included in the square unit with M × N squares as one unit, the state s of the square unit is Since it is handled as an obstacle, if the number of M × N is increased, the range of obstacles increases, and the range in which action can be performed decreases. In the first place, as many Markov state spaces as needed for one robot unit are prepared, and it is only necessary to calculate the action policy of the robot at each position using dynamic programming. The amount of learning of the value function Q (s, a) is sufficiently reduced. For this reason, in order to keep a large range in which the robot can act, it is desirable to use 2 × 2 robots as a robot unit.

<Second embodiment>
The difference from the first embodiment will be mainly described. The control method of the first embodiment is extended to a three-dimensional space. In this embodiment,
(1) Three-dimensional robot platoon.

  (2) Speed up the formation process by parallelizing void control.

(3) Reduce the computational complexity of the motion plan from O (n ² ) to O (n).

  (4) Improve the selection method of head robot unit D and guarantee application to robots of arbitrary shape composed of 24 or more robot units.

  In this embodiment, while considering the existence of a large number of robots, the calculation time required for the planned calculation is limited to the first power of the number of robots, and only sliding operations on the surfaces of other robots are possible. It is possible to perform a deformation operation from an arbitrary platoon to another arbitrary platoon in an environment where there is an obstacle while maintaining a state in which the robots that cannot be contacted.

  Further, according to the present embodiment, as will be described in detail later, it is possible to plan an operation of the robot with a calculation amount proportional to the number of grids included in the space in which the robot deforms, and use the result of the operation plan. Thus, it is possible to cause the robot to deform from an arbitrary shape to an arbitrary shape in an environment where an obstacle of an arbitrary shape exists in an execution time proportional to the square of the number of robots.

[Problem settings]
The task of performing the formation at the target position by moving the robot while maintaining the state in which each robot is in contact from the formation state at the start position in cooperation with a number of robots, Assume the use of a cube-type robot that can move by moving the faces that touch each other. As shown in FIG. 27, this is realized by the movement of a plurality of robots from a start position to a target position in a room partitioned by walls (however, walls are omitted in the figure).

  As for the robot, for example, as shown in FIG. 26, while maintaining the state in which another robot exists in one of six squares in the vertical and horizontal height directions of the robot (hereinafter also referred to as “vertical, horizontal and vertical directions”). 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 corresponding to the size of one robot. In addition, by measuring the relative positions of adjacent robots that share one surface, the position of each robot in the entire group of robots can be easily known. 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. Further, it is possible to move a plurality of robots at the same time as if a plurality of robots were connected.

  It is assumed that the robot can know whether another robot is present at the adjacent position, whether there is an obstacle, and whether the robot is on the target position.

  The robots that perform the mission are p units (p ≧ 192 = 24 × 8), and each robot can move in the X-Y-Z-axis direction in the three-dimensional space while sharing one or more surfaces with adjacent robots. Each cube in FIG. 26 indicates 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 where the robot can exist is also referred to as a mass or a lattice. In FIG. 27, a square filled with gray indicates a position where the robot is present, and a white square surrounded by a solid line indicates a position where an obstacle is present. The position where the robot of FIG. 27A exists indicates a set of start positions of the robot, and the position where the robot of FIG. 27B exists 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. As described above, each start position and each target position are adjacent to other start positions and target positions in at least one of the vertical and horizontal height directions, and the formations at the start position and the target position of the robot are each in a lump. Any shape.

[Robot coordinate settings]
The initial position of each robot i (i is the robot number i = 0,1,2,3 ,,, p-1) is (Xr0 [i], Yr0 [i], Zr0 [i]) When the position is (Xre [i], Yre [i], Zre [i]), this problem can be defined as finding an action plan for the robot placed at the initial position to move to the target position. . Let G be a set of target positions (Xre [i], Yre [i], Zre [i]).

[Definition of mission space]
When i is a robot number, each state (robot position and action) of the robot i is expressed by discrete values. When a room is represented in a three-dimensional space composed of an orthogonal coordinate system of X, Y, and Z, each position is represented by a discrete representation of the X, Y, and Z axes. 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.

[Definition of robot motion]
The action subject is each robot arranged 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 direction of X axis in 3D space
2: Move one grid in the positive Y-axis direction in 3D space
3: Move one grid in the negative X-axis direction in 3D space
4: Move one grid in the negative Y-axis direction in 3D space
5: Move one grid in the positive Z-axis direction in 3D space
6: Suppose that one grid moves in the negative Z-axis direction in the three-dimensional space.

[Problems in search calculation]
The state space in such a task environment has a state of the number of dimensions of the number of robots × 3, and the number of actions that can be selected exists by the robot power (= 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 the search calculation becomes enormous. . As the number of robots further increases, the number of states will increase by 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.

[Introduction of two action plans]
Therefore, two operation plans are introduced as in the case of the first embodiment. The search calculation required in this embodiment is roughly divided into two. Here, as a preparation for this, a robot forming a certain column Ga considers Gb as the shape of the next column to be formed. Between the formations Ga and Gb, there are robots that exist in the formation Ga and that do not exist in the formation Gb, and robots that exist in the formation Gb and do not exist in the formation Ga. The former is a tail robot and the latter is a head robot. In the present embodiment, the formation Ga and the formation Gb are defined so that the robot at the head robot position is the first robot in the movement of the robot group, and the tail robot is the last robot in the movement.

  Based on this definition, the first search calculation shows that the group of robots that form the formation Ga is selected as the next formation Gb in order to move to the target position while avoiding obstacles. This is an operation plan calculation (operation plan for determining a movement destination platoon) for determining whether it is acceptable (FIG. 28). This search calculation is actually a calculation for determining which robot of the formation Ga is selected as the robot moving to the head robot position and the tail robot in the formation Ga.

  The second search calculation is an action plan calculation (an action plan for each robot action) that determines the action of each robot when transforming from formation Ga to formation Gb while maintaining the positional relationship where the robots are in contact with each other. ). This is in effect to drive the robot from the position of the tail robot to the position of the head robot in the formation Gb, with respect to the head robot and tail robot that have already been determined by the movement plan for the movement target row determination. Search calculation.

  In this embodiment, these search calculations are performed by setting a single entrance position in the set G of target positions and calculating the Manhattan distance in the entire robot structure of each robot position from the entrance position.

[Void control]
In order to reduce the above two search calculation loads, the concept of void control is also introduced in this embodiment. First, the term “void” as used herein refers to a gap that can be restored to the original position after a robot has moved to another position. In such a group robot formation problem, the amount of search calculation explodes because it focuses on the movements of multiple robots. The planning problem can be considered as a single void motion plan, which is suitable for reducing the search calculation load.

  First, consider the behavior of the head robot that acts as the head of the movement of the robot group in the movement plan for determining the movement destination group. In the present embodiment, one entrance position Pe is provided in the set G of target positions, and the head robot cannot enter G from other positions. Also, all robots that have entered G once cannot go outside G again. Under this condition, the robot routing problem until the head robot outside G reaches the entrance position Pe can be obtained by solving the search problem for guiding one robot to the entrance position Pe. Can be used for head robot selection and guidance. As for the operation of the head robot in the set G of target positions, attention is paid to the movement of the void and the same is performed for the guidance of the void. That is, the desired behavior of the head robot in the target position set G is that the head robot appropriately moves away from the entrance position Pe and is scattered in each place in the target position set G. If this robot is seen as the movement of a void, each time the robot enters the target position set G from the entrance position Pe, the void is accompanied by a set of target positions from the entrance position Pe. Go out of G. At this time, it is an ideal operation that all the voids in the set G of target positions move toward the single entrance position Pe. In other words, in order to guide the head robot in the target position set G so as to be properly scattered in the target position set G, the path through which each void located in the target position set G reaches the entrance position Pe. It is only necessary to search for and calculate the void motion obtained by moving the head robot. With this concept, all the robots need only perform an operation plan for one point of movement toward the entrance position Pe, so the calculation load is dramatically reduced.

  Next, consider that the robot group that maintains the formation Ga transforms into the formation Gb. At this time, the movement of the robot group from the formation Ga to the formation Gb can be regarded as a process in which one void at the position of the head robot moves to the position of the tail robot (FIGS. 28 and 28). 29). Such a motion of the void can be calculated by an operation plan of one void with the head robot position as the start position and the tail robot position as the goal position, and the calculation load is small. As a constraint condition for the movement of the void to be considered in this calculation, it is only necessary to provide a restriction that the robot follows the position where the robot exists when the void moves.

[Introduction of 8 mass robot units]
Furthermore, in this embodiment, as shown in FIG. 30, the robot adjacent to the eight-field shape is defined as one unit (robot unit), and the robot moves while maintaining this field-shaped robot unit. Suppose that 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. Move. This group of robot units is controlled so that each robot unit shares one surface and moves while touching.

  The reason why such eight robots are moved as one unit is that, as long as movement is performed in such a state, each robot unit is This is because it is not necessary to destroy the positional relationship of contacting each other on one surface. In other words, this is because the calculation load for considering the connection between the robots is reduced in each robot motion operation plan in which it is necessary to consider maintaining the formation of the formation. If there is no more than one void in each robot unit, there may be voids in all robot units, so multiple robots can exist in parallel in the robot group at the same time. It is also possible to speed up the formation deformation operation.

  The movement plan for determining the movement destination corps described above is performed for a movement of a group of eight robots. The head robot and tail robot described above are in units of head robot and tail robot each composed of eight robots. Each robot operation plan guides the robot to the positions of the eight robots included in the head robot unit, and searches for and calculates the operation for driving away the eight robots from the robots included in the position of the tail robot unit. .

Here, it is assumed that the robot unit formed by eight robots is one unit of mass (in the present embodiment, this unit is hereinafter also referred to as “mass unit” or “position unit”), and one mass unit is in one state. As a state space. 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 x Xr_unit [j]
Yri1 = 2 x Yr_unit [j]
Zri1 = 2 x Zr_unit [j]
Xri2 = 2 x Xr_unit [j] + 1
Yri2 = 2 x Yr_unit [j]
Zri2 = 2 x Zr_unit [j]
Xri3 = 2 x Xr_unit [j]
Yri3 = 2 x Yr_unit [j] + 1
Zri3 = 2 x Zr_unit [j]
Xri4 = 2 x Xr_unit [j] + 1
Yri4 = 2 x Yr_unit [j] + 1
Zri4 = 2 x Zr_unit [j]
Xri5 = 2 x Xr_unit [j]
Yri5 = 2 x Yr_unit [j]
Zri5 = 2 x Zr_unit [j] + 1
Xri6 = 2 x Xr_unit [j] + 1
Yri6 = 2 x Yr_unit [j]
Zri6 = 2 x Zr_unit [j] + 1
Xri7 = 2 x Xr_unit [j]
Yri7 = 2 x Yr_unit [j] + 1
Zri7 = 2 x Zr_unit [j] + 1
Xri8 = 2 x Xr_unit [j] + 1
Yri8 = 2 x Yr_unit [j] + 1
Zri8 = 2 x Zr_unit [j] + 1
It is.

  The set of start positions for head robot unit determination is SU, and the set of target positions is GU. The start position set SU and the target position set GU are composed of cells in which eight robot positions become one unit, similar to a robot unit. One entrance position unit PeU is provided in the GU, and each robot enters the GU via a position in the PeU. It should be noted that the total number of robot units used in the movement plan for the movement destination platoon determination must be the same as the number of robot units in the start position set SU and the target position set GU. Therefore, the total number p of robots is a multiple of 8, and in the set SU of start positions and the set GU of target positions, all robot units are filled with 8 robots, and no fractional robots are generated. The set of target positions GU and the set of start positions SU each have an arbitrary shape made up of R position units.

[Movement plan for moving to move to]
In this embodiment, the Manhattan distance from the entrance position unit PeU of each position unit in the mission space used for two operation plans is calculated in advance before the robot starts the operation. For this purpose, first, for each position unit (X, Y, Z) in the mission space, the Manhattan distance δ [X] [Y] [Z] from the entrance position unit PeU to each position unit is calculated as follows: Ask for. In the following, for simplicity of explanation, the “position unit” is also simply referred to as “position”, and the “entrance position unit PeU” is also simply referred to as “entrance position Pe”.

[Calculation of Manhattan distance δ]
(1) Next [a] [X] [Y] [Z] is prepared at each position (X, Y, Z), and there is an obstacle in the direction of the adjacent action a or the position (X, Y , Z) is a position in the target position set GU other than the entrance position Pe, the position of the adjacent action a is outside the target position set GU, or the position (X, Y, Z) Is outside the target position set GU, and the position in the direction of the adjacent action a is a position in the target position set GU other than the entrance position Pe, next [a] [X] [Y] [ Z] ← 0, otherwise, next [a] [X] [Y] [Z] ← 1. That is, next [a] [X] [Y] [Z] = 0 indicates that the action a cannot be executed at the position (X, Y, Z). Means that the action a can be executed at the position (X, Y, Z).
(2) The Manhattan distance δ [X] [Y] [Z] at each position (X, Y, Z) in the state space is initialized to a value s_max larger than the number of lattices in the state space.
(3) The Manhattan distance δ at the entrance position Pe is initialized to zero.
(4) For all actions a at each position (X, Y, Z) other than the entrance position Pe, the position is determined by action a when the value of next [a] [X] [Y] [Z] is not 0. Check the Manhattan distance δ [X '] [Y'] [Z '] at the previous position (X', Y ', Z') moved from (X, Y, Z), and add 1 to the minimum value. If the obtained value is smaller than the current δ [X] [Y] [Z], the value is substituted into δ [X] [Y] [Z].
(5) Repeat (4) until there is no more update of the δ [X] [Y] [Z] value in the processing of (4) above.

  The Manhattan distance δ [X] [Y] [Z] calculated by the above processing is used, and then a path P connecting the start position set SU and the target position set GU is determined. The path P is determined by the following process. The position forming the path P is assumed to be p [ip] (ip = 0, 1, 2, 3 ...).

[Determine path P]
(1) A position having the smallest Manhattan distance δ [X] [Y] [Z] value in the start position set SU is defined as Ps.
(2) A position outside the start position set SU adjacent to the position Ps and having a Manhattan distance δ that is smaller by one than the Manhattan distance δ at the position Ps is defined as a starting point p [0] of the path P.
(3) Set ip ← 0.
(4) Among positions adjacent to the position p [ip], a position having a Manhattan distance δ smaller by 1 than the Manhattan distance δ at the position p [ip] is defined as p [ip + 1]. If p [ip + 1] does not coincide with the entry position Pe, ip is incremented and (4) is repeated. If they match, go to (5).
(5) Reset the Manhattan distance δ of all positions not included in either the target position set GU or the path P to s_max.
(6) Action a when the value of next [a] [X] [Y] [Z] is not 0 for all actions a at all positions (X, Y, Z) in the start position set SU The Manhattan distance δ [X '] [Y'] [Z '] at the previous position (X', Y ', Z') moved from the position (X, Y, Z) is checked, and the minimum value is 1 When the value obtained by adding is smaller than the current δ [X] [Y] [Z], the value is substituted into δ [X] [Y] [Z].
(7) Repeat (6) until there is no more update of the δ [X] [Y] [Z] value in the processing of (6) above.
(8) The sign of the Manhattan distance δ of all points in the set GU of target positions is made negative. As a result of this processing, the Manhattan distance δ decreases as the distance from the entrance position Pe increases within the set GU of target positions.

  The Manhattan distance δ calculated by the above processing is a value of the Manhattan distance considering the movement of the robot only in SU + P + GU. Using the Manhattan distance δ, a group of robot units that form a certain column Ga determines the head robot of the column Gb to be moved next as follows. This processing is referred to as head determination processing Head_Robot_Decision. . The Manhattan distance δ calculated by the above processing corresponds to the value function of the first embodiment, and represents the appropriateness when the robot unit takes each action in the current position unit of the robot unit. Specifically, the robot unit is controlled so as to move in a direction in which the Manhattan distance δ decreases. Therefore, a value function corresponding to the value function of the first embodiment (one value function representing appropriateness when the robot unit takes each action in the current position unit of the robot unit) is obtained from a certain position unit. It can be said that it is obtained using the Manhattan distance to the entrance position unit.

[Head_Robot_Decision]
(1) The position of each robot unit (Xr_unit [j], Yr_unit [j], Zr_unit [j]) is adjacent to the position (Xr_unit [j], Yr_unit [j], Zr_unit [j]) and the robot is 1 from the value of the Manhattan distance δ [Xr_unit [j]] [Yr_unit [j]] [Zr_unit [j]] among the positions that do not exist and belong to either the path P or the target position set GU A position having a small Manhattan distance δ is obtained, and the Manhattan distance δ at the position is set as δ_neighbor_max [Xr_unit [j]] [Yr_unit [j]] [Zr_unit [j]].
(2) Robot unit H with the maximum value of δ_neighbor_max [Xr_unit [j]] [Yr_unit [j]] [Zr_unit [j]] among all robot units (Note that the position of robot unit H is (Xrh, Yrh, Zrh)), the robot is adjacent to the robot unit H, the robot does not exist, and the Manhattan distance δ is the robot unit among the positions belonging to either the path P or the target position set GU. A position having a Manhattan distance δ that is one smaller than that of H is defined as the position of head robot unit D. The direction of action from the robot unit H toward the position of the head robot unit D is a_head.

  In the above processing, when the robot unit exists only outside the target position set GU, the group of robots approaches the entrance position Pe through the path P, or the robot unit exists within the target position set GU. When doing so, the head robot unit D is selected so that the robot can be preferentially filled from a position close to the entrance position Pe.

  Next, a method Tail_Robot_Decision for determining the tail robot unit position will be described.

[Tail_Robot_Decision]
(1) At each robot unit position (Xr_unit [j], Yr_unit [j], Zr_unit [j])
δ '[Xr_unit [j]] [Yr_unit [j]] [Zr_unit [j]]
= δ [Xr_unit [j]] [Yr_unit [j]] [Zr_unit [j]]-δ [Xrh] [Yrh] [Zrh]
Calculate
(2) In each robot unit position (Xr_unit [j], Yr_unit [j], Zr_unit [j]), all adjacent robot units N (note that the position of the robot unit N is (Xrn, Yrn, Zrn) ) For δ '[Xr_unit [j]] [Yr_unit [j]] [Zr_unit [j]] ≧ δ' [Xrn] [Yrn] [Zrn] and δ '[Xr_unit [j]] [Yr_unit Any one of the robot units satisfying [j]] [Zr_unit [j]] ≧ 3 is selected as the tail robot unit T. That is, the tail robot unit T is far from the robot unit H more than all the adjacent robot units N, and is more than 3 square units away from the robot unit H (Manhattan between the robot unit H and the tail robot unit T). The distance is more than 3 square units).

  In the above processing, the robot unit that does not lose the continuity of the formation Ga even if it is removed from the formation Ga is set as the tail robot unit.

The above processing is summarized and the movement plan determination operation plan process (Next_Formation_Decision) is performed as follows.
(1) The head determination process Head_Robot_Decision is performed.
(2) Perform tail robot decision processing Tail_robot_Decision.
(3) The tail robot unit T identified in the above (2) is deleted from the current formation Ga, and the head robot unit D is added to the formation Ga to form a formation Gb.

[Operation plan for determining each robot operation]
Since the head robot unit D and the tail robot unit T are determined in the movement plan for the movement target column determination, and the next column Gb is determined, the transformation from the current column Ga to the next column Gb is realized by the movement of each robot. Search calculation is performed in each robot motion determination motion plan.

  In this embodiment, the robot group moves while maintaining a robot unit of eight robots. Therefore, when considering the connection maintenance of each robot when performing void control, the tail robot As long as attention is paid to the movement of the void in the vicinity of the unit T and the head robot unit D, the number of voids may be within one in each robot unit.

  The operation of each robot motion determination motion plan will be described below. In the robot motion determination action plan, every time the robot unit is moved from the robot unit H to the head robot unit D, eight voids are generated. First, for each of the generated voids, the void is the robot unit H. To calculate the path to follow from T to the tail robot unit T.

  First, of the robots belonging to robot unit H, the four robots that are in contact with head robot unit D are robots i_move_11, i_move_21, i_move_31, i_move_41, and movement of robots i_move_11, i_move_21, i_move_31, i_move_41 and action a_head The robots in contact with the opposite direction of the direction are ordered as robots i_move_12, i_move_22, i_move_32, and i_move_42, respectively.

  When moving from robot unit H to head robot unit D, robot i_move_r1 (where r is one of 1, 2, 3, or 4) and robot i_move_r2 in robot unit H are paired and slide in the a_head direction. As a result, the robot moves. Therefore, the position of the void generated in the robot unit H is always one of the robots i_move_12, i_move_22, i_move_32, and i_move_42. Fully-filled robots that manage the serial number of the voids that have been generated since the robot started the formation process from the set SU at the start position to the set GU at the target position with iv (= 0, 1, 2, 3 ...) When the movement of the robot from the unit H to the head robot unit D is started, assuming that the number of voids generated so far is iv_prev, iv_prev is (multiple of 8-1). Let void [iv_prev + k] (k = 1, 2, 3, 4, 5, 6, 7, 8) be a void generated when moving from robot unit H to head robot unit D. Represent each void trajectory as (void_trj_x [iv_prev + k] [t], void_trj_y [iv_prev + k] [t], void_trj_z [iv_prev + k] [t]) (t = 0,1,2,3…) To do.

  The trajectory calculation process (Void_Trajectory_Decision) for each void is performed according to the following procedure.

[Void_Trajectory_Decision]
(1) The occurrence position of each void is as follows.
Generation location of void [iv_prev + 1], void [iv_prev + 2] → position of robot i_move_12
Position where void [iv_prev + 3] and void [iv_prev + 4] occur → Position of robot i_move_22
Position where void [iv_prev + 5] and void [iv_prev + 6] occur → Position of robot i_move_32
Position where void [iv_prev + 7] and void [iv_prev + 8] occur → Position of robot i_move_42
(2) The occurrence position of each void is defined as the end point void_end [iv_prev] of the trajectory of each void.
(3) The eight voids whose occurrence positions are set in (1) above should follow the path of the position unit to be followed from the position of robot unit H to the position of tail robot unit T (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]) (tu = 0,1,2,3 ...) and (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]) are determined by Void_Unit_Trajectory_Decision described later. The value of tu is set to 0 at the point on the path closer to T, and is set in the opposite direction to the movement of the void so as to increase as H approaches.
(4) (void_unit_trj_x [1], void_unit_trj_y [1], void_unit_trj_z [1]) is T ', and (void_unit_trj_x [2], void_unit_trj_y [2], void_unit_trj_z [2]) is T ". T' is a tail robot. A robot unit adjacent to the unit T, and T ″ is a robot unit adjacent to the robot unit T ′.
(5) The robots i_tail_0, i_tail_1, i_tail_2, and i_tail_3 are the four robots that are in the robot unit T ′ and are not in contact with the position in the tail robot unit T, and set the target position of each void as follows: .
Target position of void [iv_prev + 1], void [iv_prev + 2] → position of robot i_tail_0
Target position of void [iv_prev + 3], void [iv_prev + 4] → position of robot i_tail_1
Target position of void [iv_prev + 5], void [iv_prev + 6] → position of robot i_tail_2
Target position of void [iv_prev + 7], void [iv_prev + 8] → position of robot i_tail_3
(6) From the same position as the generation position of each void in the robot unit T "(the generation position of each void in the robot unit H when the robot unit H is translated to the position of the robot unit T") Trajectories (void_trj_x [iv_prev + k] [t], void_trj_y [iv_prev + k] [t], void_trj_z [iv_prev + k] [t]) to each void target position in T ′ are determined by Void_Local_Trajectroy_Decision described later. The value of t is set to 0 at the target position in the robot unit T ′, and is set in the opposite direction to the movement of the void so as to increase as it approaches each void generation position in the robot unit T ″.
(7) End point (t = ts) of the trajectory (void_trj_x [iv_prev + k] [t], void_trj_y [iv_prev + k] [t], void_trj_z [iv_prev + k] [t]) determined in (6) above And the trajectory from the robot unit H to the void generation position is set by the following process (8).
(8) It ← 2.
(9) If (void_unit_trj_x [2 + it / 2-1], void_unit_trj_y [2 + it / 2-1], void_unit_trj_z [2 + it / 2-1]) does not match the position of robot unit H , (Void_unit_trj_x [2+ (it) / 2-1], void_unit_trj_y [2+ (it) / 2-1], void_unit_trj_z [2+ (it) / 2-1]) to (void_unit_trj_x [2 + it / 2 ], void_unit_trj_y [2 + it / 2], void_unit_trj_z [2 + it / 2]), (void_trj_x [iv_prev + k] [ts + it-2], void_trj_y [iv_prev + k] [ts + it-2], void_trj_z [iv_prev + k] [ts + it-2]) to the position moved one step (void_trj_x [iv_prev + k] [ts + it-1], void_trj_y [iv_prev + k] [t + it-1], void_trj_z [iv_prev + k] [t + it-1]), and the position moved two steps is (void_trj_x [iv_prev + k] [ts + it], void_trj_y [iv_prev + k] [ts + it ], void_trj_z [iv_prev + k] [ts + it]) and increment it twice. Repeat (9) until (void_unit_trj_x [2 + it / 2-1], void_unit_trj_y [2 + it / 2-1], void_unit_trj_z [2 + it / 2-1]) matches the position of robot unit H. If (void_unit_trj_x [2 + it / 2-1], void_unit_trj_y [2 + it / 2-1], void_unit_trj_z [2 + it / 2-1]) matches the robot unit H position, Finish as score trj_num [iv_prev + k] ← ts + it-2.

[Void_Local_Trajectroy_Decision]
The processing of Void_Local_Trajectroy_Decision is as follows. First, before the robot starts operation, five robot units T "[kt] (kt = 1, 2, 3, 4 and 5) are in contact with each other, and the position of the tail robot unit in the robot unit T ′ for all positions in the robot unit T ′ and the position not in contact with the tail robot unit T in the robot unit T ′. Manhattan distance δlocal [vs] [al] (X, Y, Z) (vs = 0,1,2,3. Al = 1,2,3,4,5,6) from four positions not touching T Are all calculated. Here, the Manhattan distance of the robot is obtained instead of the robot unit. Here, al is an action in six directions from the position of the robot unit T to the position of the robot unit T ′, and vs is an index of four robots (that position) that do not touch the tail robot unit T in the robot unit T ′. It is.

(1) al = 1, T = (0,0,0), T '= (1,0,0), T "[1] = (1,1,0), T" [2] = (1 , -1,0), T "[3] = (2,0,0), T" [4] = (1,0,1), T "[5] = (1,0, -1)
(2) al = 2, T = (0,0,0), T '= (0,1,0), T "[1] = (1,1,0), T" [2] = (- 1,1,0), T "[3] = (0,2,0), T" [4] = (0,1,1), T "[5] = (0,1, -1)
(3) al = 3, T = (0,0,0), T '= (-1,0,0), T "[1] = (-1,1,0), T" [2] = (-1, -1,0), T "[3] = (-2,0,0), T" [4] = (-1,0,1), T "[5] = (-1, (0, -1)
(4) al = 4, T = (0,0,0), T '= (0, -1,0), T "[1] = (1, -1,0), T" [2] = (-1, -1,0), T "[3] = (0, -2,0), T" [4] = (0, -1,1), T "[5] = (0,- 1, -1)
(5) al = 5, T = (0,0,0), T '= (0,0,1), T "[1] = (0,1,1), T" [2] = (0 , -1,1), T "[3] = (0,0,2), T" [4] = (1,0,1), T "[5] = (-1,0,1)
(6) al = 6, T = (0,0,0), T '= (0,0, -1), T "[1] = (0,1, -1), T" [2] = (0, -1, -1), T "[3] = (0,0, -2), T" [4] = (1,0, -1), T "[5] = (-1, (0, -1)
Hereinafter, the calculation method of δlocal [vs] [al] (X, Y, Z) is shown.

[Calculate_delta_local]
(1) next_local [al] [a] [X] [Y] [Z at the position (X, Y, Z) of the robot unit T 'that does not touch the tail robot unit T and all the positions (X, Y, Z) of the robot unit T " ], And if there is a position not in contact with the tail robot unit T in the robot unit T ′ adjacent to the position (X, Y, Z) or a position in the robot unit T ″, next_local [al] [a ] [X] [Y] [Z] ← 1, otherwise, next_local [al] [a] [X] [Y] [Z] ← 0.
(2) δlocal [vs] [of each position (X, Y, Z) for all positions (X, Y, Z) of robot unit T 'and all positions (X, Y, Z) of robot unit T "within robot unit T' al] (X, Y, Z) values are initialized to a value s_max greater than 44 (number of 4 positions in T ′, 8 × 5 positions in T ″).
(3) For each vs and al, the following positions are set as the target position target_local [vs] [al], and the Manhattan distance δlocal [vs] [al] (24 ways) at the target position is initialized to 0.
target_local [0] [1] = (3,0,0)
target_local [1] [1] = (3,0,1)
target_local [2] [1] = (3,1,0)
target_local [3] [1] = (3,1,1)
target_local [0] [2] = (0,3,0)
target_local [1] [2] = (0,3,1)
target_local [2] [2] = (1,3,0)
target_local [3] [2] = (1,3,1)
target_local [0] [3] = (-2,0,0)
target_local [1] [3] = (-2,0,1)
target_local [2] [3] = (-2,1,0)
target_local [3] [3] = (-2,1,1)
target_local [0] [4] = (0, -2,0)
target_local [1] [4] = (0, -2,1)
target_local [2] [4] = (1, -2,0)
target_local [3] [4] = (1, -2,1)
target_local [0] [5] = (0,0,3)
target_local [1] [5] = (0,1,3)
target_local [2] [5] = (1,0,3)
target_local [3] [5] = (1,1,3)
target_local [0] [6] = (0,0, -2)
target_local [1] [6] = (0,1, -2)
target_local [2] [6] = (1,0, -2)
target_local [3] [6] = (1,1, -2)
(4) The value of next_local [al] [a] [X] [Y] [Z] is 0 for all actions a at each position (X, Y, Z) except for the target position target_local [vs] [al] If not, the value of δlocal [vs] [al] (X, Y, Z) is examined, and the value obtained by adding 1 to the minimum value is the current δlocal [vs] [al] (X, Y, Z) If it is smaller than), the value is assigned to δlocal [vs] [al] (X, Y, Z). Repeat (4) until the δlocal [vs] [al] (X, Y, Z) value is no longer updated.

  Processing of Void_Local_Trajectory_Decision is as follows.

[Void_Local_Trajectroy_Decision]
(1) With the position of robot unit T 'as (XT', YT ', ZT') and the position of robot unit T "as (XT", YT ", ZT"), the action in the direction toward T-> T ' Is the al value. . The location of i_tail_0 is target_local [0] [al] (vs = 0), the location of i_tail_1 is target_local [1] [al] (vs = 1), and the location of i_tail_2 is target_local [2] [al] ( vs = 2), and the position of i_tail_3 is assumed to be target_local [3] [al] (vs = 3).
(2) The occurrence position of each void void [iv_prev + k] is (xv [iv_prev + k], yv [iv_prev + k], zv [iv_prev + k]), and the position vt "in the robot unit T" is Calculate as follows.

The value of the movement vector from the robot unit T 'to the robot unit T "is (Xdt, Ydt, Zdt) = (XT", YT ", ZT")-(XT', YT ', ZT')
If al = 1,
vt "← (xv [iv_prev + k] -xrh * 2 + 2 + Xdt * 2, yv [iv_prev + k] -yrh * 2 + Ydt * 2, zv [iv_prev + k] -zrh * 2 + Zdt * 2 )
If al = 2,
vt "← (xv [iv_prev + k] -xrh * 2 + Xdt * 2, yv [iv_prev + k] -yrh * 2 + 2 + Ydt * 2, zv [iv_prev + k] -zrh * 2 + Zdt * 2 )
If al = 3,
vt "← (xv [iv_prev + k] -xrh * 2-2 + Xdt * 2, yv [iv_prev + k] -yrh * 2 + Ydt * 2, zv [iv_prev + k] -zrh * 2 + Zdt * 2 )
If al = 4,
vt "← (xv [iv_prev + k] -xrh * 2 + Xdt * 2, yv [iv_prev + k] -yrh * 2-2 + Ydt * 2, zv [iv_prev + k] -zrh * 2 + Zdt * 2 )
If al = 5,
vt "← (xv [iv_prev + k] -xrh * 2 + Xdt * 2, yv [iv_prev + k] -yrh * 2 + Ydt * 2, zv [iv_prev + k] -zrh * 2 + 2 + Zdt * 2 )
If al = 6,
vt "← (xv [iv_prev + k] -xrh * 2 + Xdt * 2, yv [iv_prev + k] -yrh * 2 + Ydt * 2, zv [iv_prev + k] -zrh * 2-2 + Zdt * 2 )
(3) tl ← 0, and the position of vt "is (void_local_x [iv_prev + k] [tl], void_local_y [iv_prev + k] [tl], void_local_z [iv_prev + k] [tl]).
(4) When the position (void_local_x [iv_prev + k] [tl], void_local_y [iv_prev + k] [tl], void_local_z [iv_prev + k] [tl]) does not match target_local [vs] [al]
Adjacent to the location (void_local_x [iv_prev + k] [tl], void_local_y [iv_prev + k] [tl], void_local_z [iv_prev + k] [tl]) and the value of δlocal [vs] [al] is (void_local_x [iv_prev + k] [tl], void_local_y [iv_prev + k] [tl], void_local_z [iv_prev + k] [tl]) position less than δlocal [vs] [al] value (void_local_x [iv_prev + k] [tl + 1], void_local_y [iv_prev + k] [tl + 1], void_local_z [iv_prev + k] [tl + 1]) and increment tl. (4) is repeated until (void_local_x [iv_prev + k] [tl], void_local_y [iv_prev + k] [tl], void_local_z [iv_prev + k] [tl]) matches target_local [vs] [al]. Go to (5) when the position (void_local_x [iv_prev + k] [tl], void_local_y [iv_prev + k] [tl], void_local_z [iv_prev + k] [tl]) matches target_local [vs] [al] Transition.
(5) (void_trj_x [iv_prev + k] [t], void_trj_y [iv_prev + k] [t], void_trj_z [iv_prev + k] [t]) ← (void_local_x [iv_prev + k] [tl-t], void_local_y [ iv_prev + k] [tl-t], void_local_z [iv_prev + k] [tl-t]), and ts ← tl.

  The processing of Void_Unit_Trajectory_Decision is as follows.

[Void_Unit_Trajectory_Decision]
(1) The position of the tail robot unit T is (void_unit_trj_x [0], void_unit_trj_y [0], void_unit_trj_z [0]). It is assumed that tu ← 1 and the position of an adjacent robot unit having a Manhattan distance δ smaller than the tail robot unit T is (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]).
(2) If (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]) is not robot unit H even at the entrance position Pe, increment tu and position (void_unit_trj_x [tu-1], void_unit_trj_y [tu -1], void_unit_trj_z [tu-1]), the position of an adjacent robot unit having a smaller Manhattan distance δ than the robot unit is (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]). Repeat (2) until (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]) reaches the entrance position Pe or the robot unit H position.

  If (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]) is the entrance position Pe (not H), the process proceeds to (3).

If (void_unit_trj_x [tu], void_unit_trj_y [tu], void_unit_trj_z [tu]) is the position of the robot unit H, Void_Unit_Trajectory_Decision is terminated.
(3) The position of the robot unit H is (void_unit_trj_rev_x [0], void_unit_trj_rev_y [0], void_unit_trj_rev_z [0]). It is assumed that tr ← 1, and the position of an adjacent robot unit having a Manhattan distance δ larger than the robot unit H is (void_unit_trj_rev_x [tr], void_unit_trj_rev_y [tr], void_unit_trj_rev_z [tr]).
(4) If (void_unit_trj_rev_x [tr], void_unit_trj_rev_y [tr], void_unit_trj_rev_z [tr]) is not the entrance position Pe, tr is incremented and the position (void_unit_trj_rev_x [tr-1], void_unit_trj_rev_y [tr-1], Let (void_unit_trj_rev_x [tr], void_unit_trj_rev_y [tr], void_unit_trj_rev_z [tr]) be the position of an adjacent robot unit having a Manhattan distance δ larger than the robot unit in void_unit_trj_rev_z [tr-1]). Repeat (4) until (void_unit_trj_rev_x [tr], void_unit_trj_rev_y [tr], void_unit_trj_rev_z [tr]) reaches the entrance position Pe.

If (void_unit_trj_rev_x [tr], void_unit_trj_rev_y [tr], void_unit_trj_rev_z [tr]) is the entrance position Pe, the process proceeds to (5).
(5) As it = 1 ,,, tr, (void_unit_trj_x [tu + it], void_unit_trj_y [tu + it], void_unit_trj_z [tu + it]) ← (void_unit_trj_rev_x [tr-it], void_unit_trj_rev_y [tr-it], void_unit_trj_rev_z [tr-it]).

[Void movement control]
Hereinafter, a control method for moving the void from the position of the robot unit H to the position of the tail robot unit T using the above-described operation plans for determining the robot movement will be described. As shown in FIG. 31, the robot is positioned so that there is no blank between the robot in the position in contact with the head robot unit D in the robot unit H and the robot position in the position in contact with the tail robot unit T in the robot unit T ′. The connection of the entire robot group is maintained by generating voids in unit H and expelling voids in tail robot unit T. In the selection algorithm of the tail robot unit T, the δ ′ of the position of the tail robot unit T (Manhattan distance between the robot unit H and the tail robot unit T) is 3 so that the robot unit H and the robot unit T ′ do not directly touch each other. The above conditions are set. With this control method, control is performed so that the number of voids is within one in each robot unit.

  The following is repeated until the target position set GU is satisfied.

[Void_Control]
(1) Execute Void_Trajectory_Decision. Set trj_cnt [iv_prev + 1] ,, trj_cnt [iv_prev + 8], to -1. Increment the value of iv_prev 8 times.
(2) Repeat the following until void [iv_prev] comes out of robot unit H.

  The following processing is performed from the one with the largest occurrence number (iv = iv_prev).

  (2-i) When trj_cnt [iv] =-10 → Do nothing for void [iv].

(2-ii) When trj_cnt [iv] <trj_num [iv] && trj_cnt [iv]> = 0 →
i = From trj_cnt [iv] to trj_num [iv] do the following:
There is another void in the robot unit Nv containing the position nv (void_trj_x [trj_num [iv] -i-1], void_trj_y [trj_num [iv] -i-1], void_trj_z [trj_num [iv] -i-1]) Confirm that all voids with numbers smaller than themselves belong to the robot unit whose Manhattan distance δ is larger than the robot unit Nv. If confirmed, the robot at the position of nv is moved to the position (void_trj_x [trj_num [iv] -i], void_trj_y [trj_num [iv] -i], void_trj_z [trj_num [iv] -i]).

    It increments trj_cnt [iv] and repeats the process until it cannot be confirmed. If it cannot be confirmed, nothing is done and the loop ends.

(2-iii) When trj_cnt [iv] = trj_num [iv] →
All robots that are adjacent in the direction opposite to the direction of al from the current position of void [iv] and that are traced are moved one step in the direction of al, and trj_cnt [iv] ← −10.

(2-iv) When trj_cnt [iv] =-1 →
When robot unit H is filled with 8 robots, the robot in the void [iv] generation position, the robot adjacent to the robot in the direction of action a_head, and further to the robot in the direction of a_head If there are any robots, move them all together and move them one step in the direction of a_head. Set trj_cnt [iv] ← 0. If you are not satisfied, do nothing.

  The formation of a robot row by the above method can be applied to a robot group of a start position set SU and a target position set GU having an arbitrary shape composed of 24 or more robot units.

<Behavior Control System 200 According to Second Embodiment>
The behavior control system 200 according to the second embodiment summarizes the overall operation configured by the processes described above.
(1) Calculate the Manhattan distance δ (Manhattan distance from each position unit to the entrance position unit PeU) used for the movement plan for the movement destination platoon determination. Calculate_delta_local is used to calculate the Manhattan distance δlocal used for robot motion planning near the tail robot unit.
(2) Repeat (3) and (4) below until all GUs are filled with robots.
(3) Execute the movement plan process Next_Formation_Decision for determining the movement target platoon.
(4) The robot motion determination motion planning process is executed.

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

  FIG. 32 is a functional block diagram of the behavior control system 200 according to the first embodiment, and FIG. 33 shows an example of the processing flow. As shown in FIG. 32, the behavior control system 200 includes an operation planning unit 210, a behavior selection unit 220, an adjacent state determination unit 124, a position update unit 123, a position determination unit 126, a storage unit 240, and communication. Part 150 and input part 160. The action selection part 220 includes a movement plan determination action planning part 221 and each control object action action planning part 222. The operation plan unit 210, the action selection unit 220, and the storage unit 240, which are different from the first embodiment, will be mainly described. About the other part, the process similar to 1st embodiment is performed. However, the communication unit 150 and the adjacent state determination unit 124 perform communication in the up / down / left / right front / rear direction (hereinafter also referred to as “six directions”) in the three-dimensional space instead of the up / down / left / right direction on the two-dimensional plane. To determine the state.

  In this embodiment, the behavior control system 200 controls the behavior of p robots (p is an integer of 192 or more and a multiple of 8), and one robot among the p robots. Implemented above.

<Operation Planning Unit 210>
The motion planning unit 210 enters the entrance from each position of the start position set SU, the target position set GU, and the path P by the method described in [Calculation of Manhattan distance δ] and [Determination of path P]. The Manhattan distance δ to the position Pe is calculated in advance before the robot's mission action starts (S210) and stored in the storage unit 140. However, the sign of the Manhattan distance δ from each position of the set of target positions to the entrance position Pe is negative. Further, the Manhattan distance δ of all positions not included in any of the start position set SU, the target position set GU, and the path P is stored in the storage unit 140 as s_max (a value larger than the number of grids in the state space). . Similarly, Calculate_delta_local is executed before the robot mission action is started, and the Manhattan distance δlocal used for the robot motion plan near the tail robot unit is calculated. If the Manhattan distance δ is calculated by a separate device and stored in the storage unit 140 in advance before starting the robot mission behavior, the behavior control system 100 may not include the motion planning unit 210.

<Storage unit 240>
It is assumed that the storage unit 240 stores a Manhattan distance δ from each position s to the entrance position Pe and a robot operation planning Manhattan distance δlocal near the tail robot unit. The range that s can take is all the coordinates where the robot unit in the region in the target three-dimensional space can exist.

<Action selection unit 220>
The action selection unit 220 extracts the Manhattan distances δ and δlocal from the storage unit 240.

  The action selection unit 220 controls the p robots by the method described in the above method (s220).

  The movement plan determining action planning unit 221 of the action selecting unit 220 uses the Manhattan distance δ to perform the moving plan determining action planning process Next_Formation_Decision (s221), and p robots arranged in the set of starting positions. When moving the head to the set of target positions, the head row robot unit determines the row Gb for the row Ga at a certain time using the Manhattan distance δ in each position unit so that the head robot unit acts as the head of the movement. Outputs the position of robot unit and tail robot unit.

  Further, the motion planning unit 222 for each controlled object motion of the behavior selection unit 220 receives the position of the head robot unit and the tail robot unit, and performs a motion plan for each robot motion using the Manhattan distance δlocal (s222-1). ) A control signal is sent to each robot to control the operation of each robot so that eight robots are positioned at the position of the head robot unit. Each robot behaves according to the control signal.

  Each robot behaves according to the control signal.

  In addition, the process which fills the head robot unit determined by one movement plan decision operation plan process Next_Formation_Decision by one action control is performed.

  In the head determination process Head_Robot_Decision that is performed in the movement plan process Next_Formation_Decision for determining the movement target platoon, the position of each robot unit and the position of the obstacle are required, but the position of each robot unit can be acquired as described above. . As for the position of the obstacle, the position of the obstacle used when calculating the Manhattan distance δ may be used, or the one obtained using the determination result determined by the adjacent state determination unit 124 is used. May be.

  FIG. 34 shows an example of the transition state of the robot group that is controlled by this embodiment and is transformed from the set of start positions in FIG. 27A to the set of target positions in FIG. 27B.

<Effect>
With such a configuration, the same effect as that of the first embodiment can be obtained. In addition, the control object can be controlled not only on the two-dimensional plane but also on the three-dimensional space.

<Modification>
In this embodiment, each lattice (mass) is a cube, but may have other shapes. The lattice is continuously arranged in the left-right direction, the up-down direction, and the front-back direction. Each lattice is adjacent to the other two lattices in the left-right direction, is adjacent to the other two lattices in the vertical direction, and is adjacent to the other two lattices in the front-rear direction. In other words, each grid is adjacent to other grids only in the same direction that the robot can move. Each lattice may have any shape as long as this condition is satisfied. Further, the term “orthogonal” does not necessarily mean strictly “perpendicularly”. 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, and a direction that is not parallel to the plane formed by the up-down direction and the left-right direction may be the front-back direction.

  In other words, the control object is in the first direction (for example, the right direction), the second direction (for example, the upper direction) that is not parallel to the first direction, and the first direction in the three-dimensional space. A third direction (for example, the left direction) opposite to the second direction, a fourth direction (for example, the downward direction) opposite to the second direction, a direction not parallel to the plane formed by the first direction and the second direction. Can be moved in the fifth direction (for example, the forward direction) and the sixth direction, which is the opposite direction to the fifth direction, and from the current region (lattice, square) to the current region by one action control. On the other hand, it is controlled to move to any of the adjacent areas 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, the position adjacent in the first direction is the first position, the position adjacent in the second direction is the second position, the position adjacent in the third direction is the third position, 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, the example in which the behavior control system 100 is mounted on one of the p robots has been shown, but behavior control may be performed on a control target on a computer. In that case, unless a trouble occurs intentionally, the controlled object moves as controlled, so the assumed position (Xr '[i], Yr' [i]) and the post-movement position (Xr "[i], Yr "[i]) matches. In such a state, an ideal action plan for each control object i may be performed. The actual robot is made to execute the action plan until the mission obtained as a result is completed. The real robot includes a communication unit 150 and an adjacent state determination unit 124. After each action is completed, the adjacent state is determined, the post-action position is obtained using the determination result, and the post-action position (Xr "[i] , Yr "[i]) and the assumed position (Xr '[i], Yr' [i]) are determined to match. If they do not match, it is considered that the robot controlled to move could not move as controlled due to some trouble. Subsequent processing may be the same as in the first embodiment, or other processing may be performed. With such a configuration, it is possible to detect at least that movement was not possible as controlled.

  In this embodiment, one position determination is performed for one action control. However, when a plurality of robots are moved in one action control, each robot is moved each time it is moved. It is good also as a structure which performs determination.

  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 p of robots is a multiple of 24 or more of the number M × N × Q of robots included in the robot unit. That is, p = M × N × Q × R, and R is any integer of 24 or more. Even when moving in such a state, as in the case of a 2 × 2 × 2 robot unit, even if any robot in the group of robots is missing, each robot It is not necessary to break the positional relationship that touches the sides. When the number of M × N × Q is increased, the number of robot units decreases, and the number of patterns that can be acted on decreases, so the amount of calculation of the Manhattan distance δ decreases. However, if even one obstacle is included in a square unit with M x N x Q squares as one unit, it will be treated as being unable to move to that square unit, so M x N x Q Increasing the number of vehicles increases the range in which movement is not possible and the range in which action can be reduced. In the first place, since it is only necessary to check the Manhattan distance from each position to the entrance position Pe in the operation plan, the amount of calculation is sufficiently reduced as compared with the prior art. For this reason, in order to keep a large range in which the robot can act, it is desirable to use 2 × 2 × 2 robots as a robot unit.

<Other variations>
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 embodiments and modifications may be realized by a computer. In that case, the processing contents of the functions that each device should have are 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 contents can be recorded on a computer-readable recording medium. As the computer-readable recording medium, for example, any recording medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory may be used.

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

  A computer that executes such a program first stores, for example, a program recorded on a portable recording medium or a program transferred from a server computer in its 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. Also, the program is not transferred from the server computer to the computer, and the above-described processing is executed by a so-called ASP (Application Service Provider) type service that realizes the processing function only by the execution instruction and result acquisition. It is good. Note that the program includes information provided for processing by the electronic computer and equivalent to the program (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 these processing contents may be realized by hardware.

Claims (10)

M and N are each an integer greater than or equal to 2, p is an integer greater than or equal to M × N, and p control objects arranged in a set of start positions include target positions including a predetermined entrance position A behavior control system for performing behavior control to move to a set of
The direction not parallel to the first direction is the second direction, the opposite direction to the first direction is the third direction, the opposite direction to the second direction is the fourth direction, and each start position and each The target positions are adjacent to other start positions and target positions in at least one of the first direction to the fourth direction, respectively, and the set of the target positions and the set of the start positions each have an arbitrary shape in a lump. And
The control object includes a first position adjacent in the first direction on the two-dimensional plane of the control object, a second position adjacent in the second direction, a third position adjacent in the third direction, and a fourth position. It is assumed that the fourth position is adjacent in the direction and is controlled to move to any one of the first to fourth positions on the two-dimensional plane.
The p control objects constitute one control object unit for each M × N units, and the M × N control objects constituting one control object unit each have two or more directions. Adjacent to other control objects constituting the control object unit,
When a set of target position units consisting of position units consisting of N × N positions is set from the set of target positions, and the control object unit takes each action a at the current position s of the control object unit It is controlled based on one value function that represents the appropriateness of the image, and is stationary or moved to a position unit composed of N × N positions in any of the first to fourth directions on the two-dimensional plane. And shall be controlled as
A storage unit for storing the value function;
If there is no control object in the set of all target position units, Ga is the formation that consists of multiple control object units, Gb is the other formation that consists of multiple control object units, and exists in formation Gb. A control target unit that does not exist in the formation Ga is a head control target unit, and when moving the p control targets arranged in the start position set to the target position set, the head control target The movement plan determination operation planning unit for determining the column Gb for the column Ga at a certain time using the value function so that the object unit serves as the head of movement,
Each control object that controls the operation of each control object so that M × N control objects are located at the position of the head control object unit when there is no control object in the set of all target position units An operation planning section for object movement,
When a control object exists in a set of all target position units, each of the control object operation motion planning units is included in the set of target position units but is not included in the set of target positions. To control each object to move,
Behavior control system. The behavior control system according to claim 1,
M = 2, N = 2,
Behavior control system. M and N are each an integer greater than or equal to 2, p is an integer greater than or equal to M × N, and p control objects arranged in a set of start positions include target positions including a predetermined entrance position A behavior control method for performing behavior control to move to a set of
The direction not parallel to the first direction is the second direction, the opposite direction to the first direction is the third direction, the opposite direction to the second direction is the fourth direction, and each start position and each The target positions are adjacent to other start positions and target positions in at least one of the first direction to the fourth direction, respectively, and the set of the target positions and the set of the start positions each have an arbitrary shape in a lump. And
The control object includes a first position adjacent in the first direction on the two-dimensional plane of the control object, a second position adjacent in the second direction, a third position adjacent in the third direction, and a fourth position. It is assumed that the fourth position is adjacent in the direction and is controlled to move to any one of the first to fourth positions on the two-dimensional plane.
The p control objects constitute one control object unit for each M × N units, and the M × N control objects constituting one control object unit each have two or more directions. Adjacent to other control objects constituting the control object unit,
When a set of target position units consisting of position units consisting of N × N positions is set from the set of target positions, and the control object unit takes each action a at the current position s of the control object unit It is controlled based on one value function that represents the appropriateness of the image, and is stationary or moved to a position unit composed of N × N positions in any of the first to fourth directions on the two-dimensional plane. And shall be controlled as
If the movement planning unit for determining the movement target platoon has no control object in the set of all target position units, Ga is defined as a platoon in which multiple control object units are formed, and other control object units are formed. The convoy is Gb, the control object unit that is present in the convoy Gb and not in the convoy Ga is the head control object unit, and the p control objects arranged in the set of the start positions are the set of the target positions. When moving to, movement target corporal decision operation planning step for determining the platoon Gb for the constellation Ga at a certain time using the value function, so that the head control object unit serves as the head of the movement,
When there is no control object in the set of all target position units, each motion target motion planning unit is configured so that M × N control objects are located at the position of the head control object unit. Controlling the operation of the control object;
When each control target object motion planning unit includes a control target object in a set of all target position units, each control target object motion planning step is included in the target position unit set. A step of controlling each control object to move to a position not included in the set of target positions,
Behavior control method. The behavior control method according to claim 3,
M = 2, N = 2,
Behavior control method.   A program for causing a computer to function as the behavior control system according to claim 1. M, N, and Q are each an integer greater than or equal to 2, R is any integer greater than or equal to 24, p is M × N × Q × R, and control of p units arranged in the set of start positions A behavior control system that performs behavior control for moving an object to a set of target positions including a predetermined entrance position,
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 the two directions is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and one position unit consisting of M × N × Q positions, The start position and each target position are adjacent to other start positions and target positions in at least one of the first direction to the sixth direction, respectively, and the set of target positions and the set of start positions are each R pieces. It forms an arbitrary shape consisting of a plurality of 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. Adjacent fourth position, fifth position adjacent in the fifth direction, sixth position adjacent in the sixth direction, either stationary, or any of the first to sixth positions in the three-dimensional space Shall be controlled to move,
The above-mentioned control objects of p units constitute one control object unit for each M × N × Q units, and there are three control objects of M × N × Q units constituting one control object unit. Adjacent to other control objects constituting the control object unit in the above direction,
The controlled object unit is controlled based on one value function that represents the appropriateness when each action is taken in the current position unit of the controlled object unit, and the controlled object unit is stationary or in a three-dimensional space. It shall be controlled to move to a position unit consisting of N × N × Q positions in any of the first to sixth directions,
A storage unit for storing the value function;
A convoy that consists of multiple control object units is Ga, another convoy that consists of multiple control object units is Gb, and a control object unit that exists in the convoy Gb but does not exist in the convoy Ga is a head control object unit. And the value function is used so that the head control object unit acts as a head of movement when moving the p control objects arranged in the set of start positions to the set of target positions. The movement plan determining unit for determining the column Gb for the column Ga at a certain time,
An operation planning unit for each control object operation that controls the operation of each control object such that M × N × Q control objects are located at the position of the head control object unit,
The value function is obtained using a Manhattan distance from a certain position unit to a position unit including the predetermined entrance position.
Behavior control system. The behavior control system according to claim 6,
M = 2, N = 2, Q = 2,
Behavior control system. M, N, and Q are each an integer greater than or equal to 2, R is any integer greater than or equal to 24, p is M × N × Q × R, and control of p units arranged in the set of start positions A behavior control method for performing behavior control for moving an object to a set of target positions including a predetermined entrance position,
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 the two directions is the fifth direction, the opposite direction to the fifth direction is the sixth direction, and one position unit consisting of M × N × Q positions, The start position and each target position are adjacent to other start positions and target positions in at least one of the first direction to the sixth direction, respectively, and the set of target positions and the set of start positions are each R pieces. It forms an arbitrary shape consisting of a plurality of 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. Adjacent fourth position, fifth position adjacent in the fifth direction, sixth position adjacent in the sixth direction, either stationary, or any of the first to sixth positions in the three-dimensional space Shall be controlled to move,
The above-mentioned control objects of p units constitute one control object unit for each M × N × Q units, and there are three control objects of M × N × Q units constituting one control object unit. Adjacent to other control objects constituting the control object unit in the above direction,
The controlled object unit is controlled based on one value function that represents the appropriateness when each action is taken in the current position unit of the controlled object unit, and the controlled object unit is stationary or in a three-dimensional space. It shall be controlled to move to a position unit consisting of N × N × Q positions in any of the first to sixth directions,
The movement planning unit for determining the movement target platoon sets Ga as a platoon consisting of multiple control target units, and Gb as another platoon consisting of multiple control target units. When the object unit is a head control object unit and the p control objects arranged in the start position set are moved to the target position set, the head control object unit is the head of the movement. To determine the formation Gb for the formation Ga at a certain time using the value function,
For each control object operation, the operation planning unit for each control object operation controls the operation of each control object so that M × N × Q control objects are located at the position of the head control object unit. An action planning step,
The value function is obtained using a Manhattan distance from a certain position unit to a position unit including the predetermined entrance position.
Behavior control method. The behavior control method according to claim 8,
M = 2, N = 2, Q = 2,
Behavior control method.   A program for causing a computer to function as the behavior control system according to claim 6 or 7.