һ�����ʶ��ƶ�������ϵͳ�������MAS��Э������
Էȫ��1,2, �� ��1, ����F1, ����Ƽ2
1.��������ҵ��ѧ �������ѧ�뼼��ѧԺ,������150001
2. ��������ѧԺ ��������Ϣ����ѧԺ,���� 130012
ժҪ
Ŀǰ�Ķ��ƶ�������ϵͳ������״̬��,����ṹһ���Ǿ�̬��,����������Ա�����˵Ķ�̬����,��ϵͳ������ʱ��Ҫ�������á����������һ��֧�������ƶ������˺����Ķ������ϵͳUMRS-1,���÷ֲ�ʽ��֯�ṹ,֧�ֻ����˶�̬���Զ����õؼ�����˳�ϵͳ�����������ϵͳ�ij�Ա�����˵���ϵ�ṹ�Լ�UMRS-1����֯�ṹ�����û���KQMLʵ�ֵĺ�ͬ����ΪЭ��Э��,���Զ������Э��Χ����������˳���̽����˵��UMRS-1��ͨ����Э�����ơ�
�ؼ���: �˹�����; ��Agentϵͳ; ���ƶ�������ϵͳ; UPnP; KQML; ��ͬ��Э��
Heterogeneous multiple mobile robot and its cooperation mechanism based on MAS
YUAN Quan-de1,2, GUAN Yi1, HONG Bing-rong1, MENG Xiang-ping2
1.School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001
2.School of Electrical Engineering and Information Technology, Changchun Institute of Technology, Changchun 130012
Abstract
The network structure of most of current multiple mobile robot systems is static when they are running. So it is difficult to alter the number of the robots. Most of the systems need complicated configures when launching. In this paper, a multi-robot system, UMRS-1, is proposed, which uses distributed architecture, supporting heterogeneous mobile robots. In UMRS-1, member robot can join in or quit from the system dynamically. The architectures of member robots and UMRS-1 are analyzed. It uses KQML-based Contract Net Protocol (CNP) as cooperation protocol. The multi-robot hunting problem is discussed to show the communication and cooperation mechanisms of UMRS-1.
Keyword: artificial intelligence; MAS; MMRS; UPnP; KQML; CNP

���ڶ������ϵͳ[1]���о���Ҫ������֯�ṹ��ͨ�š�������䡢������֪�붨λ��ѧϰ���۵�����[2]���������ϵͳ����֯�ṹ��ͨ�Ż����ǹ��ɶ������ϵͳ�Ļ���,�����о�������Ҫ���塣ͨ���������ϵͳ����֯�ṹ��������ʽ�ͷ�ɢʽ,���з�ɢʽ�ֿɷ�Ϊ�ֲ�ʽ�ͷֲ�ʽ[3],Ҳ���о���������ʽ�����ڶ������ϵͳ�ij�Ա������֮���ͨ�ż���,�еĶ������ϵͳֱ��ʹ��TCP/IPЭ��[4,5,6],����ͨ�ŷ�ʽʹ�õ�Э���Ϊ�ײ�,����̶Ƚϵ�,������Ա��ƻ�����ϵͳ��Ҫ���ѽ϶�ľ�������ͨ������;�������Ȳ���Corba����������һ��������˻�����ϵͳ[7],���񶫵�ʹ��JINI����ʵ������������˲���������֪ģ�������е�Ӧ�ý������о�[8],ʹ��JINI����ʵ�ֵĶ������ϵͳ,��������Ҫ��һ����������������л����˵�ע����Ϣ,��Ϊ��Ա�������ṩ���������˵���Ϣ,һ���ù���������ֹ��Ͻ����»�����֮���޷�����ͨ�š�

���ڽ�UPnPЭ��Ӧ���ڻ�����ϵͳ�е��о�,Ahn���˿����������ڻ�����ϵͳ��UPnPЭ��ջ[9],��������ʹ��UPnPЭ��ʹ����������Χ�Ļ�����Դͨ��[10],����δ�����н�UPnPЭ��Ӧ���ڶ������ϵͳ�еı�����

