- The agent’s sensorial and actuation spaces have to be abstracted in the onboard resources (CPU memory, CPU speed, controllers, etc.).
- This abstraction depends on the interactions that this agent experiments in the environment.
- As a result of the abstraction, every agent has a representation model of the environment.
- The interactions among agents and environment-agents are asynchronous, complex, and in concurrency in the real world. The physical agents are continuously running in continuous time.
- On the other hand, the real physical interactions give good data for learning (software agents lack this).
Definition 2: Extension of the agent concept
from software to physical agent. This definition consists of definition
1 and also a physical body.
Let us assume, for reasons of performance, that there is no single agent capable of doing a task alone. Every agent has to apply to the others for help. Then, each individual has to decide between the following problems: Which agent am I going to help to? On what terms am I committed to? The decision could be either deliberative or reactive. An interpretation of commitment [2] will be used for the agents. Agents that accept to help (are committed), have to know the implications of these commitments. In other words, whether they could do it or not.
For knowing what is possible or not to be done, some physical knowledge has to be taken into account. This means, physical inputs and outputs from the environment have to be mapped in the knowledge base of each agent. This is because agents have to control their physical body by means of proper physical decisions.
C. What Dynamical Physical Agents Are?
Previous analysis is true but now consider systems whose movements can be described by differential equations, that is, can be portrayed by its dynamics. Then the automatic control theory has something to assert.
Definition 3: Extension of the agent concept from
physical agent to dynamical physical agent. Complementing Definition 2
with the following new assertion: The knowledge is obtained from dynamics
of the physical body, which is represented by a further declarative control
and supervision levels [16] [17].
III. MATERIALS AND METHODS
Planning of coordinated motions for robots playing soccer game opens a new deal in motion planning, namely coordinated motion planning in team competition. The game situation continuous varies, that is, this kind of game consist of a dynamic system which constantly evolves.
The robots are devised and controlled taking into account
two main tasks:
- Low-level tasks. Main task is to execute the movement commands with accuracy. This level consists of velocity closed-loop control implemented on the robots.
- High-level tasks. Main task is to generate the movement commands to be executed by the robots. This process is done by using two computers: one for the vision system and the other one for the command generation procedure.
A: Technical Specifications of the Robots:
According to the FIRA rules, robots have strong limitations on their size so that communication features, such as autonomous motion capabilities, must be implemented by using miniaturized instruments. Therefore, it is necessary to design a control architecture that can adequately control the robot without overtaxing the available computation resources. Paying attention to "Fig. 1", robots are composed by one receiver, a CPU unit, a power unit, two micro-motors, and batteries for motion, communication and control unit supply voltages.
1. GENERAL VIEW OF THE MICRO-ROBOT
The hardware robot is devised from a 87C552 microcontroller, which is capable to change the speed of the robot using two PWM outputs according to the velocity control requirements. The actuators are two DC motors, including gear and encoder in the same axis of the motor. The connection between microcontroller and these motors is made through a L293 chip. Optional sensors consist of two photoelectric ones: one is placed high enough in order to detect the obstacles but not the ball, and the other is placed to detect the ball into a closed area in front of the robot. By integrating these two sensors, robot control procedure can efficiently distinguish which kind of thing is detected in front of the robot: ball or obstacle. Finally, communication between the host computer and robots is carried out by RS232 radio-communication, then every robot has one receiver and one identifying code (here called ID_ROBOT).
Here follows a brief description of some important components of the robots:
87C552: This microcontroller contains a non-volatile 8K´ 8 read-only program memory, a volatile 256´ 8 read/write data memory, 6 configurable I/O ports, two internal timers, 8 input ADC and a dual pulse with modulate output.
L293: Contains two full bridges and drivers, with an external component which is capable to control the speed and the sense of rotation of both motors.
Sensors: Two optional photoelectric switches with adjustable distance of detection. Its outputs are open collector.
Motors: Maxon DC motor, 9V, 1,5 W, nominal speed of 12.300 r.p.m., and Maxon gear (16:1).
Encoder: Digital magnetic encoder with 16 counts per turn.
Receiver: Super-heterodyne receiver with monolithic filter oscillator (433,92 Mhz).
Batteries: Each robot is supplied by 9 batteries of 1,2 V - 1000 mA/h.
2. TOP VIEW OF ROBOTS (A) BOARD DETAILS, (B) CHASSIS SCHEMA
B. Overall System
Robots do not have any camera on-board so that a global vision system is needed. In this work, the vision system [ 9] is implemented on a Pentium PC-computer (PC_2, see "Fig. 3") which process 7 frames/s. Obtained data are positions of all the objects in the game field (ball and robots) and orientations of the proper team robots. Data are shared with another computer using TCP/IP communication protocol (PC_1, see "Fig. 3"), and then used for the command generation procedure. This computer host also process strategy parameters, decision-making and collision-free path planning algorithms. The emulation of software agents is in the host computer with feed back from the physical agents, that is to say, the robots.
3. HIGH-LEVEL CONTROL STRUCTURE
C. Low-level Control
This section explains the main program of the robot which allows velocity control. When movement commands sent by the host computer are received by the robot, they are immediately executed. Every command has the following frame:
ID_ROBOT | #movements | mov_1 | mov_2 |. . . | ETX (1)
,where mov_X := linear_velocity | rotation_ velocity | time. Since the maximum speed of the robot can be 120m/s (straight way), usual speed values are set up to 60cm/s using a slope function in order to avoid skidding. When the last movement is executed, another slope function is used to stop the robot. The control of the movements is carried out by using three signals: those coming from the encoders (velocity closed-loop) and batteries voltage.
While movements are executed, the sensors can interrupt the main program because photoelectric sensors are directly connected to the interruption lines. When an obstacle or a ball is detected, the robot can react according to interruption function procedure; on-board sensors can be helpful to the robot in order to react in front of obstacles and walls, or look for the ball. These two sensors are optional in the sense that it is possible to get the robot totally or partially controlled with information from the host computer. Without sensors (disabled) the command frame is the previous frame (1), but when the sensors are enabled then frames must be as follows:
mov_X := linear_velocity | rotation_ velocity | time | behavior_byte
The value ‘behavior_byte’ is used as a parameter in the interruption function so that the movement of the robot becomes technologically speaking more autonomous, that is to say, reactive. Then, this kind of frame allows the robot itself to respond to contingencies in real time. However, these sensors were disabled for MIROSOT competition to avoid purely reactive behavior because they can get the robot stuck in loops. An example of this loops occurs when the robot is placed in front of the wall: the host computer sends commands to move the robot forward in order to turn it whenever the reactive robot is forced to back up when upper IR sensor detects the wall.
Although random perturbations will eventually get a reactive robot out of many loops, the environment of the soccer game in MIROSOT competitions is very dynamic: it consists of six robots moving fast through a 130´ 90 cm. sized ground. Under this point of view, the sensors in MIROSOT competition where disabled. In future competitions the sensors will be enabled using internal states to improve performance as shown in [ 10] .
D. The vision System
Every robot is equipped with two color bands: the first one is the color of the team and the other one is a robot specific-color. Finding the center of gravity of both regions allows the system to know the position and orientation of the robots.
The vision system is composed of a color camera, an specific color processor [9] and a multiple purpose frame-grabber. The camera is located at 2 meters over the playing field and the vision system is able to segment and track the moving robots and the ball over a sequence (see "Fig. 3"). The segmentation step is performed by means of an specific processor which performs a real-time conversion from RGB to the HSI space [ 9] . This processor uses the discriminatory properties of the three color attributes: hue, saturation, and intensity, in order to segment everyone of the regions in scene. Selecting different values o these attributes for every object avoids the correspondence problem in multi-tracking environments. The result of the segmentation model is an ../files/image 768´ 576 with several labeled regions on a black background. The cycle time of the segmentation module is 40 ms, that is, video rate on the CCIR standard.
The second step consists of the computation of the position and orientation of every object by using the enhanced ../files/image from the segmentation module. As a first step a median filter is applied to the region-labeled ../files/image, in order to reduce noise. Then a multiresolution approach is applied: a second ../files/image is constructed, taking one pixel over four from the filtered ../files/image. This second ../files/image is scanned searching for the labeled regions, and when these regions are detected then the exact position is computed in the high-resolution ../files/image, to increase accuracy of the measurements.
4. TRACKING SEQUENCE
There is a state vector which keeps the information about the position of every robot. At every time step, a new prediction is performed of the next position of every object using a 2D polynomial regressive model over the low-resolution ../files/image. This prediction is used in the next time step in order to search for the object, and an error factor is measured to be taken into account for the next prediction. The cycle time of the tracking module depends on the data to be processed and the accuracy of the prediction. Normal cycle time is around 150 ms.
At the end of every processing cycle the vision system sends the state vector to the host computer by means of a TCP/IP connection.
E. Path Planning
The used algorithm is based on Artificial Potential Fields (APF) approach [ 11] and some modifications proposed in [ 12] . In that way, the playing field is equivalent to a 36´ 48 matrix. Then, a Cartesian co-ordinate system is used to define the position of the center of each square cell, which allocates the value of the associated potential. When the guidance matrix elements have been settled, the algorithm will systematically scan the robot’s three neighboring cells to search for a potential value that is lower than that of the cell currently occupied by the robot. The trio of the cells to be scanned (see "Fig.E") depends on the orientation information given by the relative direction from the robot to the set-point position, that is to say, eight possible orientations: {North (N), North-East (NE), East (E), South-East (SE), South (S), South-West (SW), West (W), North-West (NW)}. In such a way, the scanning method is goal finding.
5. EXAMPLE. ONLY CELLS WITH DASHED LINES ARE SCANNED WHEN RELATIVE DIRECTION IS SE
Obtained guidance matrix give a path that could followed by the robot but the real execution of such path has no sense because it has a high number of turns. Therefore, a filtering process is applied and a smoothed path is obtained, as shown in "Fig. 6". At the end of the algorithm, an index of difficulty to execute this collision-free path is obtained taking into account the number of turns and the whole distance to be covered by the robot. This index of difficulty is normalized from 0 to 1:
0 ® Set-point position is straight way.
1 ® Set-point position can not be reached in 500 steps.
F. Co-operation
The decision-making structure is devised in two hierarchical blocks: higher one contains those tasks related to the collectivity (co-operative block), that is to say, communicative actions, and lower one where the agent executes its private actions (private block).
6. EXAMPLE OF COLLISION-FREE PATH FINDING RESULT. (A) 3-DIMENSIONAL VISUALIZATION OF THE POTENTIAL FIELD ASSOCIATED TO THE GAME FIELD. THIS EXAMPLE CONTAINS FOUR OBSTACLES. (B) ZOOM IN AREA: DOTTED LINE CORRESPONDS TO FILTERED PATH. INDEX OF DIFFICULTY = 0,7.
Private Block. Every agent is able to execute several actions according to a set of capabilities, in terms of AGENT0 language. In this block, this set is forced to include persistence capabilities because the environment is dynamic and continuously changing. This block manages several types of information so that three levels are defined depending on the abstraction degree of this information (see "Fig. 11"): agent level (behavior decisions), supervisory level (path planning -hidden intentions- and set-point calculations), and control level (execution of set-points).
Here follows some examples of real situations with only one robot; it must score to the right side of the plots. Data are acquired every 150 ms., and plots uses a Cartesian co-ordinate system where units corresponds to ‘cm’. In this examples, the behavior of the robot is set manually but the system automatically assigns different actions to the robot.
Example 1:
- Situation® "The
ball is not moving and close to the goal"
Behavior ® Defend_as_goalkeeper
Actions® Go_back_to_ball, Stand_close_to_goal_following_the_ball
- Situation®"Initially
the ball is not moving. Then it moves"
Behavior ® Defend_as_goalkeeper
Actions® Go_back_to_ball, Stand_close_to_goal_following_the_ball
- Situation®"The
ball is not moving and it is easy to score"
Behavior ® Attack_as_goal_scorer
Actions® Go_back_to_ball,
Obtain_good_orientation, Shoot
7. (A) EXAMPLE 1, (B) EXAMPLE 2
Example 4:
- Situation ® "The
ball is not moving but it is not easy to score"
Behavior ® Attack_as_ goal_scorer
Actions® Go_back_to_ball,.Avoid_wall,
Obtain_good_orientation, Shoot
8. (A) EXAMPLE 3, (B) EXAMPLE 4
Example 5:
- Situation ®"The
ball is not moving"
Behavior ® Protect_goal
Actions ® Go_to_baricenter,
Stand_there
9. EXAMPLE 5
Co-operative Block. The agent level is the connection between the agent itself (autonomous robot) and the collectivity so that it includes communicative actions to request or inform about three parameters which will be helpful to the agent decisions. These three parameters consist of which behavior has been decided (private block), what is the index of difficulty of its execution, and what is the relative distance from the robot to the set-point position. This block is based on Agent-Oriented Programming (AOP), and uses a subset of the communicative primitives defined by AGENT0: {‘request’, ‘inform’}.
With this structure, decision-making procedure can take into account both collective and individual decisions, based on the communication between agents and the exchanged information between the behavior and supervisory levels. By this way, collective decisions are based on strategy rules, and individualized decisions are only based on the index of difficulty and the relative distance from the robot to the set-point position. These two parameters are calculated in the supervisory level and, because it is contained into private block, it contains different parameters for every agent, in other words, different behavior for every agent that is included in the path planning method.
Here follows some more examples of real situations with three robots; one has ‘Protect_goal’ behavior constantly assigned. In this examples, the behavior of two robots are set automatically by co-operation procedure using relative distances as evaluation parameters. Although these two examples use relative distance as the evaluation parameter, the use of the index of difficulty as the evaluation parameter shows the same results. It must be noticed that both parameters are useful when obstacles are present in the game. Then, behaviors are changed when relative distances are on some predefined threshold values.
Example 6:
- Situation®"The
ball is not moving and near to the wall"
Behavior_1® Protect_goal (because D1>D2) Behavior_2 ® Attack_as_ goal_scorer (D2<D1)
Actions_1 ® Go_to_baricenter, Stand_there
Actions_2 ® Go_back_to_ball,
Avoid_wall, Obtain_good_orientation, Shoot
- Situation ® "The
ball is not moving and near to the wall"
Behavior_1® Attack_as_goalie (because D1<D2) Behavior_2 ® Protect_goal (D2>D1)
Actions_1® Go_back_to_ball, Avoid_wall, Obtain_good_orientation, Shoot
Actions_2 ® Go_to_baricenter,
Stand_there
10. (A) EXAMPLE 6, (B) EXAMPLE 7
IV. DESING OF THE CO-OPERATION SYSTEM
The scheme in "Fig. 11" represents the way the information, analysis, design and implementation, is distributed in each level. Also, all co-operative actions are responsibility of the behavior level. The AOP and agents could be applied to any levels although to start the application of agents in the behavior level is advisable.
11. THIS SCHEME REPRESENTS THE WAY THE INFORMATION MOVES
The co-operation of the team of robots is done at the agent (behavior) level, that is also responsible for the behavior of each robot by exchanging information to the supervision level. Originality of this work is the representation of co-operative behavior by means of an AOL that is developed in a CACSD framework so that the link behavior-supervisor could be easily implemented with tools from the automatic control field.
However, new difficulties appear in the functional protocol between the behavior and the supervisor levels, namely the persistence of goals that the AGENT0 language lacks. This lack is overcome by tuning the sample time of agent® supervisor communication that leads to persistence develop at the supervisor level.
A. Persistence: Which is the problematic of all three levels [ 6][ 13][ 14] ? The fact is that the behavior level controls the path planning of the supervision level, and the latter calculates set-points and supervises the performance of the control level that is responsible for the effective movements of the micro-robots. The environment of the game is changing continuously and this represents a difficult scenario for doing path planning that is responsibility of the supervision level. The behavior level must overcome this problem by choosing correctly the target positions that the path planner must get through. But, to do that the behavior level needs of some evaluation of the difficulties of possible targets, to decide what to do and then start the co-operative procedures to finally precisely decide what to do.
In continuously changing scenario the robot could be the whole time changing decisions of where to go. This problem we call it lack of persistence because from agents’ point of view, the decisions of the behavior level do not last enough time to success in targets, regardless of whether the targets are accurate or not. This persistence could be developed at the behavior level or the supervision level. If the behavior level does not work till the last target is succeeding by the supervision level then this is the case the responsibility for persistence is due to the supervision level. On the other hand, if the behavior level is the whole time inspecting the accuracy of targets but explicitly dealing with persistence of goals so that any change is a measured decision (not purely reactive), and then this is the case the responsibility is due to the behavior level.
To implement the latter case, responsibility for persistence in the behavior, a new AOL is required to explicitly represent intention, because the AGENT0 language does not contain this specification. Future work is to implement this persistence at the behavior level by means of PLACA language, following the instructions of [ 15] . Therefore, in this work the former case of responsibility due to the supervision level is initially chosen because of its simpler conception.
To solve the problem of difficulty evaluation of situations to help the behavior level to decide, a fuzzy measure is implemented, obtained from the path planner procedure (section 2.5.). This difficulty measure depends on the value of two parameters: the number of cells (or matrix elements) to be crossed by the robot, and the number of scanned cells. With the first parameter, the supervisor level can obtain a measure of distance and, combining both parameters a fuzzy measure of turns can be also obtained. When supervisory level knows these two values, behavior (agent) level uses them to improve its reactive and cooperative decisions.
Here follows another example similar to example 6, but now the ball is moving. In this example the persistence is at the behavior level, and only the relative distance is used as evaluation parameter.
Example 8:
Situation ® "The ball is moving. Start point is near to the wall"
Behavior_1 ® Protect_goal (because D1>D2)
Behavior_2 ® Attack_as_goalie (because D2<D1)
Actions_1 ®Go_to_baricenter, Stand_there
Actions_2 ®Go_back_to_ball, Obtain_good_orientation, Go_back_to_ball
EXAMPLE 8. SHOWING THE PERSISTENCE OF ROBOT 2
B. Simulation Results: The simulator introduced in [ 1] that uses the tools of M/S contains good continuous dynamic behavior of the soccer micro-robots and ball movements. The behavior level is inspected in some cases, thus testing the strategy and its impact in a continuous world. The simulator also provides with animation tools to see the evolution of the system over the soccer field. One result due to the discrete nature of the behavior level is that cyclic sequences sometimes appear because of the non linear components of the negotiation algorithms. For instance, cycle normally comes up when two agents decide ‘Go_back_to_ball’ action at a time: the fulfillment evaluation oscillate periodically because the environment conditions change significantly in a short period of time.
However, the simulation permits to evaluate the working conditions of the decision process and its impact in a continuous world. This decision process depends on the selected profile of each agent in the case that specialized rolls are intended.
V.CONCLUSIONS
The previous work [ 1] contained important new items such as the adaptation of an AOL (AGENT0) to the M/S application. Although M/S has not proper language to implement AOL the AGENT0 development was possible although difficult. That implementation contemplated the automatic code generation with RTW (Real-time Workshop) toolbox of M/S that was partially solved. Another novelty was the inclusion of fuzzy logic in the behavior decision process, incorporated to the AGENT0 language.
Lacks of the current work:
A.- The persistence problem is not finely solved because the solution of focusing on the supervision level to maintain the decision of the behavior level is rather rough due to the highly changing nature of the soccer game. The persistence means to maintain previous decisions while it is obvious there is no proper alternative.
B.- To link supervision « control levels is also necessary because supervision systems are not so far fully developed to calculate physically good set-points that the control level of the robot could execute. To incorporate this exchange, new controllers technology should be included to robots.
C.- A new language closer to control engineers and applied mathematics is necessary to develop agents under AGENT0 language.
D.- Engineers do still not accept the design methodology proposed in previous work [ 1] since they do not have the tools to develop it.
The experience in MIROSOT is about the lack of robustness in our approach since, even though the persistence in agents was a task of the supervision level, the generation of events from the dynamically (continuous state and time dynamically variables) is a complex matter. The suggestion to solve it is to apply theory from hybrid systems.
Future work is to introduce predictive control algorithms in the control level to easy the supervision « control activity. Also, the PLACA language [ 15] will be included to compare how does it improve our current work in terms of persistence and analysis representation poverty, after the improvement of the behavior « supervision communication contents. Finally, an increase of the use of agents in simple automatic control application is expected, with the development of agents’ librarian toolboxes within this framework.
VI. ACKNOWLEDGEMENT
This work has been partially funded by the TAP98-0955-C03-02 "Diseño de agentes físicos (DAFNE)" y TAP99-1354-E, "Eurobot-Iberia: red temática en agentes físicos" of the CICYT Spanish government.
VII. REFERENCES
[ 1] De la Rosa J.Ll., Oller A., et al. "Soccer Team Based on Agent-Oriented Programming". Robotics and Autonomous Systems. 1997. No. 21, pp. 167-176.
[ 2] Shoham Y. "Agent-Oriented Programming". Artificial Intelligence. 1993. No. 60, pp. 51-92.
[ 3] MIROSOT is the acronym of IEEE Micro-Robot Soccer Tournament, held in November 5-11 in KAIST (Taejon, Korea), 1997.
[ 4] FIRA is the acronym of Federation of International Robotic-soccer Association. http://www.fira.org.
[ 5] Tambe M. "Teamwork in real-world, dynamic environments". Proceedings of the International Conference on Multi-agent Systems (ICMAS). December 1995.
[ 6] Brooks R.A. "A Robust Layered Control System for a Mobile Robot". IEEE Journal of Robotics and Automation. March 1986. Vol.RA-2, No.1, pp. 14-23.
[ 7] Chatila R. "Deliberation and Reactivity in Autonomous Mobile Robots". Robotics and Autonomous Systems. December 1995. Vol. 16, pp. 197-211.
[ 8] MATLAB (ver. 4.2c.1) and SIMULINK (ver. 1.3c) are trademarks of Mathworks Inc. 1994.
[9] Forest J., García R. et al. "Position, Orientation Detection and Control of Mobile Robots through Real Time Processing". Proceedings of World Automation Congress, Robotic and Manufacturing Systems. May 1996. Vol. 3, pp. 307-312.
[ 10] Gat E., Rajiv R., et al. "Behavoir Control for Robotic Exploration of Planetary Surfaces". IEEE Tran. Robotics and Automat., 1994. Vol. 10, No. 4, pp. 490-503.
[ 11] Kathib O. "Real-Time Obstacle Avoidance for manipulators and Mobile Robots". International Journal of Robotics Research. 1986. Vol. 5 No.1, pp. 90-98.
[ 12] Clavel N., Zapata R., et al.. "Non-holonomic Local Navigation by means of Time and Speed Dependent Artificial Potencial Fields". IFAC Intelligent Autonomous Vehicles. 1993. pp.233-238.
[ 13] Albus J.S. "Outline of a theory of Intelligence". IEEE Transactions on Systems, Man and Cybernetics. May 1991. Vol.21, No.3, pp. 473-509.
[ 14] Simmons R.G. "Structured Control for Autonomous Robots". IEEE Transactions on Robotics and Automation. February 1994. Vol. 10, No. 1, pp. 34-43.
[ 15] Thomas S.R. "A Logic for Representing Action, Belief, Capability, and Intention". Stanford working document. Stanford, CA. 1992.
[16] Kitano H., Veloso M., et al., "The RoboCup Synthetic Agent Challenge 97". XV IJCAI-97 International Joint Conference on Artificial Intelligence, Vol 1, pp.24-29, Nagoya, August 1997.
[17] Oller A, de la Rosa J.Ll., and del Acebo E., "DPA2: Architecture for Co-operative Dynamical Physical Agents", MAMAAW ’99, Valencia June 1999
[18] Asada M., Kuniyoshi Y., et al. "The RoboCup Physical Agent Challenge". First RoboCup Workshop in the XV IJCAI-97 International Joint Conference on Artificial Intelligence, pp.51-56, 1997.
[19] Wooldridge M., Jennings N. "Intelligent Agents: Theory and Practice". Knowledge Engineering Review, October 1994.