������UPnPЭ�������,������һ����Ϊ���Ķ��ƶ�������UMRS-1ʵ��ϵͳ,������Ϊ�о��������ͨ�š�Э���ȿ����ƽ̨�����������ԵĽ���취�Ƕ�ԭ��ϵͳ��һ������,��Ƴ�ͳһ���߼��ṹ����ϵͳ��ԭ�л����˻����ϼ�֧����Ҫ�̶�������ʩ������,Ҳ֧��Ad Hoc����,��ϵͳ���÷ֲ�ʽ���ƽṹ,����������ӻ��߼���ϵͳ�еĻ����˶�����Ҫ�������á��ڴ˻�����,Ϊ��֤��ϵͳ������,���Agent֮���ͨ��Э��ͷ���,����KQML����ʵ�ֵĺ�ͬ��Э��Զ������Э���������о���

1 UPnP�ܹ�

UPnP�������IP,TCP,UPD,HTTP,SSDP,SOAP��InternetЭ���Լ�XML�ȼ���,ʹ�������豸����������������Χ�豸�������弴�õ�Ч������ʵ�����輼����ͼ1��ʾ��

UPnP�ṩ�˹㷺�ĵ�Ե����������,���������������Ӧ���Լ������豸��UPnP��һ������TCP/IP��Web�ķֲ�ʽ�����ŵ�����ܹ�,ʹ���ڼ�ͥ���칫�ҵȸ��������е��豸���Ի�����ơ��������ݡ�UPnP֧�������ú��Զ�����,����һ��ʵ����UPnP���豸���Զ�̬�������硢�Զ���ȡ��ַ�������Լ������֡�ͨ��������˵���Լ�����������֪�����豸�Ĵ��ں�������ƽ���뿪����������²���Ҫ��״̬��Ϣ��

ͼ1 UPnP�����ṹͼFig.1 Hierarchical graph of UPnP
2 ʹ��UPnP�ķֲ�ʽ�������ϵͳ��ϵ�ṹ
2.1 ��Ա������

UMRS-1ϵͳ������һ�������ϵķֲ�ʽϵͳ,�ӿ����߼��Ƕ�Ҳ�Ƿֲ�ʽ��,��Ա�����˵�λ��ͬ,ֻ����ʱ����������,û�й̶��Ĺ����ߡ������˿�����ʱ����ϵͳ,Ҳ����ʱ�˳�ϵͳ,����Ҫ��������á������������Ҫ��ʱ��һ�������˷����ʵ�������滮,��ͨ���г����������������,�������,������ɺ�,�����漴��ɢ�������Ľṹ�dz��ʺϻ�����Ѳ��ϵͳ��Χ��ϵͳ�����ܼ�ͥ�ȳ��ϡ�

�����ϵͳ�Ļ��������͡����ܿ��Բ�ͬ,����Ҫ�߱���������:��ʵ����UPnPЭ��;�ھ߱����Ķ���Ļ���UPnP��Web�����ͨ������;��Ϊʵ�ֻ�����֮��Ĺ�ͨ,����ϵͳ�Ļ�������Ҫ������ͬ�ı����ۡ�

һ���Ա�����˵Ľṹ����ͼ2��ʾ�����л�����OS���Ǵ��ڻ����˱���������˿������֮���һ��,�ò㸺����л�����Դ�ĵ���,��ͬ�Ļ����˲���ϵͳ���ܲ�ͬ��������SDK�Ǹû������ṩ�Ŀ�����API,ͨ����Щ�ӿ�һ�����ֱ���û�����ִ�л�����Ϊ,��ǰ�������ˡ�ת��̽��ȡ�SDK���о���ԱΪ�����˿���Agent�������Ҫ���ߡ�������ͨ��ϵͳ�ڻ����˲���ϵͳ�ṩ������ͨ�ŷ����UPnP�ṩ��λ�õ���Ϣ������,������������ʵ�����弶���ͨ��,����ʹ��һ��Agentͨ�����Խ������ݷ�װͨ�š��������ھ������ߺ�,����ִ��ij������,�����������ʽ�����ݷ��͸�ִ�в�,�ò����ִ�С�����Ӿ��߲㴫��һ������Ҫ��������˶�������(10,20)��,ִ�в�������Լ���ǰλ��,�滮·����ִ�����е�Ŀ��Ķ����������˾��߲�������Ҫ��һ��,��������,��������ֽ�,����ķ���ȶ�������һ����õײ��ṩ��ط���ʵ�ֵġ�

ͼ2 ��Ա�����˽ṹͼFig.2 Hierarchical graph of member robot
2.2 �»����˼������˳��Ŷ�

�������˴�Զ��ʻ����߿���������Ŀ��������ϵͳ���������,���Ҫ���������,����Ҫ�����ǻ�ȡһ���ڸ������кϷ��ĵ�ַ,û�������ַ,�����е��豸�޷��������豸����ͨ�š���Ա������ͨ��ϵͳ�ǽ�����TCP/IPЭ��������ϵ�,Ҫʵ��ͨ��������Ҫ����һ���Ϸ���IP��ַ������ʹ��DHCP���е�ַ����,���Ѱ�Ҳ���DHCP��������ͨ���Զ�IPѰַ(Auto-IP)����ѡ����ʵĵ�ַ����ȡ��ַ��,��Ա��������Ҫ��֪�����������Լ��Ĵ��ڡ�����UPnP�ܹ�,������ʹ�ü򵥷�����Э��(SSDP,Simple service discovery protocol)����������񡣻�����һ����ȡ�˺Ϸ�IP��ַ,��ͨ����SSDP��Լ���Ķಥ��ַ�Ϸ���һ��NOTIFY��Ϣ�������ڳ�����(presence announcement),��ϵͳ�е�������Ա�����˻�֪�û����˵ĵ�����

��1��ʾ��һ����Ϣ��һ����Ա�����˼��������,������㲥���Լ�����Ϣ�����е�description.xml�ļ������˻����˻�����Ϣ,�������͡��Ѻ����ơ������ߡ�������URL��ģ��������ģ�����ơ�ģ�Ͱ汾�Լ�ģ��URL��UDN��UPC���ṩ�ķ������ж����ṩ�ķ����б�����˷������������Ϣ��XML�ļ���λ����Ϣ���Ըû����˸���Ȥ������������ͨ����xml�ļ��Ϳ���֪�������û����˽����ˡ�

�������������յ����֪ͨ��,����Ըû����˸���Ȥ,����ѡ������Լ��ڲ����ֵĻ������б�,�Ա���һ�������б�ʱʹ�á�

��������ѡ���˳��������ϵͳʱ,��Ҫ��ϵͳ�����˳���֪ͨ,����2��ʾ��������������Ӧ�����Լ��ڲ��Ļ������б�

��1 ��Ա�����˼���UMRS-1ʱ�Ĺ㲥��Ϣ��ʽTable 1 Format of messages that member robots send
to UMRS-1 after their joining
��2 ��Ա�������˳�UMRS-1ʱ�Ĺ㲥��ʽTable 2 Format of messages that member robots
send to UMRS-1 before their quitting
2.3 ������֮���ͨ�ŷ�ʽ

��Ա���������ṩһ������Ի���Web����,�ṩcommunicate(String content)�������������������������ͷ�װ�õ�����,ֻҪԶ�̵��øû����˵�communicate�������ɡ�����ʱ���巢�͸�ʽ���3��ʾ��

<��ͷ> ���û�����ͨ�Žӿ�Web�������Ϣ��ʽ
<��ͷ> Format of messages that calling web
service of robots to communicatePOST/service/�AHTTP/1.0
Content-Type:�Atext/xml;�Acharset=��utf-8��
HOST:�A0.0.0.0:4004
Content-Length:�A322
SOAPACTION:�A��urn:schemas-upnp-org:service:content:1#communicate��
��?xml�Aversion=��1.0���Aencoding=��utf-8��?��
��s:Envelope�Axmlns:s=��http://schemas.xmlsoap.org/soap/envelope/���As:encodingStyle=��http://schemas.xmlsoap.org/soap/encoding/����
�A��s:Body��

��u:communicate�Axmlns:u=��urn:schemas-upnp-org:service:content:1����

��content��
��!---�˴�Ϊʹ��KQMLʵ�ֵĺ�ͬ������--��
��/content��

��/u:communicate��
�A��/s:Body����/s:Envelope�� �������Զ�������,�����˽��յ�������������Ϣ��,��������������,��������������Ӧ�ķ�Ӧ��

2.4 ���ƽṹѡ��

UMRS��Ա�����˵���ϵ�ṹ��ͨ�ŷ�ʽ�����˸ö������ϵͳ�ʺϲ��÷ֲ�ʽ��֯��ʽ��������Ա��λƽ��,ͨ���г���������Э���������

2.5 Э��ʵ��

Э�������ǽ����ͻ��һ�ֻ�����ʽ,�ڶ������Э��������,ͬ�������Ÿ��ֳ�ͻ,Ϊ�˴ﵽ������Ŀ��,ͬ����Ҫ�����Щ��ͻ���ڶ������ϵͳ��,�еĿ�ͨ����ʽͨ�Ž����ͻ,�еĿ���ʽͨ��,�����ŵ�,���к�ͬ��Э����ͨ����ʽͨ�Ž����ͻ�ıȽ���Ӱ���Э�̲��ԡ�

���ں�ͬ�����о�,�����е������һ�����ڸ�֪���ۺ϶����ء�ͳ��Ƕ����񡢶���ԡ���غϵ�agent�������������ֲ�Э��ģ��[11],�պ�����������˻����������˼������ͬ��Э��Ķ�������ϵͳЭ��ģ��[12]�����ں�ͬ����ʵ��,����[13][14]�ֱ��������KQMLʵ�ֺ�ͬ��Э��,��������[13]ΪKQML�����8��ԭ����֧�ֺ�ͬ��Э��,��Щԭ����пɲ�����,�ʱ��IJ�����KQMLʵ���˵ĺ�ͬ��Э����Ϊ������Э�����ơ�

3 Э��ʵ��
3.1 ���������

ʵ��ϵͳ��6̨�ƶ����������,����1̨Voyager 2��,1̨Voyager 3��,4̨С���ƶ�������,ʹ���Ӿ�����Ŀ��ʶ��,���ʹ�����ɽ��ж�λ,ʵ���ͼ3��

ͼ3 ��Ա������Fig.3 Member robots
3.2 �����˺���Χ��ʵ��

�û����˽���Ŀ��Χ���о�Э������,������Ϊ�����ߵ�Ŀ������˻����ϱ���һȦ��4 cm�ĺ�ɫ��־,��Ա������ͨ��ʶ��ñ�ʶ���������߶�λ��

�������Χ����������:��Զ�ά�н���λ�,����դ�񷨶Ի������н�ģ�������д���n��׷���ߺ�m�������ߡ���P={p1,p2,��,pn}��ʾ׷���߼���,��I={i1,i2,��,im}��ʾ�����߼��ϡ�����������״�ʹ�С������ϰ���,ijդ�����Ƿ��ϰ���ռ����ӳ��O:(x,y)->{0,1}���������O(x,y)=1��˵����դ�������ϰ��

�趨������ֻ��һ�������ߵ����,��ij����Ա������MRi������������Intruder��,�ó�Ա������MRi����������ʱ�����ߵĽ�ɫ�����Ƚ���Χ������ֽ�,Ŀǰ��ȡ����������ʱ������MRi����Ŀ���λ��,������������з���:�������ڿ�������һ�߻��߿����ϰ���,��ʱֻ��Ҫ3�������˼���Χס������;��������ij�����߼н���,��ʱֻ��Ҫһ�������˾Ϳ��Զ�ס;�����������Ҫ4�������˷ֱ�ռ����������4�������������Χ��,һ�����͵�Χ��������ͼ4��ʾ��

Ȼ��˳���������������������1�Ż�����MR1��Ϊ��������,�û����˷���Ŀ��λ��(10,20)��,�����������Χ��,��������������:.

Step1 �����߻�����MR1����ͨ���Լ��ڲ�����Ļ������б�ʹ��KQML������������Ϊ�ַ�������,ͨ���������ṩ��communicate���񷢲���ȥ������û������ڲ�û�п��õĻ����˻��߻����˸�������,��ʹ��SSDP�������������й㲥,������п��û����˵ľ�����Ϣ����MR1�����������л����˷���׷��λ��(10,20)λ�õ�Ŀ��Ϊ��,ѯ���ĸ�������������ִ��ռ��Ŀ�������׷�����������,Ҫ��10 s�����,��ֹʱ��Ҳ������,ʹ��KQML����������ʽ����4��ʾ��

Step2 ����Ա�����˽��յ���������˷������б���Ϣ��,���б���Ϣ���뵽�Լ��ڲ�ά�����б��б�,���������ȼ��Ŷ�,�����Լ���ǰ��״̬�����Ƿ�Ӧ�ꡣ��״̬����:���ڹ���,���С�������������ȼ��ϸ�,��ͬ��ʹ��KQML��ɵ�Ͷ����Ϣ��Ӧ��������ˡ���������˱���������ڿ���״̬,�����ڲ�״̬����,Ҳ���Բ��뵽Χ�������С�

����2�Ż����˴��ڿ���״̬,�������������������,��Ϊ�Լ�9 s�����������,����Ͷ��,��Ͷ����Ϣ��ʽ����5��ʾ��

Step3 ����������˽��յ�Ӧ����Ϣ��,����Ӧ��������ṩ���Լ���ǰλ��,�Լ�������ٶȵ���Ϣ,�������ĸ��������б�,�������б���Ϣ������MR2�������б�,�򷢱�����6��ʾ���б���Ϣ��ʽ��

���û�к��ʵĻ�����,���������˿���ѡ��ϱ겢�����б����Step 1������ֹ�бꡣ

Step4 �����б���Ϣ��,��ζ�Ÿ�������������,�ӵ��б���Ϣ�Ļ����˼����빤��״̬,���ٽ��������������,�ȴ���������˷����ж�ָ����������������Ҫ����,ת��Step1,������һ��������ķ��䡣���ȫ���������,����ִ��״̬��

���������ƶ���ָ���IJ�����,�л���Ŀ�����״̬,�����������˱���������ɡ���������˸�����Ӹ�������������״��,���յ����л������������ȷ�Ϻ�,Χ��������ɡ�ʵ�����н������:ϵͳ���Կ������������䲢�ɹ�ʵʩΧ����

ͼ4 ������Χ��Ŀ��Fig.4 Robots round up goal
��4 �����б���Ϣ��ʽTable 4 Format of messages that calling for bidding
��5 Ͷ����Ϣ��ʽTable 5 Format of messages of bidding
��6 �б���Ϣ��ʽTable 6 Format of messages of awarding
4 ������

�����һ�ֻ���UPnP�����ʶ��ƶ�������ϵͳUMRS-1����ϵͳ�������԰�������Ӳ������Ļ�����,Ҳ֧�����Agent�ļ��롣��ΪUPnP����������������������ģʽ��,���Ըö������ϵͳ��֧����Ҫ�̶�������ʩ������,Ҳ֧��Ad Hoc���硣ϵͳ���÷ֲ�ʽ���ƽṹ,����������ӻ��߼���ϵͳ�еĻ�����,������Ҫ�������á��ڴ˻�����,����KQML����ʵ�ֵĺ�ͬ��Э��Զ������Э���������о�,ʵ�����н��֤���˸÷����Ŀ����ԡ�

�����
[1] ̷��, ��˶, ��־ǿ. �������ϵͳ[M]. ����: �廪��ѧ������, 2005. [��������:1]
[2] ������. ���ƶ�������Эͬԭ���뼼��[M]. ����: �����Ƽ�������, 2011. [��������:1]
[3] Cao Y U, Fukunaga A S, Kahng A B, et al. Cooperative mobile robotics: antecedents and directions[J]. Autonomous Robots, 1997, 4��1��: 21. [��������:1]
[4] ������, ������. ����WL���� �Ķ��������Ϣ��������ΪЭ��[J]. ������, 2004, 26��3��: 226-231.
Zhang Wei-xing, Chen Wei-dong. WLAN-based multi-robot communication and action coordination[J]. Robot, 2004, 26��3��: 226-231.
[��������:1] [CJCR: 1.026]
[5] ������, ϯԣ��, �˶���, ��. һ������������Ķ�����˷ֲ�ʽЭ��ϵͳ[J]. ����������Ӧ��, 2002, 19��4��: 505-510.
Chen Wei-dong, Xi Yu-geng, Gu Dong-lei, et al. Complex task oriented multi-robot distributed coordination system[J]. Control Theory and Applications, 2002, 19��4��: 505-510.
[��������:1] [CJCR: 0.88]
[6] Parker L E. Heterogeneous multi-robot cooperation[D]. Massachusetts: Department of Electrical Engineering and Computer Science, MIT, 1994. [��������:1]
[7] ������, ������. ����CORBA �Ķ������Ӧ�û�����ϵͳ���о���ʵ��[J]. ������, 2000, 22��3��: 194-200.
He Ming-xi, Yin Chao-wan. Research on multirobot-oriented application inter-operation system based on CORBA communications[J]. Robot, 2000, 22��3��: 194-200.
[��������:1] [CJCR: 1.026]
[8] ����, �ս���. ������������֪ģ��������������е�Ӧ��[J]. ������, 2006, 28��2��: 144-148.
Gao Zhen-dong, Su Jian-bo. Application of robot autonomous perception model to internet-based robot[J]. Robot, 2006, 28��2��: 144-148.
[��������:1] [CJCR: 1.026]
[9] Ahn Sang Chul, Lee Jung-Woo, Lim Ki-Woong, et al. UPnP SDK for Robot Development[C]��SICE-ICASE International Joint Conference, 2006: 363-368. [��������:1]
[10] ����, ����, ������, ��. �ƶ����������绯������ԴӦ���еĹؼ�����[J]. ������, 2008, 30��1��: 71-78.
Jin Xin, Ma Xu-dong, Dai Xian-zhong, et al. Key technologies enabling mobile robot to utilize surrounding networked resources[J]. Robot, 2008, 30��1��: 71-78. [��������:1]
[11] ������, ���ܴ�, �½���. һ�ָĽ��ĺ�ͬ��Э��ģ��[C]���������й��˹���������ѧ���������ļ�. 1994.
Liu Da-you, Zhong Shao-chun, Chen Jian-zhong. An improved negotiation model of CNP[C]��The 3rd CAAI Conference, 1994. [��������:1]
[12] �պ���, ���Ƕ�, ��ï��, ��. �����������˼������ͬ��Э��Ķ�������Э��ģ��[J]. ������о��뷢չ, 2006, 43��7��: 1155-1160.
Tao Hai-jun, Wang Ya-dong, Guo Mao-zu, et al. A multi-agent negotiation mode based on acquaintance coalition and extended contract net protocol[J]. Journal of Computer Research and Development, 2006, 43��7��: 1155-1160.
[��������:1] [CJCR: 1.761]
[13] ������, ����, ���ɶ�, ��. ����KQML ���Եĺ�ͬ��Э��ģ�ͼ�ʵ��[J]. ��Ϣ�����, 2000, 29��5��: 454-460.
Sun Xian-peng, Zhang Yu, Wang Cheng-en, et al. KQML based contract net protocol model and realization[J]. Information and Control, 2000, 29��5��: 454-460.
[��������:0] [CJCR: 0.468]
[14] ���仪, ������, ����, ��. ����KQML��ʵ�ֺ�ͬ��[J]. �����������Ӧ��, 2000, 36��4��: 106-109.
Chen Wu-hua, Wang Li-chun, Li Hong-bing, et al. Extension of Kqml for realization of contract net[J]. Computer Engineering and Applications, 2000, 36(4)106-109.
[��������:0] [CJCR: 0.561]