Formatievorming in multi-robot systemen

Faculteit Ingenieurswetenschappen Vakgroep Elektrische Energie, Sytemen en Automatisatie Voorzitter: Prof. Dr. ir. Jan Melkebeek

Formatievorming in multi-robot systemen door

Jan De Beule Kristof Vandoorne

Promotor: Prof. Dr. ir. D. Aeyels Scriptiebegeleider: Dr. ir. J. Rogge

Afstudeerwerk ingediend tot het behalen van de academische graad van Burgerlijk Elektrotechnisch Ingenieur

Academiejaar 2005–2006

Dankwoord We wensen iedereen te bedanken die ons geholpen heeft. In de eerste plaats onze promotor, Dirk Aeyels, die op het goede moment ons inspireerde met waardevolle ideeën en daarnaast onze scriptiebegeleider, Jonathan Rogge, voor het interessante onderwerp en het vele overleg. Zonder bepaalde mensen zou de ontwikkeling van de Sonar Turret onmogelijk geweest zijn. Sean Hoyt en Pierre Bureau hielpen het PCB te ontwikkelen en verduidelijkten de KNET-bus, terwijl Bjorn Vandecasteele ons bijstond tijdens de uiteindelijk fabricage van de Sonar Turret. Daarnaast willen we Michiel De Wilde bedanken omdat hij ons uit de deadlock -situatie hielp tijdens de ontwikkeling van de code voor de microcontroller. Toen de noodzaak kwam om onze robots in een nieuwe behuizing te stoppen, stond Kristof’s nonkel, Francky Callewaert, klaar om die te helpen ontwerpen en fabriceren. Zijn neefje en nichtje verlosten tegelijk onze robots van hun naamloosheid. De lijst met mensen die ons inspiratie gaven, maar ons vooral mentaal steunden is te lang om iedereen op te noemen maar in het bijzonder denken we aan Lieve Van den Eeckhout, die het geduld en de volharding had om de volledige scriptie nauwgezet na te lezen. Joke, omdat ze onze video’s wou bewerken, Stijn voor zijn hartmeter en tenslotte Nathalie voor haar interesse en inspiratie. We willen ook zeker onze ouders niet vergeten te bedanken voor de inspanningen die ze moeten leveren en onze familie, omdat ze met ons moet leven. Als laatste willen we vooral elkaar bedanken voor de verhelderende brainstorm-sessies en de inspiratie, maar ook voor de ontspannende badmintonpartijtjes!

i

Toelating tot bruikleen De auteurs geven de toelating deze scriptie voor consultatie beschikbaar te stellen en delen van de scriptie te kopiëren voor persoonlijk gebruik. Elk ander gebruik valt onder de beperkingen van het auteursrecht, in het bijzonder met betrekking tot de verplichting de bron uitdrukkelijk te vermelden bij het aanhalen van resultaten uit deze scriptie.

Datum

Handtekening

ii

Formatievorming in multi-robot systemen door Jan De Beule Kristof Vandoorne Afstudeerwerk ingediend tot het behalen van de academische graad van Burgerlijk Elektrotechnisch Ingenieur Academiejaar 2005–2006 Universiteit Gent Faculteit Ingenieurswetenschappen Vakgroep Elektrische Energie, Systemen en Automatisering Voorzitter: Prof. Dr. ir. Jan Melkebeek Promotor: Prof. Dr. ir. D. Aeyels Scriptiebegeleider: Dr. ir. J. Rogge

Samenvatting Het doel van dit afstudeerwerk was het ontwikkelen van algoritmes om Khepera II -robots eerst in formatie te laten komen en hen daarna deze formatie te laten behouden in een op voorhand onbekende en onvoorspelbare omgeving. Om dit doel te bereiken, dienden echter enkele belangrijke voorbereidende stappen genomen te worden. Zo werd de communicatie tussen de Khepera II -robots onderzocht en werden software-mechanismen ontwikkeld om deze communicatie zo betrouwbaar mogelijk te maken. We denken hierbij aan detectie van verloren gegane boodschappen en retransmissie ervan. Betrouwbare communicatie werd zowel via de High Speed Radio Turret als via de normale Radio Turret verwezenlijkt. Uiteindelijk werd voor de rest van dit onderzoek gebruik gemaakt van de Radio Turret, omdat die het meest gebruiksvriendelijk is. Een tweede voorbereidende stap, was de ontwikkeling van een extensieturret, de Sonar Turret, voor de Khepera II die toelaat om nauwkeurige afstandsmetingen uit te voeren. Hiervoor wordt gebruik gemaakt van SRF05-modules, die ultrasone metingen uitvoeren en zeer eenvoudig aan te sturen zijn. De communicatie tussen de extensieturret en de Khepera II gebeurt door middel van de KNET-bus. Het KNET-busprotocol werd ge¨ımplementeerd op de PIC16F877A, de microcontroller die we gebruiken op de Sonar Turret. Na deze voorbereidende stappen werd overgegaan tot de ontwikkeling van formatievormingsalgoritmes. In een eerste fase werd een algoritme ontwikkeld dat enkel steunt op de IR-sensoren van de Khepera II. Hierbij bleek dat de IR-sensoren van verschillende robots elkaars metingen be¨ınvloeden, waardoor hun sensorwaarden onbetrouwbaar worden. Omdat formatievorming op die manier niet mogelijk is, baseren de algoritmes die daarna ontwikkeld werden zich enkel op metingen met de Sonar Turret. Deze algoritmes laten toe om Khepera II -robots vanuit een willekeurige positie in een voorafbepaalde formatie (driehoek) te laten komen en hen een onbekend terrein te laten verkennen waarbij ze tegelijkertijd obstakels ontwijken. Trefwoorden: formatievorming, multi-robot systeem, Khepera II, ultrasone sensor, inter-robot communicatie

iii

Realization of formations in multi-robot systems Jan De Beule and Kristof Vandoorne Supervisors: Prof. Dr. ir. D. Aeyels, Dr. ir. J. Rogge Abstract— This article describes the realization of formations in multirobot systems. As a part of this research, it has been investigated if reliable communication could be established between different Khepera II-robots via the Radio Turret and the High Speed Radio Turret. Also, a new extension turret with ultrasonic sensors has been designed and created for the Khepera II. With this turret, very precise distance measurements can be carried out. Finally, several algorithms have been developed to realize a triangle formation and explore an unknown terrain, while avoiding obstacles. One of those algoritms is only based on the measurements of the built-in IR sensors of the Khepera II, while the others are based on the measurements of the new extension turret. Keywords— triangle formation, multi-robot systems, Khepera II, interrobot communication, ultrasonic sensor

I. I NTRODUCTION

O

NE of the biggest challenges in robotics is the creation of machines that are capable of interacting with unpredictable surroundings in real-time [1]. The use for this kind of machines is mainly situated in the exploration of unknown1 or dangerous2 terrains that are not (yet) accessible to humans. A secondary challenge is the use of a multi-agent system (MAS), where multiple agents can coexist and cooperate in a common environment. The central idea behind a MAS is that agents can cooperate to solve problems that surpass their individual capacities and knowledge [2]. Several possibilities exist to implement the behaviour of these interacting agents. One is to use one agent as a central coordinating system, which performs the role of master in a master-slave combination, while the other agents are merely slaves to this master. The disadvantage of this configuration is the vulnerability of the system. As the formation (slaves) is totally dependent on the correct functioning of the master, there can be no risk of a failing master for any reason whatsoever. To avoid this vulnerability, each robot is given an equal position in the formation and exhibits the same behaviour. With this, the risk is minimalized that the formation is lost when one of the robots fails. For this research, three Khepera II-robots have been used. These have been designed by K-Team Corporation, that is specialized in the development of mobile minirobots for educative and research purposes. II. C OMMUNICATION The first goal was the establishment of reliable communication between robots. This is done via so-called extension turrets, that can expand the Khepera II’s functions. There are two extension turrets, made by K-Team Corporation, for communication: J. De Beule and K. Vandoorne are both students Electrical Engineering at Ghent University (UGent). Email: [email protected] and [email protected]. 1 exploration expeditions to other planets 2 searching and defusing land mines

The High Speed Radio Turret3 4 • The Radio Turret The first is capable of fast transmission rates, but allows only communication between the robot and a PC. Therefore a control program was designed for the PC that listens to incoming messages from the different robots and broadcasts these messages from one robot to all the others. This control unit was implemented in Java because it allows easy implementation of multiple threads that run at the same time. This was necessary to enable the PC to listen to incoming messages from different robots at the same time. In order to make the communication reliable, every message, sent from a robot to the PC and vice versa, has to be acknowledged with a special ACK-message. During the development of this protocol, some tough problems were encountered, like messages that went bogus for unknown reasons, which raised the question if reliable communication could be established at all and only at the end of the research, the communication via the High Speed Radio Turret was realized. This is the reason why the efforts of establishing communication between the robots were shifted towards the Radio Turret. The High Speed Radio Turret however could still be used to monitor the behaviour of the three robots on the PC. The Radio Turret allows the robots to communicate directly with each other, without an intermediate PC. This made the communication protocol a lot easier to implement. Although the turret itself inhabits a mechanism to detect lost messages and retransmit them, an additional mechanism was implemented, to avoid the occurrence of messages still getting lost. This mechanism, as by the High Speed Radio Turret, forces receivers to send an acknowledgement for every received message. If the acknowledgement doesn’t reach the sender in time, the sender retransmits the message. Every last outgoing and incoming message, together with their serial number, is saved per robot. Combining those two elements leads to an efficient filtering of incoming messages, because each robot can distinguish between new, retransmitted and bogus messages. This makes the communication very reliable and it even allows the implementation of dynamic groups of robots in the future, where robots can join and leave a formation. •

III. S ONAR T URRET The Khepera II has the ability to measure distances with its built-in IR sensors. The disadvantages of those sensors are that they have a very small range (3 cm) and that they cannot be stopped from within the software, running on the robot. This has a big consequence when using a multi-robot system, because the 3 http://ftp.k-team.com/khepera/documentation/KheBTManual.pdf 4 http://ftp.k-team.com/khepera/documentation/RadioTurretManual.pdf

IR sensors from different robots will affect one another (paragraph IV). That’s why an extension turret for the Khepera II has been designed, that has the ability to make distance measurements, using ultrasonic sensors (SRF055 ). A PIC16F877A microcontroller that drives the SRF05-modules, also forms the interface for the Khepera II via the implemented KNET-bus. The ultrasonic sensors have a range of about 2 meters and a resolution of less than a centimeter which make them very precise and the ideal candidate for reliable distance measurements. Nevertheless, improvements have been made to make them even more precise by reducing the sidelobes of the ultrasonic bundle. This was done by putting small tubes, with the interior covered with Velcro, on the ultrasonic sensors. Furthermore a cylinder (figure 1) has been made around the total extension turret which results in an arc when one robot scans another6 . IV. F ORMATION With the achievement of reliable communication, the development of a formation seemed possible by using only the IR sensors. Despite their small range, they have the advantage that they can measure continuously with a refreshment rate of 20 ms. This allows the robots to drive and measure simultaneously, so they can adapt their behaviour and maintain the formation in real-time. It turned out however that the IR sensors of different robots can influence each other when their emitted beams overlap. If this occurs, the robots can no longer rely on their sensor values. The robots go blind, so maintaining a formation is impossible with the built-in IR sensors. The Sonar Turret provides an interesting alternative for the IR sensors, although the ultrasonic sensors can also influence one another when their beams overlap. This problem can be tackled because the ultrasonic sensors can be switched off and the robots can negotiate on whose turn it is to use the Sonar Turret. As a consequence the robots cannot drive and measure at the same time. The biggest advantage of the Sonar Turret is the larger range which opened new opportunities like detection from greater distances. The algorithm to get the robots into a triangle formation leans heavily on this larger range. Initially, the robots are placed randomly in the room, unaware of each anothers position. There’s one condition regarding their initial position; there has to be a line of sight between each of the robots. No obstacle (including another robot) can block their vision. First, they agree on a sequence of using the Sonar Turret. Next, they scan the environment and search for matches in the measured distances of different robots. When a match is detected, the robot will check if the other robot can really be found in that direction by moving towards the other. Then both robots make a new measurement and if the new distances match again, they found each other. Once every robot has found the others, they all move into a triangle. This can be seen in the two right pictures of figure 1. 5 http://www.robot-electronics.co.uk/htm/srf05tech.htm 6 Smallest distance is measured when looking straight at the robot and increasing distances are measured when looking more to the sides.

Fig. 1. (left) Robots before coming into a triangle formation (right) Robots after coming into a triangle formation

After coming in a triangle, two approaches were used to explore the environment, while maintaining the formation. Each approach uses two competitive systems; one regulates the interaction behaviour for maintaining the triangle while the other regulates the autonomous behaviour which gives each robot a goal and makes it possible to avoid obstacles. In the first approach there is one robot leading the triangle and scanning the environment for obstacles. The others have to follow this robot and its decisions about taking the triangle in another direction when an obstacle is present. This one robot acts as a master, so this approach was abandoned for the second approach where all robots have an equal position in the formation. Their interaction behaviour is the same, but their autonomous behaviour can differ. Obstacle avoidance is achieved for every robot individually by changing its autonomous direction in which it was moving. V. C ONCLUSIONS In this article possible alternatives have been described to resolve reliable communication. Accurate distance measurements have been made possible via the designed Sonar Turret. Later on, a MAS was developed in which individual robots are equal and strive together for a complex goal, which was exploring an environment in a triangle formation. ACKNOWLEDGMENTS The authors would like to acknowledge the suggestions of many people, especially prof. dr. ir. Dirk Aeyels and dr. ir. Jonathan Rogge. R EFERENCES [1] Michael J. B. Krieger, Jean-Bernard Billeter, and Laurent Keller, “Ant-like task allocation and recruitment in cooperative robots,” Nature, pp. 992–995, August 2000. [2] Soraya Kouadri Mostéfaoui and Michele Courant, “Collective adaptation of a heterogeneous communicating multi robot system,” in Proceedings of the International Arab Conference on Information Technology, December 2002, pp. 1038–1044, University of Qatar, Doha-Qatar.

Inhoudsopgave 1 Inleiding

1

1.1

Situering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Doel van deze scriptie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Structuur van het werk

4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 Communicatie 2.1

2.2

2.3

2.4

5

Communicatie via de High Speed Radio Turret . . . . . . . . . . . . . . . . . . .

5

2.1.1

Features van de High Speed Radio Turret . . . . . . . . . . . . . . . . . .

5

2.1.2

Uitzicht van de turret . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.1.3

Structuur van de berichten . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.1.4

Controlemechanisme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

2.1.5

De Java-code voor de PC . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.1.6

De C-code voor de robot . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.1.7

Evaluatie van de High Speed Radio Turret

. . . . . . . . . . . . . . . . .

16

Communicatie via de Radio Turret . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2.1

Features van de Radio Turret . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.2.2

Uitzicht van de turret . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.2.3

Eigenschappen van de transmissie . . . . . . . . . . . . . . . . . . . . . .

20

2.2.4

Communicatie tussen de Khepera II en de Radio Turret . . . . . . . . . .

21

2.2.5

Testopstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.2.6

Communicatie in de testopstelling zonder QoS . . . . . . . . . . . . . . .

25

2.2.7

Communicatie in de testopstelling na het inbouwen van QoS . . . . . . .

26

Algemene Communicatiestructuur . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.3.1

Vaste berichtstructuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.3.2

Verpakken van boodschappen . . . . . . . . . . . . . . . . . . . . . . . . .

32

2.3.3

Boodschappen bufferen . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

2.3.4

Evaluatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

Uitbreiden van QoS

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

2.4.1

Werking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

2.4.2

Testopstelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

2.4.3

Ontvangerszijde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

iv

2.5

2.4.4

Zenderzijde . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

2.4.5

ACK-versturend proces . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

2.4.6

Evaluatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

Dynamische groepstructuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45

2.5.1

Voortbouwen op de huidige communicatiestructuur . . . . . . . . . . . . .

45

2.5.2

Aanpassingen aan de communicatiestructuur . . . . . . . . . . . . . . . .

46

3 Sonar Turret

49

3.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.2

SRF05-module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.3

Extensieturret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

3.4

PIC16F877A-microcontroller . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

52

3.5

Het PCB van de Sonar Turret . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.5.1

Aanpassingen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

Code voor de microcontroller . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.6.1

Algemene werking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.6.2

Aandachtspunten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

59

3.6

3.7

Aansturing van de turret vanop de Khepera II

. . . . . . . . . . . . . . . . . . .

61

3.8

Evaluatie van de Sonar Turret . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

3.8.1

Nadelen van de Sonar Turret . . . . . . . . . . . . . . . . . . . . . . . . .

63

Nieuw ontwerp Sonar Turret (Rev. 1) . . . . . . . . . . . . . . . . . . . . . . . .

64

3.9.1

De MAX530 DAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

3.9.2

PCB van de vernieuwde Sonar Turret . . . . . . . . . . . . . . . . . . . .

65

3.9.3

Code voor de microcontroller . . . . . . . . . . . . . . . . . . . . . . . . .

66

3.9.4

Aansturing vanop de Khepera II . . . . . . . . . . . . . . . . . . . . . . .

68

3.9

4 Formatiegedrag met IR-sensoren 4.1

4.2

4.3

4.4

69

De IR-sensoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.1.1

Metingen met de IR-sensoren . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.1.2

Interpretatie van de metingen . . . . . . . . . . . . . . . . . . . . . . . . .

70

Formatievorming: doelstellingen

. . . . . . . . . . . . . . . . . . . . . . . . . . .

71

4.2.1

Doelstellingen 1 en 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

4.2.2

Doelstelling 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

4.2.3

Doelstelling 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

4.2.4

Problemen bij de realisatie van de gezamelijke doelstellingen . . . . . . .

78

Nieuwe aanpak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

4.3.1

Dalende waarden opvangen . . . . . . . . . . . . . . . . . . . . . . . . . .

81

4.3.2

Stijgende waarden opvangen . . . . . . . . . . . . . . . . . . . . . . . . . .

82

4.3.3

Bijkomende problemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

4.3.4

Bijkomende oplossingen . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

Evaluatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

v

5 Formatievorming met de Sonar Turret

87

5.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

5.2

Robots detecteren en formatie vormen . . . . . . . . . . . . . . . . . . . . . . . .

89

5.2.1


89

5.2.2

Praktische implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

5.2.3

Resultaten

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

Formatie behouden met verschillend interactiegedrag . . . . . . . . . . . . . . . .

94

5.3.1


95

5.3.2

Praktische implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

5.3.3

Resultaten

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

98

Formatie behouden met verschillend autonoom gedrag . . . . . . . . . . . . . . .

99

5.4.1


99

5.4.2

Praktische implementatie . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

5.4.3

Resultaten

5.3

5.4

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

6 Conclusies en perspectieven 6.1

6.2

104

Conclusies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.1.1

Communicatie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

6.1.2

Sonar Turret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

6.1.3

Formatievorming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

Perspectieven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

Bibliografie

108

vi

Lijst met afkortingen A/D

Analoog / Digitaal

ACK

ACKnowledgement

ADC

Analoog-naar-Digitaal Converter

bps

bits per second

CPU

Central Processing Unit

CSMA/CD

Carrier Sense Multiple Access with Collision Detection

DAC

Digitaal-naar-Analoog Converter

EMA

Exponential Moving Average

I/O

Input / Output

ID

IDentificatie

IR

InfraRood

LED

Light Emitting Diode

LF

LineFeed

MAS

Multi-Agent System

msg

message

MSG

MeSsaGe

Nr

Nummer | Number

PCB

Printed Circuit Board

QoS

Quality of Service

REQ

Request

SN

SerieNummer

SPI

Serial Peripheral Interface

TDMA

Time Division Multiple Access

uint

unsigned integer

vii

Lijst van figuren 1.1

De Khepera II

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

2.1

Foto en bovenaanzicht van de High Speed Radio Turret . . . . . . . . . . . . . .

6

2.2

De structuur van de ontwikkelde Java-klassen . . . . . . . . . . . . . . . . . . . .

14

2.3

Foto en bovenaanzicht van de radioturret . . . . . . . . . . . . . . . . . . . . . .

19

2.4

Modus- en ID-selector van de Radio Turret . . . . . . . . . . . . . . . . . . . . .

20

2.5

De testopstelling voor de communicatie . . . . . . . . . . . . . . . . . . . . . . .

24

2.6

ACK die verloren gaat als dataverkeer . . . . . . . . . . . . . . . . . . . . . . . .

36

2.7

Proces- en bufferstructuur voor de communicatie . . . . . . . . . . . . . . . . . .

39

2.8

Testopstelling bij uitgebreide QoS . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

2.9

Communicatie via polling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

2.10 Communicatie via een virtual token ring . . . . . . . . . . . . . . . . . . . . . . .

48

3.1

De SRF05-module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

3.2

De KNET-bus met (a) alle turrets in slaaptoestand (b) één turret in actieve toestand 51

3.3

De toestand van de KNET-bus gedurende de communicatie met een slave . . . .

52

3.4

PCB-layout van de Sonar Turret . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

3.5

Khepera II met Sonar Turret (bovenaan), High Speed Radio Turret en Radio Turret (onderaan) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3.6

54

Opmeten van een andere robot in het geval van ideale ultrasone sensoren en behuizing van de robots. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

3.7

Bundelbreedte van SRF05-modules . . . . . . . . . . . . . . . . . . . . . . . . . .

56

3.8

De Sonar Turret met aanpassingen voor nauwkeurige sonarmetingen . . . . . . .

56

3.9

Reflectie van een ultrasone bundel op een schuine muur volgens de wet van de reflectie: θ1 = θ2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

3.10 PCB-layout van de Sonar Turret Rev. 1 . . . . . . . . . . . . . . . . . . . . . . .

66

viii

4.1

IR-sensoren op de robot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

70

4.2

Detecteren van een andere robot . . . . . . . . . . . . . . . . . . . . . . . . . . .

71

4.3

Draairichtingen van de robots . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

4.4

Ontmoeting met verschillende maximale sensor . . . . . . . . . . . . . . . . . . .

74

4.5

Situatie na het draaien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

4.6

Verloop van een zijsensor bij een muur . . . . . . . . . . . . . . . . . . . . . . . .

75

4.7

Sensorwaarden zonder uitmiddeling al draaiend bij een voorwerp . . . . . . . . .

77

4.8

Sensorwaarden met een lopend gemiddelde (i.c. parameter gewicht: 0.0645) . . .

78

4.9

Situatie waarbij sensoren elkaar kunnen be¨ınvloeden . . . . . . . . . . . . . . . .

79

4.10 Situatie waarbij sensoren elkaar niet kunnen be¨ınvloeden . . . . . . . . . . . . . .

80

4.11 Dalende waarden bij de robot . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

4.12 Te grote waarden bij het heropstarten van de robot . . . . . . . . . . . . . . . . .

84

4.13 Langzaam oplopende sensorwaarden . . . . . . . . . . . . . . . . . . . . . . . . .

85

4.14 Bijkomende gevallen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.1

Ontwijkgedrag door robot 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

92

5.2

Laatste stap in de formatievorming . . . . . . . . . . . . . . . . . . . . . . . . . .

93

5.3

(links) Positie voor het uitvoeren van het formatievormingsalgoritme (rechts) Positie na het uitvoeren van het formatievormingsalgoritme . . . . . . . . . . . . . .

5.4

Herpositionering van de tweede robot ten opzichte van de eerste (stilstaande) robot, zodat de gelijkzijdige driehoeksformatie hersteld wordt. . . . . . . . . . . .

5.5

94

98

Draaien van de formatie over 90 graden (de robots in lichtere kleur geven de situatie weer van voor het draaien) . . . . . . . . . . . . . . . . . . . . . . . . . .

99

5.6

Verschillend autonoom gedrag met volledig elk-om-beurt-principe . . . . . . . . . 100

5.7

Verschillend autonoom gedrag met gelijktijdig-bewegen-principe . . . . . . . . . . 101

5.8

Omgeving waarbij robots elkaar kunnen kwijtgeraken . . . . . . . . . . . . . . . . 103

ix

Lijst van tabellen 2.1

De algemene vorm van een bericht . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.2

Ontvangen berichten zonder QoS . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.3

Algemene berichtstructuur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

2.4

Buffer voor inkomende berichten: initiële toestand . . . . . . . . . . . . . . . . .

33

2.5

Buffer voor inkomende berichten: nieuw bericht van robot 3 ontvangen . . . . . .

33

2.6

Circulaire buffer voor ACK’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

2.7

Structuur van een ACK-bericht . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

4.1

Draaitabel voor een robot met 2 sensoren . . . . . . . . . . . . . . . . . . . . . .

73

x

Lijst van algoritmes 2.1

De aangepaste getReply()-functie . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2

De aangepaste sendBytesSyn(byte[] msg)-functie . . . . . . . . . . . . . . . . . .

11

2.3

De messageAvailable()-functie . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

2.4

De run()-functie in de KheperaComm-klasse . . . . . . . . . . . . . . . . . . . . .

13

2.5

De run()-functie in de KheperaSend-klasse . . . . . . . . . . . . . . . . . . . . . .

13

2.6

Het proces dat instaat voor het ontvangen van boodschappen op de robot . . . .

15

2.7

De functie die instaat voor het verzenden van boodschappen op de robot . . . . .

16

2.8

Ontvangerszijde zonder QoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25

2.9

Zenderzijde zonder QoS voor robot 2 . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.10 Ontvangerszijde met QoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

2.11 Zenderzijde met QoS voor robot 3 . . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.12 Zendfunctie met QoS: sendRobot() . . . . . . . . . . . . . . . . . . . . . . . . .

28

2.13 Testprogramma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

2.14 Ontvangerszijde met uitgebreide QoS . . . . . . . . . . . . . . . . . . . . . . . . .

42

2.15 Zendfunctie 2 met uitgebreide QoS: sendAckRobot() . . . . . . . . . . . . . . . .

43

2.16 Het ACK-versturend proces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.1

PIC16F877A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

3.2

De sonar(direction)-functie op de Khepera II

. . . . . . . . . . . . . . . . . . . .

62

3.3

PIC16F877A Rev. 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

67

4.1

Doelstelling 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

4.2

Maximum vinden in real-time: differentieel . . . . . . . . . . . . . . . . . . . . .

76

4.3

Maximum vinden in real-time: tweede methode . . . . . . . . . . . . . . . . . . .

77

4.4

Dalende waarden opvangen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

4.5

Stijgende waarden opvangen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

86

5.1

Algemene werking van het beurtensysteem: algoritme-proces . . . . . . . . . . .

88

xi

5.2

Algemene werking van het beurtensysteem: luister-proces . . . . . . . . . . . . .

xii

88

Hoofdstuk 1

Inleiding Inhoudsopgave

1.1

1.1

Situering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Doel van deze scriptie . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3

Structuur van het werk . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

Situering

Eén van de grootste uitdagingen in de robotica is het creëren van machines die in staat zijn te interageren met onvoorspelbare omgevingen in ware tijd [1]. Toepassingen hiervoor situeren zich voornamelijk in het verkennen van onbekend1 of gevaarlijk2 terrein dat (nog) niet toegankelijk is voor de mens. Een bijkomende uitdaging hierbij is het gebruik van een multi-agent system (MAS), waarbij meerdere agents samenleven en -werken in een gemeenschappelijke omgeving. De centrale idee achter MAS is dat agents samenwerken en op die manier een collectief gedrag kunnen vertonen om problemen op te lossen die boven hun individuele capaciteiten of kennis liggen. Het is dit collectief gedrag dat we zullen onderzoeken. Robotica is een goed domein om MAS te onderzoeken. Robots kunnnen gezien worden als agents met de volgende karakteristieken [2]: • Belichaamd: Robots hebben een fysische behuizing en ervaren de wereld direct. Hun acties maken deel uit van een dynamisch interactiesysteem met de wereld en hebben een onmiddellijke weerslag op de robots zelf. • Gesitueerd: Robots zijn gesitueerd in hun omgeving. Ze werken in het ‘hier’ en ‘nu’ van de omgeving die het gedrag van het systeem direct be¨ınvloedt. • Autonomie: Robots werken zonder de directe interventies van mensen en hebben controle over hun acties en interne toestand. 1 2

bv. verkenningstochten op andere planeten bv. landmijnen opzoeken en onschadelijk maken

1

Hoofdstuk 1. Inleiding

2

Figuur 1.1: De Khepera II

• Mogelijkheid tot sociaal gedrag: De robots kunnen met elkaar communiceren en hebben de mogelijkheid om sociaal gedrag te vertonen om hun doel te bereiken. • Mobiliteit: Robots kunnen zich verplaatsen in de omgeving. • Aanpasbaarheid: Robots kunnen hun individueel of collectief gedrag aanpassen aan nieuwe situaties door hun constante interactie met de omgeving. Er zijn verschillende mogelijkheden om het gedrag van deze interagerende agents te implementeren. Eén mogelijkheid is het centraal coördineren van deze machines in een master-slave combinatie. Een master-robot zal het gedrag regelen van elk van de andere robots, zodat de andere robots zelf niets moeten (kunnen) beslissen. Het nadeel aan deze configuratie is de kwetsbaarheid van het systeem. Aangezien de hele formatie (slaves) valt of staat met de correcte werking van de master, mag er geen enkel risico bestaan dat die niet meer correct zou functioneren om welke reden dan ook. Daarentegen zijn evenwaardige agents veel minder kwetsbaar [3], omdat het wegvallen van één van hen kan opgevangen worden door de anderen. Bovendien zal het ontwerp van de individuele robots eenvoudiger zijn in vergelijking met het systeem van een master waarbij de master alles moet regelen en daardoor heel vlug een complex systeem vereist. Daarom wordt in deze scriptie niet uitgegaan van een master-slave configuratie. We zullen tijdens de formatievorming elke robot een evenwaardige positie geven en proberen hen zoveel mogelijk hetzelfde gedrag te laten vertonen. We willen hiermee het risico dat de formatie verloren gaat bij het uitvallen van één van de robots zo klein mogelijk houden. In dit onderzoek wordt gebruik gemaakt van drie Khepera II -robots. Deze robots werden aangekocht bij het Zwitserse bedrijf K-Team Corporation dat gespecialiseerd is in het ontwikkelen van mobiele minirobots voor educatieve en onderzoeksdoeleinden. De voordelen van de Khepera II -robot (Fig. 1.1) bestaan uit, maar zijn niet beperkt tot de krachtige microcontroller, de kleine afmetingen en de mogelijkheid tot het creëren van sensoren-


3

en actuatoren-extensies3 . Voor elk van de drie robots werd een High Speed Radio Turret [4] aangekocht. Dit is een extensieturret met Bluetooth-module waarmee de Khepera II draadloos geprogrammeerd kan worden. Ook communicatie tussen de robots onderling (via een PC om) behoort tot de mogelijkheden. Deze manier van communiceren wordt in paragraaf 2.1 uitgebreid beschreven. Daarnaast werd dit jaar ook voor elk van de drie robots een Radio Turret [5] aangekocht om rechtstreeks communicatie tussen de robots toe te laten (zonder via de PC om te moeten gaan). Deze manier van communiceren wordt beschreven in paragraaf 2.2. Deze scriptie bouwt verder op het onderzoek van Brecht Senepart [6]. In zijn scriptie wordt de Khepera II -robot uitgebreid besproken en worden enkele algoritmes uitgewerkt met individuele Khepera II -robots.

1.2

Doel van deze scriptie

Het uiteindelijke doel van deze scriptie (of eventueel een volgende), was met de Khepera II -robots formatievormingsalgoritmes uit te testen in de praktijk. In de literatuur is er reeds heel wat te vinden over dit onderwerp; meestal blijft het echter bij theoretische afleidingen van algoritmes en strategieën. De bedoeling was dan ook om hier verandering in te brengen en ons niet zozeer op het theoretische aspect te concentreren, maar zoveel mogelijk algoritmes uit te testen op de robots zelf, om op die manier te ontdekken waar de problemen zich in de praktijk situeren. In referentie [6, sectie 5.2] is te lezen dat de Khepera II -robot ook zijn onvolkomenheden heeft. Zo is het onmogelijk om een precieze absolute positie bij te houden door zich louter te baseren op de metingen van de ingebouwde sensoren van de robot. Absolute positionering houdt in dat de robot op elk moment over zijn coördinaten beschikt in een voorgedefinieerd assenstelsel. De robot zal geprogrammeerd worden met een beginpositie op t = 0 in dit assenstelsel en zijn positie op elk ogenblik t > 0 berekenen aan de hand van de waarden van zijn sensoren (dead reckoning). De ingebouwde sensoren die hiervoor gebruikt kunnen worden, zijn positie-encoders op de wielen van de robot (odometrie). Deze blijken echter onvoldoende nauwkeurig4 om een precieze positionering toe te laten. Daarom wordt in deze scriptie gewerkt met het principe van relatieve positionering. Dit wil zeggen dat elke robot op elk moment zijn positie ten opzichte van de andere robots kent, maar niet zijn absolute positie in de ruimte. De robots beschikken over ingebouwde IR5 -sensoren die deze taak zouden kunnen vervullen, maar die zijn sterk afhankelijk van de reflectiviteit van de oppervlakken waartegen de uitgestuurde IR-bundel geweerkaatst wordt, waardoor ze de exacte afstand tot een obstakel niet kunnen bepalen. Een bijkomend nadeel van deze IR-sensoren is hun beperkte bereik (slechts enkele centimeters). Daarom werd besloten om voor deze scriptie een extensieturret te ontwikkelen voor elk van de robots met daarop ultrasone sensoren om zo de exacte afstand tot obstakels te kunnen meten. 3

http://www.k-team.com/kteam/index.php?site=1&rub=22&page=17&version=EN De sensoren op zich zijn wel nauwkeurig, maar door het doorslippen van de wielen, geven ze geen nauwkeurige meting van de afgelegde afstand. 5 IR = infrarood 4


1.3

4

Structuur van het werk

In hoofdstuk 2 zullen we de communicatieopties bespreken waarover de Khepera II beschikt om met andere Khepera II ’s of de PC te communiceren. Dit hoofdstuk is opgesplitst in twee grote delen, namelijk communicatie via de High Speed Radio Turret en via de Radio Turret enerzijds en algemene communicatiestructuur anderzijds. Voor beide extensieturrets wordt onder andere de berichtstructuur besproken, de mogelijkheid tot foutdetectie en eventuele retransmissie van een verloren gegaan bericht, de transmissiesnelheid enz. In hoofdstuk 3 bespreken we de ontwikkeling van de Sonar Turret. We overlopen zowel het hardwaregedeelte als het softwaregedeelte. Bij de hardware gaan we vooral in op de werking van de gebruikte PIC16F877A-microcontroller en de verschillende ingebouwde modules waarover die beschikt. In het softwaregedeelte gaan we in op het KNET-protocol dat we dienden te implementeren om een communicatiekanaal te kunnen opzetten tussen de Khepera II en de Sonar Turret. Ten slotte maken we ook een evaluatie van het gerealiseerde ontwerp. In hoofdstuk 4 behandelen we het eerste algoritme dat door ons ontwikkeld werd om formatiegedrag te implementeren op de Khepera II. Hierbij werd enkel gewerkt met de ingebouwde IR-sensoren van de Khepera II. In dit hoofdstuk worden de IR-sensoren uitgebreid besproken, alsook de belangrijke nadelen die ze hebben bij het gebruik van meerdere Khepera II ’s in eenzelfde ruimte. In hoofdstuk 5 bespreken we dan enkele formatievormingsalgoritmes die ontwikkeld werden in het kader van dit onderzoek, waarbij enkel gebruik gemaakt werd van de Sonar Turret. Zo bespreken we een algoritme waarmee de robots elkaar kunnen vinden, startend van een willekeurige positie voor elk van de robots. Verder werken we enkele algoritmes uit om de robots in een driehoeksformatie te houden en eventueel zelfs obstakels te ontwijken. In hoofdstuk 6 ten slotte geven we enkele conclusies omtrent het door ons gerealiseerde werk en proberen we al even in de toekomst te kijken.

Hoofdstuk 2

Communicatie Inhoudsopgave 2.1

Communicatie via de High Speed Radio Turret . . . . . . . . . . . . .

5

2.2

Communicatie via de Radio Turret . . . . . . . . . . . . . . . . . . . . .

18

2.3

Algemene Communicatiestructuur . . . . . . . . . . . . . . . . . . . . .

30

2.4

Uitbreiden van QoS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

2.5

Dynamische groepstructuur . . . . . . . . . . . . . . . . . . . . . . . . .

45

In dit hoofdstuk worden de communicatiemogelijkheden tussen de robots besproken. De Khepera II ondersteunt twee manieren van communiceren, waarvoor telkens een extensieturret1 nodig is: • High Speed Radio Turret [4] Deze turret ondersteunt snelle (tot 115200 bps2 ) Bluetoothverbindingen tot een afstand van 30 m tussen robot en PC (tot 7 robots tegelijkertijd). • Radio Turret [5] Deze turret ondersteunt trage (tot 9600 bps) verbindingen tot een afstand van 10 m tussen robots onderling (tot 32 tegelijkertijd) en tussen robot en PC. Beide mogelijkheden werden gebruikt in dit scriptieonderzoek en zullen worden besproken in dit hoofdstuk.

2.1 2.1.1

Communicatie via de High Speed Radio Turret Features van de High Speed Radio Turret

De specificaties van de High Speed Radio Turret zijn de volgende: 1. 2.4 GHz draadloos communicatiekanaal 2. communicatiesnelheid: 38400 bps of 115200 bps 1 2

Het begrip extensieturret wordt in hoofdstuk 3 uitgebreid besproken. bps = bits per second

5

Hoofdstuk 2. Communicatie

6

3. geen kabel meer nodig tussen robot en PC 4. maximaal 7 robots tegelijk verbonden met één PC Er werd voor dit onderzoek in eerste instantie gekozen voor de High Speed Radio Turret omdat deze hogere communicatiesnelheden toelaat. Voor dit soort van communicatie bestond echter nog geen protocol, dus werd er één ontwikkeld in het kader van deze scriptie. Aangezien alle verkeer via de PC om moet, zal op de PC een programma moeten lopen dat luistert naar de verschillende robots en de berichten onderling doorstuurt. De High Speed Radio Turret verschilt van andere extensieturrets omdat deze de RS232 seriële kabel (om de robot te programmeren en data van de robot te loggen) vervangt door een draadloze verbinding. Het seriële kanaal zorgt voor een verbinding tussen de Khepera II en een PC, maar laat geen rechtstreekse communicatie tussen robots onderling toe. Communicatie, bestemd voor andere robots, dient dus via de PC om te gebeuren.

2.1.2

Uitzicht van de turret

Figuur 2.1: Foto en bovenaanzicht van de High Speed Radio Turret

In figuur 2.1 zien we een bovenaanzicht van de High Speed Radio Turret met daarop de volgende onderdelen aangeduid: 1. Dip switches Hiermee kan de modus en het ID van de High Speed Radio Turret geselecteerd worden. 2. Reset knop Heeft dezelfde functie als de resetknop op de Khepera II -robot. 3. De antenne 4. Power LED 5. Connect LED AAN wanneer er een connectie opgezet is tussen de PC en de turret.


7

6. Tx LED AAN wanneer de turret data verstuurt. 7. Rx LED AAN wanneer de turret data ontvangt. 8. Seri¨ ele kabel (S) connector [7, sectie 3.1.4] Modus- en ID-selectie In deze paragraaf verduidelijken we de modus- en ID-selectie bij de High Speed Radio Turret. Hieronder worden de belangrijkste mogelijkheden van deze instelling besproken. Er zijn 4 switches die naar links (waarde 1) of naar rechts (waarde 0) geschoven kunnen worden. • Switch 1 bepaalt de communicatiesnelheid van de turret (waarde 1: 115200 bps, waarde 0: 38400 bps). • Switches 2 tot 4 laten toe om het ID in te stellen van de turret, wat nodig is om verschillende robots te kunnen onderscheiden op de PC.

2.1.3

Structuur van de berichten

Om het protocol zo eenvoudig mogelijk te maken, werd gekozen voor een broadcast-mechanisme. Dit wil zeggen dat, wanneer de robots een bericht versturen naar de PC, de PC ervoor zal zorgen dat dit bericht naar alle andere robots doorgestuurd wordt. Het ontwikkelde protocol bepaalt hoe elk bericht van robot naar PC, en omgekeerd, ingedeeld is. Er bestaan in beide richtingen telkens twee soorten berichten. Er zijn berichten die data bevatten en er zijn berichten die een ACK3 bevatten. Waarom dit zo is, wordt besproken in paragraaf 2.1.4. Data van robot naar PC Elk bericht (met data) dat verstuurd wordt vanop een robot naar de PC bestaat uit de volgende bytes: controlByte

size

func

khepFrom

msgNr

data0

data1

data2

• controlByte We zullen deze byte de waarde 126 geven, zodat de controle-eenheid op de PC hieruit kan besluiten dat dit een bericht is dat nuttige communicatie-informatie bevat, hetzij data voor de andere robots, hetzij een ACK voor een bericht dat de PC naar deze robot gestuurd heeft. Indien deze byte een andere waarde bevat, zal de controleeenheid besluiten dat dit geen geldig communicatiebericht is en zal het bericht dan ook niet broadcasten naar de andere robots. • size Deze byte geeft het totaal aantal bytes weer dat het bericht bevat. 3

ACK = acknowledgement: bericht dat gebruikt wordt om de zendende robot te laten weten dat de boodschap goed ontvangen is.


8

• function Deze byte wordt in dit geval op 0 gezet, omdat het bericht data voor andere robots bevat. • khepFrom Deze byte bevat het ID van de robot die het bericht verzonden heeft. • msgNr Deze byte is nodig voor het controlemechanisme. (zie paragraaf 2.1.4) • data Dit is een array van drie keer vier bytes (dus een totaal van drie keer 32 bits = 96 bits) die data bevat voor de andere robots. ACK van robot naar PC Elk bericht (met een ACK) dat verstuurd wordt vanop een robot naar de PC bestaat uit de volgende bytes: controlByte

size

func

msgNr

• controlByte Deze byte is opnieuw 126 omdat het een communicatie-bericht is. • size Deze byte geeft het totaal aantal bytes weer dat het bericht bevat. • function Deze byte wordt in dit geval op 1 gezet, omdat het bericht een ACK bevat. • msgNr Deze byte geeft aan welk bericht van de PC wordt acknowledged. Data van PC naar robot Voor de communicatie in omgekeerde zin, elk bericht (met data) vanop de PC naar een robot bevat de bytes: controlByte

size

func

khepFrom

msgNr1

msgNr2

msgNr3

data0

data1

data2

• controlByte Deze byte is opnieuw 126 omdat het een communicatie-bericht is. • size Deze byte geeft het totaal aantal bytes weer dat het bericht bevat. • function Deze byte wordt in dit geval op 0 gezet, omdat het bericht data voor andere robots bevat. • khepFrom Deze byte bevat het ID van de robot die het bericht verzonden heeft. • msgNr1 Deze byte is nodig voor het controlemechanisme. (zie paragraaf 2.1.4) • msgNr2 Extra byte voor het controlemechanisme • msgNr3 Extra byte voor het controlemechanisme • data Dit is een array van drie keer vier bytes die de data bevat van een andere robot.


9

ACK van PC naar robot Elk bericht (met een ACK) dat verstuurd wordt vanop de PC naar een robot bestaat uit de volgende bytes: controlByte

size

func

msgNr

• controlByte Deze byte is opnieuw 126 omdat het een communicatie-bericht is. • size Deze byte geeft het totaal aantal bytes weer dat het bericht bevat. • function Deze byte wordt in dit geval op 1 gezet omdat het bericht een ACK bevat. • msgNr Deze byte geeft aan welk bericht van deze robot wordt acknowledged.

2.1.4

Controlemechanisme

Er werd ook een controlemechanisme voorzien dat ervoor zorgt dat alle berichten die verstuurd worden vanop de PC ook daadwerkelijk aankomen op de robot en omgekeerd. Het programma dat op de robot loopt, bestaat namelijk uit verschillende processen die verondersteld worden parallel te werken. De robot beschikt echter maar over één processor zodat de processen slechts elk om beurt voor een bepaalde tijdsspanne de processor kunnen gebruiken. Hierdoor kan het gebeuren dat het proces dat luistert naar berichten afkomstig van de PC toch zo’n bericht mist, omdat hij op dat moment de processor niet voor zich heeft en het bericht dus niet kan verwerken. Daarnaast kan het gebeuren dat er al een volgend bericht verstuurd werd, terwijl het vorige nog niet verwerkt was, zodat het nieuwe bericht verloren gaat. Om deze problemen op te vangen werd een controlemechanisme ge¨ımplementeerd. Wanneer de PC een databericht verstuurt naar een robot, stuurt hij naast de data ook drie keer het berichtnummer4 mee. Wanneer de robot nu een databericht ontvangt, zal hij eerst controleren of de drie berichtnummers dezelfde zijn en zal, in het geval dat dit zo is, een ACKbericht sturen naar de PC. Het programma op de PC is zo geschreven dat de PC slechts een nieuw databericht naar de robot kan sturen wanneer hij het juiste ACK-bericht (van het vorig verstuurde databericht) heeft ontvangen. Hierbij is ook een time-out-mechanisme ingebouwd dat ervoor zorgt dat de PC niet blijft wachten op een ACK, maar na een bepaalde tijd (100 ms) het databericht opnieuw doorstuurt naar de robot. Hierdoor weet de PC dat, wanneer hij een nieuw databericht probeert te versturen, het vorige zeker ontvangen is. Voor de databerichten van robot naar PC is een soortgelijk mechanisme aanwezig. Ook hier werd vastgesteld dat sommige berichten van de robot verloren gingen. Daarom wordt met elk databericht vanop de robot ook een berichtnummer meegestuurd en zal elk databericht acknowledged moeten worden door de PC. 4

Dit berichtnummer is 1 bij het eerste databericht en incrementeert elke keer er een databericht wordt verstuurd vanop de PC.


2.1.5

10

De Java-code voor de PC

De robots communiceren met de PC over een draadloos kanaal. Via een Bluetooth-dongle komt het signaal binnen op de PC. Deze dongle laat toe om een seriële poort te emuleren zodat het voor de PC lijkt alsof de robots via een seriële poort met de computer verbonden zijn. Elke robot zal een verschillende (virtuele) COM-poort toegewezen krijgen naargelang het ID dat ingesteld staat op de turret (zie paragraaf 2.1.2). Voor het aansturen van deze poorten, maken we gebruik van de Khepera-klasse (geschreven in Java) uit het JKhepera-package dat beschreven staat in referentie [8]. We zullen de aanpassingen die we maakten aan deze klasse in de volgende paragraaf kort beschrijven. In de paragrafen die daarop volgen, bespreken we bijkomende klassen die volledig ontwikkeld werden in het kader van dit onderzoek. De Khepera-klasse Eerst werd de functie getReply() aangepast om de specifieke berichten uit het nieuw ontwikkelde protocol te kunnen ontvangen. Deze functie was oorspronkelijk geschreven om standaardberichten van een Khepera-robot te ontvangen. Deze berichten eindigen altijd met een linefeed (een byte die het getal 10 voorstelt), zodat deze berichten gelezen werden in een while()-lus totdat de linefeed ontdekt werd. Voor de berichten uit het ontwikkelde protocol was dit echter niet mogelijk omdat het getal 10 meerdere keren kan voorkomen in één bericht. Daarom wordt nu eerst gecontroleerd of de eerste ingelezen byte gelijk is aan 1265 en indien dit zo is, wordt het aantal bytes ingelezen dat te vinden is in de tweede ingelezen byte. Indien de eerste byte niet 126 is, worden bytes ingelezen tot een linefeed ontdekt wordt. Dit algoritme staat in pseudo-code beschreven onder Algoritme 2.1. Algoritme 2.1 De aangepaste getReply()-functie 1: b = incoming byte 2: add b to reply 3: if (b == 126) then 4: size = incoming byte 5: add size to reply 6: for (0 ≤ i < (size − 2)) do 7: b = incoming byte 8: add b to reply 9: end for 10: else 11: while (b 6= LF ) do 12: b = incoming byte 13: add b to reply 14: end while 15: end if 16: return reply

Het probleem met seriële poorten is dat er niet gelijktijdig van gelezen en naar geschreven kan worden. Daarom werd een algoritme ontwikkeld waarbij het schrijven altijd voorrang krijgt 5

Waarbij we mogen veronderstellen dat een standaard-bericht nooit met 126 begint.


11

op het lezen en waarbij het lezen onderbroken wordt wanneer er geschreven moet worden. De functie sendBytesSyn(byte[] msg) implementeert dit algoritme. Deze functie wordt gebruik om vanop de PC berichten te versturen naar een robot. We zullen nu de code in deze functies kort overlopen (zie ook Algoritme 2.2). De eerste while()-lus wacht tot vorige schrijfoperaties afgelopen zijn. Aangezien alle zenden ontvangstfuncties van het synchronized6 -type zijn, moeten we hier gebruik maken van de wait()-functie die andere synchronized functies toelaat om de variabele writingBusy aan te passen. Wanneer deze variabele op 1 staat, kan er enkel één bericht verstuurd worden naar de robot en zal er niet meer geluisterd worden naar inkomende berichten. De volgende while()-lus wacht tot de thread die luistert naar deze robot, gepauzeerd is. Vervolgens kan het bericht verzonden worden. Om het controlemechanisme (zie 2.1.4) te implementeren, worden eerst nog drie extra bytes ingevoegd die het berichtnummer bevatten. Tenslotte wacht de functie op een ACK van de robot en indien een time-out optreedt of de ACK niet overeenkomt met het verstuurde berichtnummer, wordt het bericht herverzonden. Algoritme 2.2 De aangepaste sendBytesSyn(byte[] msg)-functie 1: while (other threads are sending to this robot) do 2: wait() 3: end while 4: while (thread is listening to this robot) do 5: wait() 6: end while 7: msgN r + + 8: compose message msg with msgN r in it 9: sendBytes(msg); 10: let thread start listening again to this robot 11: while !(correct ACK received from robot) do 12: wait(100) 13: if (time-out occurred) then 14: sendBytes(msg) 15: end if 16: end while De functie messageAvailable() controleert of er een zendfunctie een aanvraag voor de COM-poort gedaan heeft. Indien dit zo is, zal deze functie niet meer luisteren naar deze COMpoort, maar aan de zendfunctie duidelijk maken dat de COM-poort vrij is om te zenden (m.b.v. de notifyAll()-functie die andere synchronized functies toelaat om de variabele writingBusy te controleren). Indien er geen aanvraag is, zal de messageAvailable()-functie (zie Algoritme 2.3) controleren of er een bericht ontvangen is via de getReply()-functie. De functie sendAck(int mesNr) ten slotte stuurt een ACK-bericht naar de robot zoals beschreven in paragraaf 2.1.4. Eerst wordt het bericht opgebouwd zoals voorgeschreven in het ontwikkelde protocol en wanneer de COM-poort vrij komt, wordt het bericht verzonden (analoog aan Algoritme 2.2, maar hierbij wordt op het einde niet meer gewacht op een ACK van de robot). 6

Voor meer informatie omtrent gesynchroniseerde threads en threads in Java in het algemeen, verwijzen we naar http://java.sun.com/docs/books/tutorial/essential/threads/index.html


12

Algoritme 2.3 De messageAvailable()-functie 1: returnV alue = 0 2: if (other thread wants to send to robot) then 3: notifyAll() 4: else 5: if (message is incoming) then 6: returnV alue = 1 7: end if 8: end if 9: return returnV alue De KheperaComm-klasse Elk KheperaComm-object komt overeen met één specifieke robot en dit object zal voordurend controleren op nieuwe berichten van deze robot. De KheperaComm-klasse stamt af van de Thread-klasse (standaard klasse uit Java). Threads zijn processen die parallel naast elkaar kunnen lopen op een processor (de CPU van de PC in dit geval). In elke KheperaCommthread wordt er naar één specifieke robot geluisterd en een ontvangen bericht zal, indien nodig, doorgestuurd worden naar de andere robots (via de KheperaSend-klasse). Omdat het luisteren naar een robot ondergeschikt is aan het zenden naar een robot, controleert de run()-functie7 voortdurend (via de messageAvailable()-functie uit Algoritme 2.3) of er ergens (in andere threads) een zendfunctie naar deze robot opgeroepen werd en in dat geval zal de messageAvailable()-functie het luisteren onderbreken totdat de data verzonden is (de pseudo-code is te vinden onder Algoritme 2.4). De KheperaSend-klasse Ook de KheperaSend-klasse stamt af van de Thread-klasse. Voor elk ontvangen bericht in een KheperaComm-object, wordt dus een nieuw KheperaSend-object aangemaakt en opgestart (run()-functie). Bij het verzenden (via de sendBytesSyn()-functie uit de Khepera-klasse) zijn er twee mogelijkheden. Indien het KheperaComm-object het bericht al ontvangen had (sendAckOnly == true), zal hij enkel nog een ACK (via de sendAck()-functie uit de Kheperaklasse) doorsturen. Dit is nodig wanneer de acknowledgment die reeds verstuurd werd, verloren is gegaan. Indien het KheperaComm-object het bericht nog niet ontvangen had, zal het KheperaSend-object eerst het bericht naar alle andere robots doorsturen en pas dan een ACK sturen naar de robot die bij het KheperaComm-object hoort (Algoritme 2.5). De KheperaPC-klasse De main(String[] args)-functie van de KheperaPC-klasse begint met het openen van de verschillende seriële poorten waarop een Khepera II is aangesloten. Omdat deze poortnummers van PC tot PC kunnen verschillen, worden ze meegeven als argument bij het opstarten van het programma. Vervolgens zal er voor elk Khepera-object ook een KheperaComm-thread opgestart 7

deze functie wordt gestart wanneer een thread van de klasse KheperaComm start


13

Algoritme 2.4 De run()-functie in de KheperaComm-klasse 1: loop 2: while (messageAvailable() ≤ 0) do 3: sleep(50) 4: end while 5: read message msg 6: controlByte = msg[0] 7: if (controlByte 6= 126) then 8: jump to line 1 and wait for next message 9: else 10: if (msg[2] == 0) then 11: khepF rom = msg[3] 12: msgN r = msg[4] 13: if (new message) then 14: start new KheperaSend-thread to broadcast the received message and send ack to robot 15: else 16: start new KheperaSend-thread, but only to send ack to robot 17: end if 18: else if (msg[2] == 1) then 19: msgN r = msg[3] 20: setAckReceived(true,msgN r) 21: end if 22: end if 23: end loop

Algoritme 2.5 De run()-functie in de KheperaSend-klasse 1: if !(only send ack) then 2: for (0 ≤ i < Number of Kheperas) do 3: if (i 6= own ID) then 4: send message to Khepera with ID i 5: end if 6: end for 7: end if 8: send ACK for this message to Khepera with own ID


14

Figuur 2.2: De structuur van de ontwikkelde Java-klassen

worden. Tot slot wacht het programma totdat de gebruiker het programma wenst af te sluiten en het sluit dan de verschillende seriële poorten. Een voorbeeld van hoe alle hierboven beschreven klassen samenwerken en de communicatie verzorgen tussen de robot 1 en robot 2 is te zien in figuur 2.2. De Java-code voor de communicatie via de High Speed Radio Turret is te vinden op de bijgeleverde CD in de map Communicatie\High Speed Radio Turret\Java-code”. ”

2.1.6

De C-code voor de robot

Data ontvangen Het proces op de robot dat inkomende berichten detecteert (Algoritme 2.6), controleert voortdurend de ontvangstbuffer op een ontvangen byte8 en indien er een byte gedetecteerd wordt, worden de volgende ontvangen bytes in de juiste volgorde (zie paragraaf 2.1.4) naar juiste variabelen geschreven. Wanneer het volledige bericht ontvangen is, worden de drie ontvangen berichtnummers vergeleken met elkaar en indien ze dezelfde zijn, wordt een ACK-bericht verzonden naar de PC. 8

m.b.v. de ingebouwde functie ser receive byte()


Algoritme 2.6 Het proces dat instaat voor het ontvangen van boodschappen op de robot 1: loop 2: while !(incoming byte) do 3: read buffer 4: end while 5: controlByte = incoming byte 6: if (controlByte == 126) then 7: while !(incoming byte) do 8: read buffer 9: end while 10: sizeBuf f er = incoming byte 11: for (0 ≤ i < sizeBuf f er − 2) do 12: while !(incoming byte) do 13: read buffer 14: end while 15: msgBuf f er[i] = incoming byte 16: end for 17: if (msgBuf f er[0] == 0) then 18: robotN rSndr = msgBuf f er[1] 19: msgN r1 = msgBuf f er[2] 20: msgN r2 = msgBuf f er[3] 21: msgN r3 = msgBuf f er[4] 22: save real data from received message 23: if (msgN r1 == msgN r2) AND (msgN r2 == msgN r3) then 24: sendAck(msgN r1) 25: if (msgN r1 > msgN rP rev) then 26: msgN rP rev = msgN r1 27: process message 28: end if 29: end if 30: else if (msgBuf f er[0] == 1) then 31: msgN r1 = msgBuf f er[1] 32: ackReceived = msgN r1 33: end if 34: else 35: receive message (read till linefeed) and discard it 36: end if 37: end loop

15


16

Data versturen Door het oproepen van de sendRobot()-functie (Algoritme 2.7), zal data verstuurd worden naar alle andere robots via het broadcast-mechanisme op de PC. Eerst wordt het bericht opgebouwd zoals we besproken hebben in paragraaf 2.1.4. Vervolgens wordt het volledige bericht als bytearray verzonden met de ingebouwde functie ser_send_buffer(). Ten slotte wordt er gewacht op een ACK van de PC, die aangeeft dat het bericht correct9 naar alle andere robots is verstuurd. Algoritme 2.7 De functie die instaat voor het verzenden van boodschappen op de robot 1: buf f er[0] = 126 2: buf f er[1] = size of message 3: buf f er[2] = 0 4: buf f er[3] = own ID 5: buf f er[4] = msgN r 6: msgN r + + 7: convert 3 uint32’s (data0, data1, data2) to byte-array data[] 8: save data[] in buf f er[] 9: com reserve channel() 10: com send buffer(buf f er, buf f er[1]) 11: com release channel() 12: while !(correct ack received) do 13: if (time-out occurred) then 14: com reserve channel() 15: com send buffer(buf f er, buf f er[1]) 16: com release channel() 17: end if 18: end while De C-code voor de communicatie via de High Speed Radio Turret is te vinden op de bijgeleverde CD in de map Communicatie\High Speed Radio Turret\C-code”. ”

2.1.7

Evaluatie van de High Speed Radio Turret

Het communicatieprotocol voor de High Speed Radio Turret werd ontwikkeld in het begin van deze scriptie . Betrouwbare communicatie tussen de robots via de PC om werd echter pas in de eindfase van dit onderzoek gerealiseerd. Het perfect betrouwbaar10 maken van deze communicatie hield het optimaliseren in van heel wat parameters (bv. de tijd die we inbouwen voor een time-out optreedt en een boodschap opnieuw verstuurd wordt). Aangezien ons de tijd ontbrak om dit iteratief proces te vervolledigen, werd besloten om de Radio Turret aan te schaffen voor de Khepera II ’s. De Radio Turret ondersteunt rechtstreekse communicatie tussen robots en dus was het implementeren van een communicatieprotocol voor deze turret een stuk eenvoudiger. We bespreken deze vorm van communicatie in paragraaf 2.2. Zoals reeds hierboven vermeld, werd uiteindelijk toch betrouwbare communicatie gerealiseerd 9

Dit houdt in dat de verzonden berichten vanop de PC ook acknowledged zijn door de individuele robots. Dit houdt in dat boodschappen met voldoende hoge snelheid verzonden moeten kunnen worden en dat zelfs bij druk dataverkeer elke robot ervan verzekerd moet kunnen zijn dat alle andere robots zijn boodschappen ontvangen. 10


17

via de High Speed Radio Turret, omdat er op het einde van deze scriptie nog tijd restte om de parameters alsnog te optimaliseren. Een groot nadeel echter aan het gebruik van de High Speed Radio Turret als communicatiekanaal tussen de robots is het feit dat er geen printf()-statements11 meer mogen voorkomen in de rest van de code op de Khepera II. Deze informatie ontvingen we van K-Team Corporation zonder verdere uitleg. We weten dan ook niet wat de precieze reden hiervoor is. De informatie waarover we beschikken is dat de printf()-boodschappen over hetzelfde kanaal verstuurd worden als de communicatieboodschappen die we versturen. Verder weten we ook dat een printf()-boodschap heel wat tijd in beslag neemt om te versturen over dit kanaal. Toch vinden we het onbegrijpelijk dat communicatie via de High Speed Radio Turret de printf()-statements uitsluit.

11

Deze functie wordt gebruikt om gegevens van de robot te kunnen loggen op een PC.


2.2

18

Communicatie via de Radio Turret

2.2.1

Features van de Radio Turret

De specificaties van de Radio Turret zijn de volgende: 1. Inter-robot communicatie tussen maximaal 32 robots. De beperking tot 32 robots wordt verduidelijkt in paragraaf 2.2.2. 2. Foutdetectie en -correctie. 3. Een bereik tot 10 meter. 4. Een transmissiesnelheid van maximaal 9600 bps. Deze snelheid is echter afhankelijk van de grootte van de berichten en daarom wordt er een typische waarde van 4800 bps opgegeven. De reden hiervoor wordt verduidelijkt in paragraaf 2.2.3. 5. Twee operationele modes: als bijkomend communicatiekanaal of als hoofdkanaal waarbij deze laatste modus de mogelijkheid biedt tot communicatie met een PC. Punt 5 verdient enige bijkomende uitleg. De Radio Turret kan op twee verschillende manieren gebruikt worden [5, sectie 4.2]: • Main Communication Channel : In dit geval dienen we ook over een basisstation (de Radio Base [9]) te beschikken. Alle boodschappen die de robots naar elkaar versturen, zullen dan via het basisstation hun bestemming bereiken. Indien dit station verbonden is met een computer, kan al het verkeer ook geanalyseerd worden op de computer. Er is nog een tweede implicatie. Standaard gebeurt de communicatie tussen robot en PC immers via het S seriële kanaal. Dit kan zowel via de High Speed Radio Turret (paragraaf 2.1) als via de S seriële kabel. Met de Radio Turrets ingesteld als Main Communication Channel nemen zij deze taak over en zal bijvoorbeeld het inladen van programma’s via het basisstation en de turrets verlopen. • Extensieturret : In dit geval wordt de Radio Turret gebruikt als een extensieturret. De communicatie tussen de robots verloopt nu enkel via hun Radio Turrets zonder dat een pc of basisstation tussenkomt. Elke robot kan alle andere robots die zich binnen het bereik (10 m) van de Radio Turret bevinden, individueel aanspreken. In paragraaf 2.2.2 zullen de details van de Radio Turret besproken worden. We hebben ervoor gekozen om in het kader van deze scriptie de turrets als gewone extensieturrets te gebruiken, zodat de optie wegviel om het verkeer te monitoren 12 via de Radio Base. Dit was geen handicap, omdat het communicatieverkeer via de Radio Turrets, indien nodig, steeds te monitoren was via de S seriële kabel (en TeraTerm Pro) of via de High Speed Radio Turret op elk van de robots. Het sluit zelfs dichter aan bij de doelstelling van het onderzoek, omdat deze stelt dat de robots als onafhankelijke eenheden moeten opereren en een centrale eenheid 12

Observeren vanop een PC.


19

zoals de Radio Base of PC dus best vermeden wordt. Bij het falen van het basisstation zou de communicatie tussen de robots volledig wegvallen, wat meteen de kwetsbaarheid van de eerste configuratie aantoont.

2.2.2

Uitzicht van de turret

Sommige functies zoals retransmissie en detectie van verloren boodschappen worden gevisualiseerd op de radioturret [5, sectie 4.1] via LED’s.

Figuur 2.3: Foto en bovenaanzicht van de radioturret

In figuur 2.3 zien we een bovenaanzicht van de Radio Turret met daarop aangeduid de volgende onderdelen: 1. Reset knop Deze heeft dezelfde functie als de resetknop op de Khepera II -robot. 2. De antenne 3. Rx LED AAN wanneer de turret klaar is om data te ontvangen . 4. Tx LED AAN wanneer de turret data verstuurt. 5. Channel active AAN wanneer de turret een actief radiokanaal heeft gedetecteerd. 6. Seri¨ ele kabel (S) connector 7. Dip switches Hiermee kan de modus en het ID van de robot geselecteerd worden 8. Repeat data LED AAN wanneer er data verloren is gegaan (retransmissie van het bericht). 9. Lost data LED AAN wanneer de data 10 keer herverzonden werd zonder succes (geen ACK ontvangen) en het bericht dus als verloren wordt beschouwd. Deze LED is rood van kleur in tegenstelling tot de andere LED’s, die groen zijn.


20

Modus- en ID-selectie In deze paragraaf verduidelijken we de modus- en ID-selectie. Deze instelling van de Radio Turret gebeurt via de switches die te zien zijn in figuur 2.3 (nummer 7). Figuur 2.4 toont hiervan een uitvergroting. Hieronder worden de belangrijkste mogelijkheden van deze instelling besproken. Er zijn 8 switches die naar boven (waarde 1) of naar onder (waarde 0) geschoven kunnen worden. • Switches 1 tot 5 laten toe om het ID (5 bits = maximaal13 32) in te stellen van de robot. • Switch 6 bepaalt of de Radio Turret als extensieturret gebruikt wordt (waarde 0) of als Main Communication Channel (waarde 1). Zoals besproken in sectie 2.2.1, wordt in dit onderzoek altijd voor de eerste optie gekozen: deze switch zal dus altijd op nul moeten staan. • Switches 7 en 8 hebben geen betekenis, maar staan standaard op nul. Op figuur 2.4 zien we dat ID 4 werd gekozen en dat de turret als een extensieturret gebruikt wordt.

Figuur 2.4: Modus- en ID-selector van de Radio Turret

2.2.3

Eigenschappen van de transmissie

Het kanaal is half duplex wat wil zeggen dat er niet tegelijk verzonden en ontvangen kan worden. De turret zal zich standaard in de ontvangst-toestand bevinden, waarbij de turret zal wachten op binnenkomende boodschappen. Enkel wanneer er data moet verzonden worden, zal de turret overschakelen op de zend-toestand. De toestand van de Radio Turret wordt gevisualiseerd via de Rx LED en de Tx LED, zichtbaar in figuur 2.3 met de nummers 3 en 4. Data wordt automatisch verpakt in berichten en die bevatten: • informatie over het type bericht 13 Indien gebruik wordt gemaakt van de Radio Base-eenheid, heeft deze altijd ID 0, zodat in dat geval nog slechts 31 robots gebruikt kunnen worden om te communiceren.


21

• het ID van de zender • het ID van de gewenste ontvanger • lengte van de data • een checksum voor foutcorrectie Deze informatie vormt de header van het bericht en bevat de noodzakelijke gegevens om de eigenlijke data foutloos bij de gewenste robot te bezorgen. De ontvanger stuurt een ACK als de boodschap goed ontvangen is. Enkel wanneer de zender deze ACK ontvangt, beschouwt hij de boodschap als correct verstuurd. Als na een zekere tijd (enkele milliseconden) geen ACK ontvangen wordt voor een verzonden bericht, dan beschouwt de zender het bericht als verloren en genereert hij een time-out. Hierop zal hij het bericht opnieuw versturen en tegelijk de Repeat data LED aanzetten. Deze cyclus van time-out en retransmissie wordt, indien nodig, tot 10 keer herhaald, waarna de boodschap als definitief verloren beschouwd wordt. In dit laatste geval zal de Lost data LED aanstaan. De data-encapsulatie en het transmissieprotocol voegen een niet te verwaarlozen vertraging toe aan het dataverkeer. Dit is echter noodzakelijk om alles correct te laten verlopen. Een bericht bestaat naast de header altijd uit 16 bytes pure data. Als die niet allemaal opgevuld worden, zal de nuttige informatie van het bericht kleiner zijn. De berichten blijven even lang, zodat de vertraging en de hoeveelheid toegevoegde informatie dezelfde blijft, ongeacht het aantal nuttige data-bytes dat de gebruiker wil verzenden. Om de transmissiesnelheid optimaal te benutten, is het dus beter om de pure data volledig op te vullen tot 16 bytes. Dit verklaart het verschil tussen de maximale en de typisch haalbare transmissiesnelheid, die we reeds bespraken in paragraaf 2.2.1. Een transmissiesnelheid van 9600 bps is enkel haalbaar als alle boodschappen maximaal (16 bytes) opgevuld zijn. Wanneer dit niet het geval is, zal de transmissiesnelheid lager liggen. In dit laatste geval blijft de overhead per boodschap hetzelfde, maar ligt de nuttige hoeveelheid getransfereerde informatie lager en bijgevolg ook de nuttige datatransmissiesnelheid.

2.2.4

Communicatie tussen de Khepera II en de Radio Turret

De communicatie tussen de robot en de Radio Turret heeft net als bij de Sonar Turret (zie ook paragraaf 3.3) een master-slave karakter. De robot initiëert alle communicatie. Hij vraagt de status en de inhoud van de ontvangstbuffer op van de Radio Turret en stuurt zelf een boodschap naar de zendbuffer van de Radio Turret. Bij dit laatste zal de turret de boodschap onmiddellijk versturen, onafhankelijk van het reeds verstuurd zijn van de vorige boodschap. Het zou kunnen dat de turret nog volop de boodschap uit zijn zendbuffer aan het versturen is als de robot alweer een nieuwe boodschap in die zendbuffer duwt. Dit kan de communicatie onbetrouwbaar maken en moet dus vermeden worden. Dit kan door eerst de status van de Radio Turret te controleren voor een bericht verstuurd wordt. De communicatie tussen de Khepera II en de Radio Turret gebeurt met behulp van de MSG-module14 , die ingebouwd is in de BIOS van de robot [10, sectie MSG]. Het master-slave 14 De MSG-module maakt gebruik van het KNET-protocol om te communiceren met extensieturrets. Dit KNET-protocol wordt uitgebreid beschreven in hoofdstuk 3.


22

karakter houdt in dat de robot enkel commando’s kan sturen naar de turret en dat de turret pas informatie zal terugsturen wanneer de robot erom vraagt. Dit gebeurt via de functie msg_snd_rec_message(msgS, sizeS, msgR, sizeR, rep) waarbij de verschillende argumenten duiden op: • msgS Een pointer naar het begin van de byte-array met data die de robot naar de turret wil sturen. • sizeS De grootte van de boodschap. • msgR Een pointer naar het begin van de byte-array waarin het antwoord zal terechtkomen dat de turret terugstuurt. • sizeR De grootte van het antwoord. • rep Aantal keer dat de robot zal herproberen als er een fout optreedt. Structuur van het bericht voor de Radio Turret De algemene structuur van een bericht voor de MSG-module is te zien in tabel 2.1. De eerste twee bytes vormen de MSG-header. De eerste byte daarvan bevat het ID van de Radio Turret waarnaar een boodschap verstuurd moet worden en de tweede byte de lengte van die boodschap. Het ID van de Radio Turret is 4 (dit ID werd in de hardware van de Radio Turret geprogrammeerd) en de lengte is afhankelijk van het bericht. Het ID van de Radio Turret mag niet verward worden met het ID van de robot dat ingesteld kan worden via de ID-selector (paragraaf 2.2.2). Het eerste is intern, opdat de Khepera II een onderscheid zou kunnen maken tussen de verschillende extensieturrets. Het laatste is enkel voor de communicatie, opdat de robots zich zouden kunnen onderscheiden van elkaar. Tabel 2.1: De algemene vorm van een bericht

Turret ID

lengte

byte 1

byte 2

...

byte n

Het tweede deel van de boodschap (rechts van de dubbele streep in tabel 2.1) is het turretafhankelijke deel. De eerste byte van een boodschap van de robot bevat het commando en wordt voorgesteld door het ascii-karakter dat overeenkomt met deze eerste byte. De eerste byte van het bijhorende antwoord van de turret zal altijd het corresponderende kleine karakter zijn. De eventuele bytes die daarna verstuurd worden tussen de robot en de turret, bevatten parameters voor het gebruikte commando. Gebruikte commando’s voor de Radio Turret Voor deze scriptie zijn slechts vier commando’s belangrijk en die zullen we nu bespreken. Bij elk commando vormen de eerste twee bytes de header (gescheiden door een dubbele streep zoals in tabel 2.1). In het antwoord is geen header aanwezig.


23

• Opvragen van het ID – commando 4

1

c

– antwoord c

eigen ID

Het ’c’-commando vraagt het ID aan van de robot (eigen ID). Dit kan ingesteld worden via de ID-selector bovenop de Radio Turret. Als enige commando van de vier gebruikt deze voor commando en antwoord een kleine letter. • Versturen van een boodschap (De bytes met pure data worden van de rest van de boodschap gescheiden door een driedubbele streep, waarbij de grootte van dit blok nuttige bytes vervat zit in de byte (size) links van deze driedubbele streep (zie ook paragraaf 2.2.3).) – commando 4

19

S

dest ID

size

byte 1

byte 2

...

byte 15

byte 16

– antwoord s Het berichtonderdeel dat specifiek is voor de Radio Turret (na de dubbele streep) bevat het commando (S ), het ID van de Radio Turret (dest ID) waarnaar gestuurd wordt en het aantal nuttige bytes (size) in het bericht. Dit commando stuurt een boodschap naar de zendbuffer van de Radio Turret, die op zijn beurt laat weten of de boodschap succesvol geschreven is in de zendbuffer via het terugsturen van een kleine ’s’. Dit wil niet zeggen dat de boodschap correct verstuurd is naar de doelrobot. Om dat te controleren, moet de statusbyte van de Radio Turret opgevraagd worden. Dit commando initieert een duidelijke fire-and-forget actie. • Opvragen van de ontvangstbuffer – commando 4

1

R

– antwoord r

source ID

size

byte 1

byte 2

...

byte 15

byte 16

Hiermee vraagt de robot de ontvangstbuffer aan van de Radio Turret. Die bevat, naast het ID van de robot die de boodschap stuurde (source ID), ook de nuttige lengte (size) van de boodschap. • Opvragen van de status – commando 4

1

F

– antwoord f

status


24

Het antwoord bevat de 8-bit status van de robot, waarbij de bits de volgende betekenis hebben. – bit 0 (minst significante bit) is 1 als de zendbuffer leeg is en de Radio Turret klaar is om een nieuwe boodschap te verzenden. – bit 1 is 1 wanneer een nieuwe boodschap in de ontvangstbuffer zit. – bit 2 is 1 wanneer de boodschap 10 keer zonder succes verstuurd werd en zodanig als verloren beschouwd wordt. Deze bit wordt ook op nul gezet wanneer een nieuw bericht in de zendbuffer terechtkomt. – bit 3 - 7 Geen betekenis. Via de eerste drie bits kan er dus een zekere kwaliteitsgarantie in de communicatie ingebouwd worden. Dit wordt beschreven in paragraaf 2.2.7.

2.2.5

Testopstelling

Figuur 2.5: De testopstelling voor de communicatie

De communicatie moet in de eerste plaats betrouwbaar zijn. Dit wordt voor een deel door de Radio Turret zelf verzorgd door de boodschappen uit te breiden met extra informatie voor foutdetectie en -correctie en met een ACK-mechanisme. De testopstelling om de betrouwbaarheid te testen van de ingebouwde mechanismen is te zien in figuur 2.5, waarbij de drie robots in elkaars buurt staan. Eén robot zal voortdurend controleren of er boodschappen binnenkomen. In de testopstelling is dit de robot met ID 1. De andere robots zullen voortdurend boodschappen (elk in totaal 256) sturen naar die ene robot. Elk zullen ze twee verschillende boodschappen continu afwisselen zodat makkelijk kan nagegaan worden op de


25

ontvangende robot of er iets fout gaat. De boodschappen bevatten enkel een serienummer15 en een reeks getallen die allemaal hetzelfde zijn. Elke robot houdt een eigen serienummer bij voor zijn boodschappen, zodat voor elke robot meteen gezien kan worden of boodschappen herhaald werden of verloren gegaan zijn. Naast het zenden of ontvangen van berichten loopt er ook nog een parallel proces op elk van de robots dat elke halve seconde een LED zal doen veranderen van toestand (aan/uit).

2.2.6

Communicatie in de testopstelling zonder QoS

Hieronder staan de programma’s aan de zender- en ontvangerszijde beschreven in pseudocode waarbij we geen gebruik maken van extra QoS16 . De gebruikte commando’s van de Radio Turret werden uitgebreid besproken in paragraaf 2.2.4. Ontvangerszijde Aan de ontvangerszijde wordt bijgehouden welke robot (ID) het laatst een bericht stuurde en met welk serienummer (SN). De robot controleert voortdurend de ontvangstbuffer en als het serienummer, het ID van de zendende robot of beide veranderen, zal dit ge¨ınterpreteerd worden als de ontvangst van een nieuw bericht. Algoritme 2.8 Ontvangerszijde zonder QoS 1: loop 2: Read reception buffer 3: if ( current SN 6= previous SN or current ID 6= previous ID ) then 4: Message received from robot current ID with serial number current SN 5: previous SN = current SN 6: previous ID = current ID 7: end if 8: end loop

Zenderzijde Elke robot stuurt afwisselend twee verschillende boodschappen naar de luisterende robot met ID 1. Dit wordt getoond in figuur 2.5. Ze doen dit zo snel als hun hardware hen toelaat. Het serienummer wordt, vóór het versturen van een nieuwe boodschap, met 1 verhoogd zoals te zien is in algoritme 2.9. De C-code voor de communicatie zonder QoS via de Radio Turret is te vinden op de bijgeleverde CD in de map Communication\Radio Turret\without QoS”. ” 15

Dit serienummer is 1 bij het eerst verzonden bericht en incrementeert elke keer er een nieuw bericht verzonden wordt. 16 QoS = Quality of Service, extra mechanismen in de communicatiestructuur die er zullen voor zorgen dat de communicatie betrouwbaarder wordt.


26

Algoritme 2.9 Zenderzijde zonder QoS voor robot 2 1: SN = 0 2: loop 3: Send message {SN, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1} to the Radio Turret 4: SN + + 5: Send message {SN, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2} to the Radio Turret 6: SN + + 7: end loop

Evaluatie In tabel 2.2 is het resultaat van een experiment te vinden met enkele opeenvolgende boodschappen die robot 1 ontvangen heeft van robots 2 en 3. Normaal moeten de serienummers voor elke robot mooi oplopend zijn. Dit is duidelijk niet het geval. Voor elke ontvangen boodschap van robot 3 gaan er drie of meer verloren, terwijl de boodschappen van robot 2 amper tussen de berichten van robot 3 raken. Het hoge aantal verloren boodschappen is slechts één aspect; ook de integriteit van de boodschappen wordt niet gewaarborgd. In principe moet elke boodschap uit één en het hetzelfde cijfer bestaan, maar in de tabel is te zien dat boodschappen in elkaar overlopen. Het is duidelijk dat het sturen en ontvangen op deze manier niet betrouwbaar is en dat de mechanismen, beschreven in paragraaf 2.2.1, ontoereikend zijn. Tabel 2.2: Ontvangen berichten zonder QoS

2.2.7

ontvangen bericht

van robot

met serienummer

4,4,4,4,4,4,4,3,3,3,3,3,3,3,3

3

61

4,4,4,4,4,4,4,4,4,4,4,4,4,4,4

3

65

4,4,4,4,4,4,4,4,4,4,4,4,4,4,4

3

69

3,3,4,4,4,4,4,4,4,4,4,4,4,4,4

3

72

3,3,3,3,3,3,3,3,3,3,3,3,3,3,3

3

76

1,1,1,1,1,2,2,2,2,2,2,2,2,2,2

2

202

4,4,4,4,4,4,4,4,4,4,4,4,4,2,2

3

83

4,4,4,4,4,4,4,4,4,4,4,4,4,4,4

3

87

3,3,3,3,3,3,3,3,3,3,3,3,3,3,4

3

90

3,3,3,3,3,3,3,3,3,3,3,3,3,3,4

3

94

4,4,4,4,4,4,4,4,3,3,3,3,3,3,3

3

97

Communicatie in de testopstelling na het inbouwen van QoS

Om de tekortkomingen uit de vorige paragraaf op te vangen, kan een beroep gedaan worden op de statusbyte van de Radio Turret. Het commando om deze byte op te vragen en de betekenis van de afzonderlijke bits werd reeds beschreven in paragraaf 2.2.4.


27

Ontvangerszijde Aan de ontvangerszijde is er slechts één statusbit van belang, namelijk bit1 die op 1 wordt gezet als er een nieuwe boodschap in de ontvangstbuffer zit. De robot zal de statusbyte van de Radio Turret opvragen tot bit1 op 1 staat. Pas daarna zal de ontvangstbuffer opgevraagd worden. De boodschappen zouden hierdoor niet meer in elkaar mogen overlopen. Bij druk radioverkeer bleek dat boodschappen vaak herverstuurd werden en na elkaar in de ontvangstbuffer terechtkwamen. Dit doet vermoeden dat er vaak iets fout loopt met de ACK die de ontvanger terugstuurt. In dit geval zal de zender vaak onnodig boodschappen herversturen. De Radio Turret van de ontvanger aanziet die duplicaten dus onterecht als nieuwe berichten. Daarom wordt het ID van de robot die het laatst een bericht stuurde bijgehouden en ook het bijhorende serienummer (SN), zodat duplicaten die net na elkaar toekomen er uitgefilterd kunnen worden. Als er zich een andere boodschap tussen bevindt, zal deze eenvoudige filtering niet werken, maar met een verstandig gebruik van het serienummer, zijn die toch gemakkelijk op te sporen. Als het serienummer monotoon stijgt bij elke nieuwe boodschap, kunnen alle boodschappen met een lager of gelijk serienummer genegeerd worden. De pseudo-code wordt weergegeven in algoritme 2.10. Algoritme 2.10 Ontvangerszijde met QoS 1: loop 2: repeat 3: Read the 8 bit status of the Radio Turret 4: until (bit1 == 1) 5: 6: 7: 8: 9: 10: 11:

Read reception buffer if ( current SN 6= previous SN or current ID 6= previous ID ) then Message received from robot current ID with serial number current SN previous SN = current SN previous ID = current ID end if end loop

Zenderzijde Aan de zenderzijde zijn er twee bits van de statusbyte die voor een QoS kunnen zorgen. Bit0 controleert of de zendbuffer leeg is en desgevallend kan een nieuwe boodschap naar de Radio Turret verstuurd worden. Dit is het duale geval als bij de ontvanger. Via bit2 kan gecontroleerd worden of de verzonden boodschap verloren is gegaan. Na het sturen van een bericht naar de zendbuffer, wordt de statusbyte gecontroleerd tot bit0 terug 1 is en er opnieuw gezonden mag worden. Als tegelijk ook bit2 1 is, weet de robot dat het laatste bericht verloren is gegaan. Als bit2 nul blijft, is de boodschap correct toegekomen. Het volledige proces van het zenden wordt in een aparte functie gestopt die −1 teruggeeft wanneer het bericht verloren is gegaan. Het programma aan de zenderzijde valt op die manier uiteen in 2 delen. Ten eerste is er de zendfunctie zelf (sendRobot()), die de boodschap als argument meekrijgt en een waarde teruggeeft, zodat de robot weet of een boodschap al dan niet verloren is gegaan. Dit staat beschreven


28

Algoritme 2.11 Zenderzijde met QoS voor robot 3 1: SN = 0 2: loop 3: repeat 4: Send message {SN, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3} with sendRobot() 5: until (sendRobot() == 0) 6: SN + + 7: 8: 9: 10: 11:

repeat Send message {SN, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4} with sendRobot() until (sendRobot() == 0) SN + + end loop

in algoritme 2.12. Het andere deel is het hoofdprogramma zoals te zien in algoritme 2.11. Hier zullen de boodschappen geschreven worden en daarna verstuurd worden via sendRobot(). Het versturen met sendRobot() wordt herhaald tot die 0 teruggeeft. Algoritme 2.12 Zendfunctie met QoS: sendRobot() 1: repeat 2: Read the 8 bit status of the Radio Turret 3: until (bit0 == 1) 4:

Send message to the Radio Turret

repeat 6: Read the 8 bit status of the Radio Turret 7: until (bit0 == 1) {Message sent} 5:

if (bit2 == 1) then return −1 {Message lost} 10: else 11: return 0 {Message sent successfully} 12: end if 8: 9:

De C-code voor de communicatie met QoS via de Radio Turret is te vinden op de bijgeleverde CD in de map Communication\Radio Turret\with QoS”. ” Evaluatie De test met de opstelling uit figuur 2.5 werd een aantal keer uitgevoerd. Eerst met één zendende en één ontvangende robot. In deze configuratie gingen er geen berichten verloren en moesten er zelfs geen herverstuurd worden. De ingebouwde kwaliteitsgaranties bleken in dit geval dus voldoende. De ontvangende robot kon de toestroom van berichten dus perfect binnenhalen en verwerken aan het tempo dat de andere robot zendde. De integriteit van de boodschappen bleek geen probleem meer te zijn, want nergens werd het verschijnsel van in elkaar overlopende boodschappen nog waargenomen. Het probleem bleek dus volledig opgelost met de genomen


29

maatregelen. Als de derde robot ook geactiveerd werd en boodschappen verstuurde, werd het ganse plaatje wat minder rooskleurig. Ten eerste bleek de robot met ID 3 dominanter te zijn dan die met ID 2. Robot 3 slaagde er immers in om zijn boodschappen zonder veel retransmissies door te sturen, terwijl robot 2 er maar af en toe in slaagde om een boodschap correct te verzenden. Als robot 3 zijn 256 boodschappen verstuurd had, kon robot 2 weer probleemloos boodschappen verzenden zonder dat er zelfs retransmissies nodig waren. Dit bevestigde opnieuw dat communicatie met maar twee robots en alle ingebouwde veiligheden foutloos verloopt. Als beide robots tegelijk communiceerden, gingen er soms geen, vaak twee of drie en maximaal zeven of acht boodschappen verloren. Een oplossing waarbij robots niet tegelijk mogen zenden staat beschreven in paragraaf 2.5.2. Dit duidt er dus op dat de ingestelde veiligheidsmechanismen nog ontoereikend zijn voor de communicatie met meer dan twee robots. Het probleem is dat de verloren boodschappen door de ontvangende robot moeten bevestigd zijn met een ACK, omdat de zendende robot anders de boodschap herverstuurd zou hebben. De fout ligt dus hoogstwaarschijnlijk bij de ontvangende robot die de boodschappen uit de ontvangstbuffer niet snel genoeg uitleest, zodat die al overschreven kunnen worden door een bericht van een derde robot. Een tweede mogelijkheid is dat er iets foutloopt in de communicatie (via de KNET-bus) tussen de Khepera II en de Radio Turret, net zoals bij de Sonar Turret ook soms het geval was (hoofdstuk 3). Dit gebeurde heel sporadisch, maar toch lijkt de belofte van K-Team Corporation, beschreven in paragraaf 2.2.1, dat inter-robot communicatie mogelijk is met 32 robots wat onrealistisch, zelfs met de veiligheidsmechanismen die tot hiertoe werden ingebouwd. Er moet wel een belangrijke kanttekening gemaakt worden bij de observaties van de voorgaande paragraaf. Er gaan inderdaad nog boodschappen verloren, maar de test ging dan ook uit van een worst-case scenario met robots die continu boodschappen versturen. Het is niet onlogisch dat één robot slechts de stroom berichten van één andere robot op maximale zendsnelheid aankan. Als er meer robots in het spel zijn, die elk zo snel mogelijk zenden, zal, door de vele retransmissies, de uiteindelijke datatransmissiesnelheid veel lager liggen dan in het geval dat er slechts één robot zendt en één ontvangt. Dit heeft een belangrijke implicatie op de mogelijke toepassingen van de communicatie. Het zal bijvoorbeeld onmogelijk zijn de robots voortdurend gegevens te laten uitwisselen om zo de andere robots te monitoren. Een permanente interactie tussen drie robots via communicatie, waarbij ze hun gedrag voortdurend aanpassen aan dat van de andere is dus een utopie. Dit hoeft niet noodzakelijk een zware beperking te zijn. De communicatie is immers een uitstekend middel om afspraken te maken tussen de robots onderling, waarna ze elk hun eigen programma volgen tot de nood aan nieuwe afspraken zich manifesteert. Het aantal verzonden boodschappen zal per sessie nooit echt hoog liggen, zodat een verzadiging van het medium nooit lang kan duren. De veiligheden die ingebouwd zijn, blijken voor deze niet-intensieve vorm van communicatie te volstaan. Verloren boodschappen die niet gedetecteerd werden, kwamen niet meer voor en de communicatie kon dus als betrouwbaar beschouwd worden.


2.3

30

Algemene Communicatiestructuur

Tot hiertoe werd enkel besproken hoe de communicatie tussen de robots verloopt en hoe deze betrouwbaar gemaakt wordt. De communicatiestructuur voor de robots zoals beschreven in deze paragraaf zal voor een deel specifiek zijn aan de berichtstructuur van de Radio Turrets, maar dit geldt enkel voor de concrete implementatie. De concepten zoals een vaste berichtstructuur, het bufferen en verpakken van berichten zijn algemeen toepasbaar voor andere communicatievormen, zoals die met de High Speed Radio Turret (paragraaf 2.1).

2.3.1

Vaste berichtstructuur

Bij de Radio Turrets werd in het voorgaande deel enkel het rauwe bericht beschouwd dat bestaat uit 16 bytes data. Deze bytes zijn unsigned17 , maar er kan ook afgesproken worden dat een groepje bytes samen een groter getal vormt. Een typische groepering bestaat uit 2 bytes (uint16) of 4 bytes (uint32)18 , maar ook decimale getallen zouden voorgesteld kunnen worden door een aantal bytes. De afspraak om bytes te groeperen kan nu op twee verschillende manieren gebeuren : • zonder vaste structuur: Indeling van de 16 bytes in groepjes verschillend voor elke andere boodschap. • met vaste structuur: Indeling voor alle boodschappen gelijk. Het probleem met de eerste optie is dat de ontvanger zal moeten kunnen detecteren hoe de 16 bytes data ingedeeld zijn in groepjes. Hij zal hiervoor extra informatie nodig hebben die we dus ook zullen moeten verwerken in de 16 bytes die we ter beschikking hebben. Concreet houdt dit in dat we enkele bytes zullen moeten reserveren waarmee de zender aan de ontvanger kan duidelijk maken hoe het huidige bericht ingedeeld is. Hierdoor verliezen we dus kostbare bytes, zodat we voor eenzelfde hoeveelheid informatie uiteindelijk meer berichten zullen moeten versturen. We zullen bijgevolg gebruik maken van de tweede optie, waarbij we elk bericht een vaste structuur geven. Deze structuur bestaat uit twee grote delen: de header en de pure data. Elk bericht dat binnenkomt, kan onmiddellijk ontleed en verwerkt worden aan de hand van de headerinformatie. Die heeft dezelfde vorm voor elk bericht. Eenvoudige velden zoals het serienummer en het functienummer kunnen het behandelen van een bericht veel eenvoudiger en sneller maken. De header gebruikt een deel van de byte-ruimte die voor zuivere data bedoeld is, zodat uiteindelijk minder zuivere data verstuurd kan worden per bericht, maar de flexibiliteit die een header met zich meebrengt is te belangrijk om er geen te gebruiken. Een groot voordeel van de Khepera II -robots is dat ze in staat zijn met parallelle processen te werken [11, sectie 2.1]. Hierbij kiezen we ervoor om één proces voortdurend de ontvangstbuffer te 17

Een byte bestaat uit 8 bits en als de byte unsigned is, kan hij waarden aannemen van 0 tot 255. De 16 en 32 slaan op het aantal bits waarmee de integer gerepresenteerd wordt. Het zijn altijd veelvouden van acht omdat ze uit een paar bytes zullen bestaan en deze bevatten 8 bits. Als er een ’u’ voor staat, is het getal unsigned. 18


31

laten lezen en een eerste verwerking te laten doen, waarna de rest van de verwerking afgehandeld wordt door een ander proces. Het ontvangend proces kan zo meteen weer verder gaan met zijn kerntaak: het lezen van de ontvangstbuffer. Als de volledige verwerking in het ontvangend proces zou gebeuren en dit te lang zou duren, zouden nieuwe berichten niet vlug verwerkt kunnen worden. Een vaste structuur laat gemakkelijk toe om een opsplitsing te maken tussen een ontvangend en een verwerkend proces. Het ontvangend proces verwerkt de header, waarna het afhandelen van de data wordt overgelaten aan het verwerkend proces. Naast de header kan voor elk bericht ook vastgelegd worden hoe de bytes in het pure datagedeelte gegroepeerd zullen zijn tot grotere eenheden. Het voordeel is dat de verwerking van de data altijd op dezelfde manier gebeurt. Het nadeel is dat bepaalde informatie minder efficiënt opgeslagen wordt, zodat de beschikbare bytes niet optimaal benut worden. De lengte van de berichten ligt bij de Radio Turrets vast en daardoor wordt het aanlokkelijk om de groeperingen op voorhand vast te leggen. In de uiteindelijke berichtstructuur die hieronder beschreven wordt, werd getracht om een evenwicht te vinden tussen groeperingen van bytes en afzonderlijk bytes, opdat de structuur zowel flexibel als algemeen toepasbaar zou zijn. De berichtstructuur Tabel 2.3: Algemene berichtstructuur

SN

functieNr

byte 1

byte 2

uint32 -1

uint32 -2

uint32 -3

Elk bericht bestaat uit de volgende onderdelen: • SN Het serienummer dat toelaat om retransmissies er uit te filteren. • functieNr Deze byte laat toe te specifiëren welke functie de daaropvolgende data-bytes hebben. • 2 extra bytes Deze bytes worden gebruikt om kleine waarden in op te slaan. • 3 uint32’s Deze uint32’s worden gebruikt om grote waarden in op te slaan. De oorspronkelijke 16 bytes worden gereduceerd tot zeven informatieve cellen. Daarvan vormen de eerste twee de header, die bedoeld is om het verwerken gemakkelijk te maken voor het ontvangend proces. Het serienummer van een bericht kan algemeen opgeslagen worden, waarbij enkel gecontroleerd kan worden of het serienummer verandert tegenover een vorig bericht (zonder dat hierbij het ID van de verzender in rekening wordt gebracht), zoals in algoritmes 2.8 en 2.10, maar het kan ook met een uitgebreid geheugen werken. Hierbij wordt voor elke sturende robot het serienummer bijgehouden van zijn laatste bericht. De manier waarop dit wordt opgeslagen, staat beschreven in paragraaf 2.3.3. Hierdoor zal de filtering veel strikter gebeuren, omdat per robot een onderscheid gemaakt kan worden tussen nieuwe berichten, herverzonden berichten en vervormde berichten. Hoe het precies werkt voor de eerste twee komt terug in de volgende paragraaf.


32

De categorie van vervormde berichten is erg zeldzaam, maar toch kunnen ze met een vervormd functienummer op het verkeerde moment het gedrag van een robot grondig in de war sturen. De tweede byte in de header stelt het functienummer voor dat voor een eerste opsplitsing zorgt, zodat er met de rest van de data kan omgesprongen worden op een manier die eigen is aan de functie. Het tweede aspect van de vaste structuur betrof het groeperen van de pure data-bytes. De grootste eenheid voor integers bij de Khepera II -robots bestaat uit 32 bits en het lag voor de hand om die als eenheid te nemen voor het doorsturen van data. Door de twee headerbytes was er slechts plaats voor drie van deze uint32 waarna er nog twee bytes overbleven van de 16. Die laatste twee zullen gebruikt worden om kleine stukjes extra informatie door te geven, zoals bijvoorbeeld het teken van een uint32. Dit kan nodig zijn, omdat negatieve getallen niet kunnen worden doorgestuurd aangezien alle doorgegestuurde waarden unsigned zijn. Om de overgang van de vaste berichtstructuur naar de uiteindelijke fysische communicatie te realiseren, moet een zekere functionaliteit ingebouwd worden. Die wordt in de volgende twee paragrafen beschreven.

2.3.2

Verpakken van boodschappen

De hoofdtaak van de inpakfunctie bestaat erin om de zeven informatievelden die beschreven werden in de vorige paragraaf om te zetten in de 16 bytes van het eigenlijke bericht dat naar de Radio Turret gestuurd zal worden. De eerste vier informatievelden (serienummer, functienummer en twee extra bytes) zijn al van het type byte en kunnen rechtstreeks in de uiteindelijke byte-rij geschreven worden. De drie uint32 zullen via modulorekenen omgezet worden in telkens vier bytes. Het omzetten kan ook gerealiseerd worden met een 8-bit masker (acht keer ‘1’), dat vier bytes uit de uint32 filtert (door de AND-functie te nemen van het masker en de uint32). Het uitpakken van een bericht van de Radio Turret verloopt op dezelfde manier, maar dan in de omgekeerde richting, waarbij de laatste twaalf bytes per vier weer omgezet worden in een uint32. Het inpakken heeft ook nog een tweede functie: het zal ervoor zorgen dat elk bericht het goede serienummer meekrijgt. Dit serienummer vormt dus geen argument van de functie packMsg(), maar maakt gebruik van de bufferstructuur die aanwezig is in de software. Die zal in de volgende paragraaf beschreven worden; het volstaat te weten dat de robot, voor elke andere robot waarnaar hij boodschappen stuurt, het serienummer bijhoudt van de laatst verzonden boodschap. Als de functie packMsg() wordt opgeroepen, zal de robot het serienummer bij de goede robot automatisch met één verhogen. Zolang de packMsg()-functie niet opgeroepen wordt, zal dit serienummer niet verhogen en zal de vorige boodschap (die hoort bij dit serienummer) bewaard blijven in een buffer, zodat het bericht eventueel herverzonden kan worden. In de volgende paragraaf wordt wat dieper ingegaan op de buffers.


2.3.3

33

Boodschappen bufferen

De buffers zijn in feite niets meer dan twee matrices. Eén matrix waarin we de ontvangen boodschappen bufferen en één waarin we de verstuurde boodschappen opslaan. Het aantal rijen is gelijk aan het totale aantal robots dat op dat moment binnen het Radio Turret-bereik is van de robot. Als er een boodschap verstuurd wordt naar een andere robot, zullen de zeven informatievelden van een bericht, die beschreven staan in paragraaf 2.3.1, in de zeven kolommen van de matrix gestopt worden. Dit zal gebeuren in de rij die overeenkomt met het ID van de robot waarnaar gestuurd wordt. Bij een ontvangen bericht is de situatie volkomen duaal. De informatievelden worden opgeslaan in de rij die overeenkomt met het ID van de zendende robot. De rij met het ID van de robot zelf zal natuurlijk nooit ingevuld worden. Er zijn meerdere voordelen aan dit buffersysteem. Ten eerste maakt de functie packMsg() hiervan gebruik om het serienummer van te verzenden berichten aan te passen en op te slaan. Ten tweede wordt de binnenkomende data meteen beschikbaar en bereikbaar voor alle parallelle processen die erop wachten. Hierdoor kan de afhandeling van de eigenlijke data van de boodschap door een ander proces gebeuren dan het proces dat boodschappen ontvangt, zodat het ontvangend proces weer kan doorgaan met de controle op nieuwe berichten. Om dit alles te verduidelijken wordt een voorbeeld gegeven van een situatie afkomstig uit de testopstelling die te zien is in figuur 2.5. De matrix voor inkomende berichten wordt weergegeven van de robot met ID 1 voor en na het ontvangen van een nieuwe boodschap van robot 3. Tabel 2.4: Buffer voor inkomende berichten: initiële toestand

SN

functieNr

byte 1

byte 2

uint32 -1

uint32 -2

uint32 -3

0

0

0

0

0

0

0

30

10

1

1

1

1

1

133

5

4

4

4

4

4

Tabel 2.5: Buffer voor inkomende berichten: nieuw bericht van robot 3 ontvangen

SN

functieNr

byte 1

byte 2

uint32 -1

uint32 -2

uint32 -3

0

0

0

0

0

0

0

30

10

1

1

1

1

1

134

12

3

3

3

3

3

Zoals te zien is in de tweede tabel verandert de derde rij (in vet) omdat er een nieuwe boodschap is van robot 3.


2.3.4

34

Evaluatie

Deze communicatiestructuur vormt de ruggengraat bij het inbouwen van QoS. Ze ondersteunt de initieel ge¨ımplementeerde QoS (paragraaf 2.2.7), die enkel gebaseerd was op de statusbyte van de Radio Turret. Door de flexibiliteit van het systeem kan dezelfde communicatiestructuur zonder problemen gebruikt worden om een verhoogde QoS te implementeren, zoals we zullen bespreken in paragraaf 2.4. De zenden ontvangstfuncties dienen aangepast te worden, maar het verpakken, bufferen en indelen van een bericht kunnen blijven. In de toekomst kan nog extra functionaliteit ingebouwd worden zoals het opvangen van nieuwe robots, robots die herstarten of wegvallen... Dit alles kan gerealiseerd worden met de hierboven beschreven communicatiestructuur, zoals zal blijken in paragraaf 2.5.1. Het belangrijkste minpunt is de vaste lengte van boodschappen, maar dit is eigen aan de Radio Turret die met dergelijke berichten werkt. Het algemene concept voor een communicatiestructuur via berichten met variabele lengte is net hetzelfde, maar de buffering van berichten dient te gebeuren met behulp van matrices met een dynamische lengte.


2.4

35

Uitbreiden van QoS

In paragraaf 2.2.7 was de statusbyte van de Radio Turret de basis om kwaliteitsgaranties in te bouwen. De statusbyte laat toe drie zaken te controleren: • Het beschikbaar zijn van de Radio Turret om te zenden (bit0) • Het beschikbaar zijn van de Radio Turret om te ontvangen (bit1) • Verloren gegane boodschappen (bit2) Er zijn twee soorten observaties waaruit bleek dat deze drie controlebits toch niet voldoende waren. Ten eerste konden er bij druk verkeer toch nog boodschappen verloren gaan, zoals bleek in paragraaf 2.2.7. Ten tweede zijn er observaties waarbij de robots een half uur probleemloos hun algoritme uitvoeren, waarbij relatief weinig communicatie nodig is en waarbij toch plots enkele boodschappen na elkaar om onverklaarbare redenen verloren gaan. De zendende robot denkt dat zijn boodschappen zijn toegekomen, maar de andere heeft ze nooit ontvangen. Met de huidige QoS kan dit niet opgevangen worden. Hoe zeldzaam deze observaties ook zijn, toch waren de gevolgen voor het verloop van het algoritme dat de robots uitvoerden, meestal dramatisch. Vaak wachtte één robot op input van een andere en aangezien die informatie nooit meer kon komen, omdat de andere robot dacht dat zijn boodschap was toegekomen, zat de hele formatie in een deadlock. Wegens deze problemen werd ervoor gekozen om extra veiligheden in de communicatie in te bouwen.

2.4.1

Werking

Het detecteren van definitief verloren berichten zal niet meer door de Radio Turret afgehandeld worden, maar door de software op de robot zelf, door middel van time-outs and ACK-berichten. Ook de Radio Turret zelf werkt met time-outs en ACK’s, maar dit gebeurt zonder dat de software op de robot hierin kan tussenkomen. Aangezien er blijkbaar toch berichten kunnen verloren gaan, zullen we dit mechanisme in de software van de robot zelf implementeren, zodat we er meer controle over hebben. Het principe is als volgt. Een robot stuurt een bericht en start een timer. Als er binnen een zeker tijdsinterval (enkele milliseconden) geen ACK voor het verzonden bericht is ontvangen, dan verloopt de timer en wordt een time-out gegenereerd. In dit geval zendt de robot dezelfde boodschap - met hetzelfde serienummer - opnieuw. Als er wel een ACK binnenkomt, gaat de robot verder met zijn programma tot er een nieuw bericht verzonden moet worden, waarbij het serienummer verhoogd wordt.


36

Loskoppelen van ACK-verkeer Indien een bericht ontvangen wordt, stuurt de robot een ACK terug. Dit gebeurt zonder een time-out-mechanisme, hoewel ook ACK’s verloren kunnen gaan. De achterliggende visie hierbij is dat de zendende robot zijn bericht maar moet herversturen als de ACK verloren gaat en hij dus geen ACK ontvangt. Dit maakt de ACK-structuur eenvoudiger dan het normale dataverkeer. We krijgen bijgevolg een opsplitsing van het verkeer in verschillende stromen waarbij het ACKverkeer volgens andere regels verstuurd wordt dan het dataverkeer. De ACK wordt verstuurd volgens best-effort principe. Een robot verstuurt een ACK als hij een databericht ontvangen, maar kijkt er verder niet meer naar om. Dit in tegenstelling tot het dataverkeer waarbij de robot pas een volgend bericht zal versturen indien hij zeker is dat het vorige goed ontvangen is. Er is nog een tweede reden om het ACK-verkeer los te koppelen van het dataverkeer en dat is het serienummer. Bij het dataverkeer zullen berichten ingepakt en uitgepakt worden. Het serienummer zal daarbij automatisch verhogen en boodschappen zullen opgeslagen worden in de buffers. Zo kan een ontvangende robot filteren op het serienummer. Als de robot een bericht binnenkrijgt met hetzelfde serienummer, dan weet hij dat het een retransmissie is. Als het serienummer één hoger is, gaat het over een nieuw bericht (paragraaf 2.3.2). Als ACK’s in ditzelfde systeem betrokken werden, zouden ze de strikte filtering met het serienummer onmogelijk maken. Dit wordt duidelijk met figuur 2.6. Hierin sturen twee robots tegelijk een bericht naar

Figuur 2.6: ACK die verloren gaat als dataverkeer

elkaar (volle pijlen). Ze ontvangen deze ongeveer op hetzelfde moment en sturen beide een ACK (gestreepte pijlen) voor het ontvangen bericht. Stel dat de ACK met serienummer 6 verloren gaat (dit is een ACK-bericht voor het bericht dat verstuurd werd vanop de robot met ID 2 en het serienummer 13 had). Dan zal de robot met ID 2 het bericht met serienummer 13 opnieuw doorsturen op het moment dat zijn timer is afgelopen. Dit is echter onmogelijk geworden, omdat er nu een ander bericht (ACK met SN 14) in zijn buffer zit in plaats van het bericht met SN 13. Bovendien is ook het serienummer van de berichten naar de robot met ID 1 al verhoogd, aangezien we het ACK-bericht voor bericht met serienummer 5 ook een serienummer (14) gegeven


37

hebben. Omdat de robot met ID 1 een filtering toepast op de inkomende berichten, waarbij enkel berichten met een serienummer gelijk aan of één hoger dan het huidige serienummer in de buffer aanvaard worden, zal het herverzonden bericht met serienummer 13 niet meer door deze filtering geraken (aangezien het huidige serienummer reeds op 14 staat, door de ACK voor boodschap SN 5 die ook een serienummer gekregen heeft). De strenge filtering kan weggelaten worden, maar op die manier vervalt een belangrijk veiligheidsmechanisme. Daarom hebben we voor een andere oplossing gekozen. Indien we de ACK niet inpakken of bufferen, waardoor het serienummer niet verhoogt, verdwijnt het filterprobleem dat we hierboven beschreven. De ACK’s staan op die manier los van de andere berichten en zullen verstuurd worden via sendRobot() beschreven in algoritme 2.12. Processen De Khepera II -robot ondersteunt parallelle processen. Hiervan werd eerder al gebruik gemaakt door de opsplitsing in een ontvangend en verwerkend proces (paragraaf 2.3.1). In het geval van ACK’s hebben we opnieuw een ontvangend en een verwerkend proces. Het ontvangen van ACK’s maakt deel uit van het globaal ontvangend proces dat voortdurend de Radio Turret controleert op nieuwe boodschappen en elke nieuwe boodschap naar functie indeelt. Het tweede proces zal instaan voor de verdere verwerking van de data en het algoritme van de robot. Met het invoeren van het ACK-verkeer, hebben we ook nog een derde proces ge¨ımplementeerd dat enkel instaat voor het versturen van ACK’s en dit doet de robot wanneer een bericht van een andere robot ontvangen wordt. Het voordeel van het ontkoppelen van deze twee taken (nieuwe boodschappen detecteren en ACK’s versturen) is dat ze beide op een verschillende snelheid kunnen werken en dat bij druk verkeer de te versturen ACK’s gebufferd kunnen worden en rustig verstuurd kunnen worden op het eigen tempo van het derde proces. Bovendien verliest het ontvangend proces zo geen tijd met het versturen van ACK’s en kan het terug verdergaan met het ontvangen van berichten. We zullen dus de te versturen en de ontvangen ACK’s bufferen vanuit het ontvangend proces. Via twee arrays van booleans (0: verwerkt, 1: niet verwerkt) laten we de verschillende processen met elkaar communiceren over welke ACK’s nog verstuurd moeten worden en voor welke verstuurde berichten reeds een ACK ontvangen is. Eén array bevindt zich tussen het ontvangend proces en het ACK-versturend proces waarbij het ontvangend proces een boolean op 1 zet als er een nieuwe ACK verstuurd moet worden. Het ACK-versturend proces heeft echter meer gegevens nodig om de correcte ACK te versturen, namelijk naar welke robot en voor welk serienummer de nieuwe ACK verstuurd moet worden. Daarom gebruiken we een 2-dimensionale array met de volgende drie kolommen: • Eerste kolom: bevat 0 (verwerkt) of 1 (nieuw te versturen ACK). • Tweede kolom: bevat het ID van de robot waarnaar de ACK verstuurd moet worden. • Derde kolom: bevat het serienummer dat acknowledged moet worden.


38

Een tweede, soortgelijke array bevindt zich tussen het ontvangend proces en het proces dat boodschappen verzendt, waarbij het ontvangend proces een boolean op 1 zet indien een ACK van een andere robot ontvangen werd. Het verzendend proces dat wacht op een ACK, zal dit detecteren en vervolgens verdergaan met het proces. De array bestaat uit: • Eerste kolom: bevat 0 (verwerkt) of 1 (nieuw ontvangen ACK). • Tweede kolom: bevat het ID van de robot vanwie de ACK afkomstig is. • Derde kolom: bevat het serienummer van het bericht dat acknowledged werd. Deze buffer lijkt op het eerste gezicht niet nodig aangezien ervoor gezorgd wordt dat boodschappen - ACK’s niet meegerekend - enkel verstuurd worden indien er een ACK voor het voorgaande bericht ontvangen is. Toch wordt er op die manier geen rekening gehouden met de grootte van de time-out timer. Als deze zeer klein gekozen wordt, zodat berichten snel herverzonden kunnen worden, kan het gebeuren dat een ACK nog ontvangen wordt nadat de time-out optrad. Ondertussen is het bericht al herverstuurd en zal er even later nog een tweede ACK voor het bericht ontvangen worden. De verzendende robot kan geen onderscheid maken tussen een ACK voor het oorspronkelijke en één voor het herverzonden bericht en zal dus, na het ontvangen van de eerste ACK, doorgaan met het sturen van een volgende boodschap. In dit geval kunnen zowel de ACK voor het nieuwe bericht en dat voor het herverzonden bericht tegelijk toekomen en om dit op te vangen is er een kleine buffer nodig tussen de twee processen. De buffers zijn circulair wat wil zeggen dat wanneer het laatste element van de buffer geschreven werd, de volgende keer opnieuw het eerste element overschreven zal worden. Maar belangrijker is dat ze niet te groot gekozen moeten worden. Ze dienen vooral om plotse golven van binnenkomende boodschappen op te vangen en dan rustig te verwerken. Ze vormen dus een oplossing voor korte uitbarstingen”. De proces- en bufferstructuur wordt weergegeven in figuur ” 2.7 met de drie processen en de twee buffers. Een voorbeeld van zo’n buffer is te zien in tabel 2.6. De buffer houdt enkel het serienummer bij, het ID van de sturende robot en of er nieuwe informatie is toegevoegd. De buffer wordt van boven naar onder opgevuld om daarna weer bovenaan te beginnen. De buffer kan zowel gebruikt worden om binnengekomen ACK’s in op te slaan als boodschappen waarvoor nog een ACK gestuurd moet worden. In het laatste geval stelt de buffer uit tabel 2.6 een situatie voor waarbij de robot een ACK moet sturen voor een retransmissie (SN 34) en een nieuw bericht van robot 3 (SN 67). Elke rij met een nul in de eerste kolom toont een verwerkt bericht dat overschreven mag worden door het ontvangend proces. Als er een één staat moet het nog verwerkt worden (vet). In het andere geval zal de buffer binnenkomende ACK’s bevatten en nu toont tabel 2.6 de situatie waarin een ACK (SN 34) een tweede keer is toegekomen en een ACK (SN 67) bevat voor het bericht dat daarna al verstuurd werd. Deze situatie werd hierboven beschreven in paragraaf 2.4.1 bij de uiteenzetting over de noodzaak van een buffer voor ontvangen ACK’s.


39

Figuur 2.7: Proces- en bufferstructuur voor de communicatie

Tabel 2.6: Circulaire buffer voor ACK’s

nieuw/oud

ID sturende robot

SN

0

2

34

1

2

34

1

3

67

0

2

33

0

3

66

Structuur van een ACK-bericht Tot hiertoe werd een ACK steeds beschouwd als een speciaal soort boodschap die gescheiden moet zijn van het normale dataverkeer. Om dit te verkrijgen, nemen we een gewoon bericht maar geven we het een functienummer 250 om aan te duiden dat we hier te maken hebben met een ACK-bericht. Het serienummer doet er niet toe maar zal altijd op 0 gezet worden. Verder wordt ook het serienummer meegestuurd van de boodschap die acknowledged wordt. De robot die een boodschap verstuurd heeft en wacht op de correcte ACK, controleert of de goede ACK ontvangen is. De boodschap die verstuurd is, zit immers nog altijd in zijn buffer voor uitgaande berichten. Door te controleren of de ACK van de goede robot afkomstig is en het meegestuurde serienummer overeenkomt met het serienummer in de buffer voor uitgaande berichten, kan de robot de ACK verifiëren.


40

De structuur wordt hieronder weergegeven in tabel 2.7 en via het speciale functienummer kan het ontvangend proces met algoritme 2.14 achterhalen of een bericht een ACK is of niet. Tabel 2.7: Structuur van een ACK-bericht

SN

functieNr

byte 1

byte 2

uint32 -1

uint32 -2

uint32 -3

0

250

SN ontvangen bericht

0

0

0

0

In het volgende deel wordt de zender- en ontvangerszijde besproken bij de robots. Omdat elke robot nu ook ACK’s zal moeten versturen is het moeilijk om deze helemaal los te koppelen van elkaar. Al de veiligheden zijn maar mogelijk door gebruik te maken van de communicatiestructuur beschreven in paragraaf 2.3 en de zender- en ontvangerszijde zullen hier dan ook op steunen.

2.4.2

Testopstelling

Analoog aan de testopstelling uit figuur 2.5, zullen de robots stil staan en communiceren ze enkel met elkaar. Het verschil met de vorige testopstelling zit hem in de aard van de communicatie. Elke robot zal nu twee berichten sturen en er ook twee ontvangen. Eén naar elke andere robot en één van elke robot. In het totaal zullen dus zes verschillende boodschappen doorgestuurd worden en dit is te zien in figuur 2.8. Het programma zal dus voor elke robot hetzelfde zijn op de inhoud van de verstuurde boodschappen na.

Figuur 2.8: Testopstelling bij uitgebreide QoS


41

Testalgoritme Het testprogramma zorgt ervoor dat elke robot een verschillende boodschap stuurt naar de twee andere robots zoals te zien in algoritme 2.13. Dit verkeer is dataverkeer en telkens zal een boodschap ingepakt worden met de packMsg()-functie en verstuurd met sendAckRobot() (paragraaf 2.4.4). Algoritme 2.13 Testprogramma 1: loop 2: if (Eigen ID == 1) then 3: packMsg({5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5}) for robot 2 4: Send message with sendAckRobot() and wait for ACK packMsg({6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6}) for robot 3 Send message with sendAckRobot() and wait for ACK

5: 6:

else if (Eigen ID == 2) then packMsg({3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3}) for robot 1 Send message with sendAckRobot() and wait for ACK

7: 8: 9:

packMsg({2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}) for robot 3 Send message with sendAckRobot() and wait for ACK

10: 11:

else if (Eigen ID == 3) then packMsg({1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}) for robot 1 Send message with sendAckRobot() and wait for ACK

12: 13: 14:

packMsg({4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}) for robot 2 Send message with sendAckRobot() and wait for ACK

15: 16: 17: 18:

end if end loop

2.4.3

Ontvangerszijde

In deze sectie breiden we het vorige algoritme voor de ontvangerszijde (paragraaf 2.2.7) uit. Dit resulteert in algoritme 2.14 waarbij de robot eerst zal controleren of de ontvangen boodschap een ACK is door te kijken of het functienummer gelijk is aan 250. In dat geval wordt de ACK in de circulaire buffer geplaatst voor binnenkomende ACK’s. Het proces dat berichten verstuurt, zal dit opmerken en na controle van de ACK zal dit proces verdergaan en kan het opnieuw boodschappen versturen. Indien het functienummer niet 250 is, zal de robot controleren of het huidige serienummer één hoger is dan dat van het voorgaande bericht van die robot. De robot weet in dat geval dat het om een nieuw bericht gaat en zal de nodige gegevens in de buffer plaatsen, zodat het ACKversturend proces de correcte ACK kan versturen. In dit geval zal de boodschap ook uitgepakt worden en opgeslagen in de buffer voor ontvangen berichten. Indien het serienummer gelijk is aan dat van het vorige bericht dat ontvangen werd, zal de


42

robot besluiten dat zijn ACK niet is toegekomen. Hierop zal hij dezelfde actie ondernemen als bij een nieuw bericht zodat er een nieuwe ACK verstuurd wordt. De boodschap zal evenwel niet uitgepakt worden, omdat het bericht al in de buffer zit. In alle andere gevallen zal de ontvangen boodschap genegeerd worden. Algoritme 2.14 Ontvangerszijde met uitgebreide QoS 1: loop 2: repeat 3: Read the 8 bit status of the Radio Turret 4: until (bit1 == 1) 5:

Read Reception Buffer

6:

if (f uncieN r == 250) then ACK received Place in ACK-in-buffer ⇒ Deal with ACK in sending process

7: 8:

else if (current SN == previous SN + 1) then unpackMsg() New message Received Place in ACK-out-buffer ⇒ Send ACK in ACK-sending process

9: 10: 11: 12: 13: 14: 15: 16: 17:

else if (current SN == previous SN ) then Same message received Place in ACK-out-buffer ⇒ Send ACK in ACK-sending process end if end loop

2.4.4

Zenderzijde

Voor het zenden van berichten wordt nog altijd gesteund op de zendfunctie (sendRobot()) beschreven in algoritme 2.12. Die vormt nu echter enkel de kern van de nieuwe zendfunctie en rond die kern is een extra kader gebouwd, zodat het systeem van ACK’s en time-outs ge¨ımplementeerd kon worden. In deze nieuwe zendfunctie (sendAckRobot()) zal, na het verzenden van een bericht, een timer gestart worden en indien die afloopt zonder dat een correcte ACK ontvangen werd, zal de boodschap herverstuurd worden. Wordt uiteindelijk toch de correcte ACK ontvangen, dan wordt de nieuwe zendfunctie afgesloten en wordt verdergegaan met de rest van het programma.

2.4.5

ACK-versturend proces

Dit proces controleert de circulaire buffer die aanwezig is tussen dit proces en het ontvangend proces om te zien of er nieuwe berichten zijn waarvoor een ACK moet gezonden worden. Als dit zo is, dan zal er een ACK aangemaakt worden die ook het serienummer zal meekrijgen van de ontvangen boodschap. Deze informatie zit in de buffer naast het ID van de robot waarnaar het ACK moet worden verstuurd en de byte die aangeeft of informatie in de buffer nieuw is of niet. De ACK wordt verstuurd met de oude zendfunctie (sendRobot()) van algoritme 2.12.


Algoritme 2.15 Zendfunctie 2 met uitgebreide QoS: sendAckRobot() 1: Send message with sendRobot() repeat Start timer 4: repeat 5: Check elapsed time 6: until (ACK received or time-out) 2: 3:

7: 8: 9: 10:

if (time-out) then Resend message with sendRobot() else if (correct ACK received for sent message) then Continue program

else 12: Received ACK is incorrect 13: end if 14: until (Correct ACK received) 11:

Algoritme 2.16 Het ACK-versturend proces 1: loop 2: repeat 3: Check ACK-in-buffer 4: until (new ACK to be sent) 5: Send ACK 6: end loop

43


44

De C-code voor de communicatie met uitgebreide QoS via de Radio Turret is te vinden op de bijgeleverde CD in de map Communication\Radio Turret\with extended QoS”. ”

2.4.6

Evaluatie

De robot heeft nu volledige controle over de communicatie dankzij het invoeren van de ACK’s en time-outs. Bij het uitvoeren van de test met de opstelling in figuur 2.8 bleek dat de drie robots in 12 minuten elk ongeveer 256 berichten hadden doorgestuurd naar elke andere robot. Dit is eigenlijk niet zo snel, maar er zijn toch een paar heel interessante zaken op te merken. Bij de vorige kwaliteitsgaranties was het meestal zo dat één robot de bovenhand haalde, waardoor de andere hun boodschappen er amper nog door kregen. Met meerdere robots wil dat zeggen dat een enkele robot het ganse verkeer kan overheersen door verzadiging van het medium. De andere robots kunnen in dat geval nog amper communiceren. Daarnaast konden boodschappen af en toe verloren gaan zonder dat ze herverzonden werden. Deze twee problemen zijn nu verholpen met de huidige communicatie. Niet alleen zullen boodschappen nooit meer verloren gaan omdat ze bevestigd moeten worden via een ACK, maar het verkeer blijkt ook veel eerlijker verdeeld te zijn. In de test slaagde de ene robot erin om iets sneller te zenden dan een ander, maar deze verschillen waren verwaarloosbaar in vergelijking met de situatie ervoor. Op 256 berichten liep het verschil tussen de verstuurde boodschappen van beide robots op tot 50 maar dat is veel beter dan de situatie waarbij de andere robots niet meer kunnen communiceren. Daarbij komt dat deze situatie het worst-case scenario simuleert waarbij robots continu informatie doorzenden. Dit zal bij de gebruikte algoritmes in dit onderzoek nooit voorkomen, omdat de communicatie enkel wordt gebruikt om afspraken te maken. Deze vorm van communicatie waarbij de drie robots tegelijk mogen zenden, voldeed aan de opgestelde eis voor foutloze transmissie.


2.5

45

Dynamische groepstructuur

Nu de communicatie helemaal op punt staat, kan nagedacht worden over de uitdagingen in de toekomst. De belangrijkste is het omgaan met dynamische groepen. In deze scriptie bestond een formatie steeds uit drie robots. Dit is eigenlijk slechts een startpunt voor het onderzoek, want veel situaties zijn denkbaar waarbij het aantal variabel is. Zo kan een robot die later is opgestart vragen aan de huidige robots om zich aan te sluiten bij de formatie. In dit geval zullen de robots samen hun gedrag moeten herbepalen. Maar evengoed kan een robot uitvallen, zodat de resterende robots hun formatiegedrag zullen moeten aanpassen aan de nieuwe situatie. Vanuit een communicatie-oogpunt is dit een uitdagend gegeven en in de volgende paragrafen zullen hiervoor twee aanpakken aangebracht worden19 . De eerste bouwt voort op de bestaande structuren die in dit onderzoek ontwikkeld werden, terwijl de tweede aanpassingen vereist aan het huidige communicatieprotocol.

2.5.1

Voortbouwen op de huidige communicatiestructuur

Het is mogelijk om het dynamisch groepsgedrag te implementeren, voortbouwend op de bestaande communicatiestructuur. In de volgende twee paragrafen besteden we aandacht aan hoe robots het wegvallen en toevoegen van een robot in de groep kunnen implementeren. Detecteren van een weggevallen robot De reeds besproken zendfunctie (sendAckRobot()) kan een ondersteuning bieden voor het detecteren van weggevallen robots. Als er voor een boodschap na een zeker aantal time-outs nog altijd geen ACK ontvangen is, kan deze robot als verloren beschouwd worden. Hij kan dan uit de lijst van actieve robots verwijderd worden. Bovendien zal de rij die overeenkomt met zijn ID in de buffer van inkomende en uitgaande berichten weer op nul ge¨ınitialiseerd worden. Als de robot heropstart en weer boodschappen zou versturen, dan zullen deze door de andere robots niet meer genegeerd worden omdat het eerste bericht serienummer 1 zal hebben, wat inderdaad één hoger is dan nul. Robot toevoegen aan een groep andere robots Het toevoegen van een robot kan geregeld worden via een speciaal soort bericht (zoals het ACK-bericht dat reeds beschreven werd in paragraaf 2.4.1) met een functienummer dat we bijvoorbeeld gelijkstellen aan 251. Deze boodschap zal vanaf nu een REQ20 genoemd worden. Het ontvangend proces zal nu ook moeten controleren of een boodschap een REQ-boodschap is. In dat geval zal de robot de nieuwe robot toevoegen aan zijn lijst van actieve robots en de rij overeenkomstig met zijn ID in de buffers voor binnenkomende en uitgaande berichten op nul initialiseren. De manier waarop de nieuwe robot in de formatie opgenomen wordt, valt buiten 19 Beide aanpakken worden besproken uitgaande van de communicatie met behulp van de Radio Turrets, maar de aangebrachte oplossingen kunnen ook toegepast worden op de communicatie via de High Speed Radio Turrets. 20 REQ (request) duidt op een robot die verzoekt om een deel van de groep te zijn.


46

de communicatie en moet in de robot zelf ge¨ımplementeerd worden. Een weggevallen robot kan ook met een REQ boodschap vragen om weer opgenomen te worden in de groep. Het dynamisch omgaan met robots in een groep kan dus met de huidige structuur opgevangen worden. Het voordeel is dat er geen master nodig is en dat elke robot lokaal bijhoudt welke robots binnen zijn bereik zijn. Een grotere groep robots kan zo spontaan uiteenvallen in kleinere groepjes die binnen elkaars communicatiebereik voorkomen.

2.5.2

Aanpassingen aan de communicatiestructuur

Bij de Radio Turrets kan elke robot met elke andere robot communiceren. Als er druk dataverkeer is, kunnen er boodschappen met elkaar botsen, waardoor de boodschap moet herverzonden worden. Het aantal botsingen stijgt kwadratisch [12] met het aantal robots, zodat er bij een groot aantal al vlug een verzadiging van het medium zal zijn met herverzonden boodschappen. Om dit op te vangen zijn in principe twee denkpistes mogelijk. 1. CSMA/CD: Carrier Sense Multiple Access with Collision Detection 2. TDMA: Time Division Multiple Access CSMA/CD Dit principe wordt onder andere gebruikt in het ethernet protocol [13]. Als een robot een boodschap wil versturen, zal hij luisteren of een andere robot aan het zenden is. Als dit zo is, zal hij zelf wachten met zenden tot niemand anders nog zendt. Het kan gebeuren dat twee robots tegelijk opmerken dat het medium vrij is zodat ze beide tegelijk proberen te zenden. Ze zullen dan echter opmerken dat hun boodschappen door elkaar verstuurd zijn en zullen daaruit besluiten om een zekere tijd te wachten alvorens nogmaals te proberen de boodschap te versturen. Deze tijd is random maar kleiner dan een ingestelde bovengrens. Botsen de boodschappen nog eens, dan zullen ze dit keer langer wachten alvorens opnieuw te proberen. Deze wachttijd bij herhaalde botsingen wordt exponentieel langer, zodat men spreekt van exponential back-off. De wachttijden zijn random om ervoor te zorgen dat één robot eerst zal beginnen zenden en de anderen, die zien dat deze ene robot eerst was, zullen wachten tot hij klaar is met zenden. Met de bestaande Radio Turrets valt niet te achterhalen of boodschappen gebotst zijn. Het strikt toepassen van CSMA/CD is in dit geval dus niet onmiddellijk mogelijk. De exponential back-off kunnen we echter wel implementeren door bij een time-out steeds langer en een willekeurige tijd te wachten vooraleer opnieuw te zenden. Bij een communicatie met drie robots blijkt dit bij weinig verkeer nog niet nodig te zijn, omdat time-outs niet voorkomen en ook bij druk verkeer konden alle robots nog blijven communiceren aan een redelijke snelheid. Als het aantal robots zou verhogen, kan dit ge¨ımplementeerd worden om de bestaande communicatie te verbeteren.


47

TDMA In referentie [12] vinden we nog een andere manier om robots niet tegelijk te laten zenden. Hierbij wordt de tijd opgedeeld in tijdslots op zo’n manier dat slechts één robot mag zenden en de andere enkel mogen luisteren tijdens elk tijdslot. Er zijn twee verschillende manieren om te bepalen wie wanneer mag sturen: • Polling Deze eerste manier is te zien in figuur 2.9. In deze configuratie is er één master die de robots één voor één afgaat, zodat deze elk om beurt mogen zenden. Het toevoegen en wegvallen van robots aan de ring wordt enkel aan de master toevertrouwd. Deze configuratie heeft als nadeel dat er een master in het spel is. Hoewel deze masterrol niet statisch hoeft te zijn en kan worden doorgegeven, is het een stap terug van gelijkwaardige robots. De master maakt het geheel kwetsbaar. Er kan natuurlijk een veiligheidsmechanisme ingebouwd worden dat de andere robots na een bepaalde tijd van radiostilte doet besluiten dat de master weg is en er dus een nieuwe moet gekozen worden. Bij grote groepen kan het heel lang duren voor een robot weer aan beurt is. Om dit te verhelpen kan de grote groep in subgroepen ingedeeld worden met elk een master, terwijl de masters onderling ook een groep vormen. Deze laatste groep zal dan opnieuw een master hebben en zo kan een piramide opgebouwd worden van groepen. De verschillende subgroepen kunnen elkaars radioverkeer natuurlijk be¨ınvloeden als ze in elkaars buurt staan. Om de piramide praktisch te realiseren zou elke subgroep een andere frequentie kunnen gebruiken. • Virtual Token Ring De tweede aanpak is te zien is in figuur 2.10. In dit geval is er een token dat wordt doorgegeven van robot naar robot. Enkel wanneer iemand het token heeft, mag hij zenden. Het concept is analoog aan dat van polling, maar de rol van een delegerende master wordt nu grotendeels overgenomen door het token. Toch is ook hier een master nodig, omdat er maar één token mag zijn en er ook maar één robot voor het eerst het token mag aanmaken en versturen. Als een token verloren gaat, mag er ook slechts één robot dit opvangen en een nieuw token maken. Het toevoegen en wegvallen van robots aan de ring wordt ook hier aan de master toevertrouwd. Net zoals bij polling moet het wegvallen van de master door de andere robots gezamenlijk opgevangen worden. De virtual token ring is iets flexiber dan polling, maar in essentie staat de master bij virtual token ring gewoon in de kring in plaats van erbuiten. Bij grote groepen kan de wachttijd voor elke robot onaanvaardbaar groot worden en zal er naar andere oplossingen gezocht moeten worden. Het idee van de subgroepen kan ook hier een interessant pad zijn om alles schaalbaar te houden.


48

Figuur 2.9: Communicatie via polling

Figuur 2.10: Communicatie via een virtual token ring

Hoofdstuk 3

Sonar Turret Inhoudsopgave

3.1

3.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.2

SRF05-module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

3.3

Extensieturret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

3.4

PIC16F877A-microcontroller . . . . . . . . . . . . . . . . . . . . . . . .

52

3.5

Het PCB van de Sonar Turret . . . . . . . . . . . . . . . . . . . . . . . .

53

3.6

Code voor de microcontroller . . . . . . . . . . . . . . . . . . . . . . . .

57

3.7


. . . . . . . . . . . . .

61

3.8

Evaluatie van de Sonar Turret . . . . . . . . . . . . . . . . . . . . . . . .

63

3.9

Nieuw ontwerp Sonar Turret (Rev. 1) . . . . . . . . . . . . . . . . . . .

64

Inleiding

In dit hoofdstuk wordt de ontwikkeling beschreven van de Sonar Turret voor de Khepera II. Deze turret werd ontwikkeld om nauwkeurige afstandsmetingen te kunnen maken. Vooreerst wordt de gebruikte SRF05-sonarmodule besproken. Vervolgens wordt ingegaan op de mogelijkheden die de Khepera II biedt om extensieturrets te creëren. Daarna bespreken we de microcontroller die de SRF05-modules zal aansturen. Ten slotte overlopen we het gerealiseerde PCB1 , de code ontwikkeld voor de microcontroller en de robot en maken we ook een evaluatie van de Sonar Turret.

3.2

SRF05-module

De SRF05-sonarmodule (Fig. 3.1) werd speciaal ontwikkeld voor minirobot-toepassingen en heeft als belangrijkste voordelen een laag vermogenverbruik, een hoge resolutie, kleine afmetingen en een lage kostprijs. 1

PCB = Printed Circuit Board

49

Hoofdstuk 3. Sonar Turret

50

Figuur 3.1: De SRF05-module

De module bestaat uit een ultrasone sensor (verzender en ontvanger), enkele analoge componenten en een eenvoudige microcontroller. Het starten van de module gebeurt door een hoge puls (10µs, 5V) aan te leggen aan de Trigger Input-pin (figuur 3.1). Vervolgens zal de module een ultrasone puls uitsturen en zet hij de Echo Output-pin hoog (5V). Daarna wacht de module op de echo van de ultrasone puls en zet hij, wanneer deze echo ontvangen wordt, de Echo Output-pin terug laag (0V). De tijdsduur dat de Echo Output-pin hoog was, is dan evenredig met de afstand tot het gedetecteerde object.

3.3

Extensieturret

De Khepera II is modulair opgebouwd. Dit wil zeggen dat de robot aangepast/uitgebreid kan worden met behulp van zogenaamde extensieturrets. Dit zijn kleine PCB’s die bovenop de Khepera II passen en die een bijkomende functionaliteit geven aan de robot. De communicatie tussen de robot en de extensieturrets gebeurt door middel van pinnen die zich bevinden onder elke turret en die connecteren op de turret/robot eronder [14, sectie 2]. Er zijn twee mogelijkheden om zulke turrets te ontwikkelen voor de Khepera II : • Parallelle Turret Dit soort turrets maakt gebruik van acht digitale I/O2 -pinnen, drie analoge I-pinnen, zes adres-pinnen en twee pinnen voor asynchrone communicatie. Wanneer de robot een commando (via acht digitale I/O-pinnen) schrijft naar een bepaald adres (via de zes adres-pinnen), vergelijken alle aanwezige parallelle turrets dat adres met hun eigen (voorgeprogrammeerde) adres en weten op die manier of het commando voor hen bedoeld is. Dit is een eenvoudig principe dat toelaat zeer snel extensieturrets te ontwikkelen. • Seri¨ ele Turret Dit soort turrets maakt gebruik van de KNET-bus [15]. Die is gebaseerd op de SPI-bus3 en beschikt over zes pinnen om te communiceren: 2 3

I/O = Input / Output SPI = Serial Peripheral Interface


51

Figuur 3.2: De KNET-bus met (a) alle turrets in slaaptoestand (b) één turret in actieve toestand

1. /CS COM (standard SPI signal) Chip select 2. SCK (standard SPI signal) Clock 3. MOSI (standard SPI signal) Master Out Slave In 4. MISO (standard SPI signal) Master In Slave Out 5. /F7 (additional signal) Communication request 6. PAI (additional signal) Acknowledge Wanneer verschillende seriële turrets aanwezig zijn op de Khepera II, krijgen we een structuur zoals in figuur 3.2a. Alle turrets bevinden zich initieel in slaaptoestand. Wanneer de robot iets wil sturen naar één van de turrets, stuurt hij een lage puls (1µs, 0V) naar pin F7 en vervolgens het adres van de turret die hij wil aanspreken via de seriële pin MOSI. Wanneer de juiste turret dit ontvangt, configureert hij zijn MISO- en PAI -pin als outputpin (zie Fig. 3.2b, slave #1); alle andere turrets blijven in hun slaaptoestand. Vanaf dat moment communiceert de robot (voor dit bericht) enkel nog met die ene turret. Deze communicatie tussen de master en een slave gebeurt altijd in twee fasen: – De master stuurt een bericht (opdracht) naar de slave. – De slave verwerkt dit bericht en stuurt een antwoord hierop terug naar de master. De toestand van de verschillende pinnen van de KNET-bus gedurende deze communicatie is te zien in figuur 3.3 waarbij we nog opmerken dat elke verstuurde byte van de robot acknowledged moet worden door de turret via een puls op de PAI -pin en elke te versturen byte naar de robot voorafgegaan wordt door een puls op diezelfde PAI -pin.


52

Figuur 3.3: De toestand van de KNET-bus gedurende de communicatie met een slave

Wanneer het bericht naar de master verstuurd is, keert de slave terug naar zijn slaaptoestand en wacht op de volgende puls op pin F7. Ons eerste idee was te kiezen voor een parallelle turret. Die zou dan rechtstreeks de Trigger Input-pinnen van de drie4 SRF05-modules aansturen en de breedte van de puls op de Echo Output-pinnen meten. Helaas bleek de timerfunctie op de robot een te kleine resolutie te hebben zodat een bijkomende microcontroller voor het meten van de duur van de puls onvermijdelijk was. Er werd dan overgegaan op het principe van seriële turrets, omdat het terugsturen van data vanop de turret via een parallelle turret niet eenvoudig is. Een bijkomend voordeel aan seriële turrets is dat de commando’s op de robot zelf zeer eenvoudig blijven (cfr. paragraaf 3.7). Het nadeel is dat op de microcontroller van de turret het volledige seriële KNET-busprotocol ge¨ımplementeerd moet worden, wat niet zo eenvoudig bleek te zijn (cfr. paragraaf 3.6).

3.4

PIC16F877A-microcontroller

Als microcontroller werd gekozen voor de PIC16F877A. Daar zijn twee redenen voor. Ten eerste is de PIC16F877A één van de weinige microcontrollers die het SPI-busprotocol in slave-mode ondersteunt. Slave-mode houdt in dat de microcontroller niet zelf het kloksignaal aanmaakt, maar afhankelijk is van het kloksignaal dat de master verstuurt (Fig. 3.2). De tweede reden om voor deze microcontroller te kiezen is het feit dat de onderzoekers bij K-Team Corporation ervaring hebben met deze microcontroller en zelfs reeds code geschreven hebben om vanuit de Khepera II te communiceren met deze microcontroller. Bijkomende features van de microcontroller zijn onder andere 33 I/O-pinnen, ondersteuning van kristallen tot 20 MHz, in-circuit seriële herprogrammering, 8-bit en 16-bit timers. Een kristal van 20 Mhz in samenwerking met de 16-bit timers laat toe om een zeer nauwkeurige tijdsduurmeting uit te voeren. 4

één om links te scannen, één om rechts te scannen en een derde om recht voor de robot te scannen


53

Figuur 3.4: PCB-layout van de Sonar Turret

3.5

Het PCB van de Sonar Turret

In figuur 3.4 is het layout-ontwerp van de Sonar Turret te zien. We hebben gekozen voor een tweezijdig PCB omdat er relatief veel signalen over het PCB gerouteerd moesten worden. Op een enkelzijdig PCB kunnen signaallijnen elkaar nooit kruisen (omdat dit tot kortsluiting zou leiden); op een dubbelzijdig PCB kan men echter zowel op de onderkant (blauwe lijnen in figuur 3.4) als op de bovenkant (rode lijnen in figuur 3.4) signaallijnen routeren zodat een densere structuur mogelijk is. Centraal in figuur 3.4 is de microcontroller te zien die aangestuurd wordt met het kristal van 20 MHz. Uiterst links en rechts en helemaal bovenaan bevinden zich de connectoren voor de SRF05-modules. Links onderaan bevindt zich de ICSP-connector (nodig om de microcontroller te programmeren) en links bovenaan een circuit om de microcontroller te resetten.

3.5.1

Aanpassingen

Bij de eerste tests met de Sonar Turret bleek al snel dat de SRF05-modules zeer nauwkeurige afstandsmetingen toelaten. De afstandsmetingen geven ook steeds nagenoeg hetzelfde resultaat wanneer eenzelfde afstand gemeten wordt. Dit is een groot voordeel ten opzichte van andere sensoren die vaak te kampen hebben met ruisproblemen. Toch bleken nog enkele aanpassingen noodzakelijk om de Sonar Turret ten volle te kunnen gebruiken in onze situatie. Deze


54

Figuur 3.5: Khepera II met Sonar Turret (bovenaan), High Speed Radio Turret en Radio Turret (onderaan)

aanpassingen worden besproken in de volgende paragrafen. Onregelmatige vorm In de eerste plaats willen we de Sonar Turret gebruiken om de afstanden tot andere robots te meten. In een ideale situatie, waarbij de ultrasone bundel zo smal zou zijn dat hij als een straal kan worden beschouwd en waarbij de robot een perfecte cilinder zou zijn (zie figuur 3.6), zouden de afstandsmetingen tot de robot het kleinst zijn als de bundel er recht op invalt. Hoe meer de straal dan op de zijkant van een robot invalt, hoe groter de gemeten afstand zal zijn. Door de smalheid van de bundel, zal de bundel echter al snel weerkaatsen op zo’n manier dat de sensor geen echo meer kan opmeten, waardoor de andere robot dus ook niet meer gedetecteerd kan worden (cfr. tweede situatie in figuur 3.6). In dit ideale geval zal de robot dus vanuit elke richting dezelfde meetwaarden geven (op voorwaarde dat de afstand tussen beide robots dezelfde blijft) over de hoek waarin de ultrasone sensor van de andere robot hem kan detecteren. In de praktijk is dit helaas niet zo. De robot heeft een zeer onregelmatige vorm (grotendeels door de Sonar Turret (figuur 3.5) bovenop de robot). Daardoor detecteren de robots elkaar als een onregelmatige kromme, en niet als een cirkelboog. Dé afstand van één robot tot een andere robot bleek dus niet gedefinieerd. Uit experimenten met formatievormingsalgoritmes (hoofdstuk 5), is gebleken dat het feit dat een robot als een onregelmatige kromme werd gedetecteerd een probleem was dat we dienden op te lossen. We zijn dan op zoek gegaan naar een soort cilinder die we rond de robot met Sonar Turret konden monteren opdat de robot als een cirkelboog zou kunnen worden gedetecteerd. Dit werd uiteindelijk uitgevoerd door een PVC-buis rond de robot te plaatsen en te bevestigen aan de ultrasone sensoren.


55

Figuur 3.6: Opmeten van een andere robot in het geval van ideale ultrasone sensoren en behuizing van de robots.

Bundelbreedte In figuur 3.7 is een illustratie te zien van de vorm van de ultrasone bundel die de ultrasone sensoren uitsturen. De ultrasone sensoren van de SRF05-modules ‘kijken’ dus niet enkel in de richting waarin ze meten, maar detecteren ook objecten die zich in de buurt van deze richting bevinden. Dit zorgt voor een grote hoek waarover objecten gedecteerd worden door de ultrasone sensoren. Ook dit leek ons een probleem dat we moesten aanpakken. Daarom brachten we smalle PVC-buisjes aan rond de ultrasone sensoren met een lengte die ongeveer dubbel zo lang is als de lengte van een ultrasone sensor. De gehele binnenkant van de buisjes bedekten we met Velcro. De reden waarom dit de bundelbreedte verkleint, is de volgende. Een deel van de ultrasone bundel verlaat de ultrasone sensoren onder een bepaalde hoek5 . Wanneer die ultrasone golf de Velcro bereikt voor het de PVC-buis kan verlaten, zal die golf geabsorbeerd worden door de Velcro. Velcro heeft namelijk een heel onregelmatige structuur zodat de invallende golf onmiddellijk verschillende keren gereflecteerd wordt, waarbij telkens een groot deel van de energie geabsorbeerd wordt. Bijgevolg zal enkel dát deel van de uitgestuurde ultrasone bundel de uitgang van de PVCbuisjes bereiken, dat onder een voldoende kleine hoek vertrekt uit de ultrasone sensoren. Een afbeelding van de Sonar Turret na het aanbrengen van de hierboven vermelde aanpassingen is te vinden in figuur 3.8. Verloren echo’s Na het aanbrengen van de verschillende PVC-buizen, werden nieuwe sonarmetingen uitgevoerd, waarbij we trachtten te bepalen over welke hoek een robot een andere robot detecteert. Een 5

Dit deel van de ultrasone bundel maakt dus een hoek ten opzichte van de hoofdrichting waarin de sensor meet


Figuur 3.7: Bundelbreedte van SRF05-modules

Figuur 3.8: De Sonar Turret met aanpassingen voor nauwkeurige sonarmetingen

56


57

probleem dat tijdens deze tests aan het licht kwam, was het probleem van de echo’s die verloren gaan. Wanneer een robot een ultrasone bundel uitstuurt en deze bundel komt in een smal PVC-buisje (dat met Velcro bedekt is) van een andere robot terecht, dan wordt deze bundel geabsorbeerd en zal de robot die aan het meten is, denken dat er geen object in de buurt is. Dit is een probleem dat niet opdook vóór de aanpassingen en een logisch gevolg van het aanbrengen van de PVC-buisjes met Velcro. We lossen dit op door in dit geval de robots onderling te laten afspreken wie wie zal meten en we laten de robot die opgemeten wordt met zijn achterkant (waar geen PVC-buisjes aanwezig zijn) naar de andere draaien. We zullen dit dan ook consequent toepassen in de algoritmes die we ontwikkelen waarbij afstanden tot andere robots moeten worden gemeten (en waarbij we kennis hebben over de positie van de andere robots).

3.6

Code voor de microcontroller

Zoals reeds vermeld in paragraaf 3.4, werd de PIC16F877A gekozen omwille van de ervaring die aanwezig is bij K-Team Corporation met deze microcontroller. Er werd dan ook gestart van een template-C-file die we ontvingen van K-Team Corporation. Helaas bleek deze niet rechtstreeks bruikbaar in onze situatie en ook de mensen bij K-Team Corporation konden ons niet onmiddellijk verder helpen. De problemen situeerden zich vooral rond de communicatie tussen de Khepera II en de microcontroller. De KNET-bus bleek niet gedetailleerd beschreven en we hebben dan ook zelf uitgebreide tests uitgevoerd om te proberen de KNET-bus zo goed mogelijk te doorgronden om op die manier de communicatie in orde te krijgen. Tijdens dit proces zijn we ook van programmeertaal veranderd en hebben we de volledige code die we reeds hadden, herschreven in Assembler, omdat die dichter aanleunt bij de hardware en we dus meer controle hadden over wat er juist moest gebeuren op hardware-niveau. Toen het KNET-protocol naar behoren werkte op de microcontroller, werd ook code geschreven voor de aansturing van de SRF05-sonarmodules en ten slotte werd de code uitgebreid van commentaar voorzien. De volledige Assembler-code voor de PIC16F877A is te vinden op de bijgeleverde CD in de map Sonar Turret\PIC16877A”. ”

3.6.1

Algemene werking

In deze paragraaf geven we een schematisch overzicht van de Assembler-code waarmee de microcontroller geprogrammeerd is (zie ook Algoritme 3.1). • De code die zich bevindt voor het Main-label, zorgt ervoor dat de verschillende modules6 van de microcontroller correct geconfigureerd worden en dat alle variabelen die we verder zullen gebruiken ge¨ınitialiseerd worden. Ook de I/O-pinnen worden hier geconfigureerd7 . 6

timermodule, ADC-module, SPI-module,... (laatste twee worden besproken in paragraaf 3.6.2) Bij het configureren wordt bepaald of de pinnen als input of als output gebruikt zullen worden en wat hun initiële toestand (0V of 5V) is. 7


58

Algoritme 3.1 PIC16F877A 1: initialise variables 2: initialise modules 3: initialise I/O-pins 4: loop 5: Main label 6: while (pin B0 high) do 7: wait 8: end while 9: start SPI-module 10: wait for incoming byte (RXDAT A addr) via SPI-module 11: generate ACK on P AI-line 12: if (RXDAT A addr 6= correct turret address) then 13: discard message 14: else 15: wait for incoming byte (RXDAT A nr) via SPI-module 16: generate ACK on P AI-line 17: wait for incoming byte (RXDAT A len) via SPI-module 18: generate ACK on P AI-line 19: wait for incoming byte (RXDAT A comm) via SPI-module 20: generate ACK on P AI-line 21: if (RXDAT A comm == ’S’) then 22: send ’s’ to SPI-buffer 23: generate ACK on P AI-line 24: trigger SRF05-modules and measure echo-time with 16-bit timer-module 25: save each 16-bit timer-value in 2 bytes (T XDAT A lowX and T XDAT A highX where X is replaced by the direction of the measured SRF05-module) 26: else if (RXDAT A comm == ’F’) then 27: send ’f’ to SPI-buffer 28: generate ACK on P AI-line 29: send (T XDAT A lowlef t) XOR (T XDAT A highlef t) via SPI-module 30: generate ACK on P AI-line 31: send T XDAT A lowlef t via SPI-module 32: generate ACK on P AI-line 33: send T XDAT A highlef t via SPI-module 34: generate ACK on P AI-line 35: else if (RXDAT A comm == ’G’) then 36: send ’g’ to SPI-buffer 37: generate ACK on P AI-line 38: send XOR of T XDAT A-values 39: send T XDAT A-values for front sonar measurement 40: else if (RXDAT A comm == ’H’) then 41: send ’h’ to SPI-buffer 42: generate ACK on P AI-line 43: send XOR of T XDAT A-values 44: send T XDAT A-values for right sonar measurement 45: end if 46: end if 47: stop SPI-module 48: end loop


59

• De code die zich na het Main-label bevindt, zal sequentieel en cyclisch doorlopen worden tot de voeding wegvalt of de microcontroller gereset wordt. De code begint met het pollen 8 van de B0 -pin (deze is verbonden met de F7 -pin van de Khepera II ). Dit gebeurt in een lus die wacht tot de B0 -pin laag (0V) komt. Vervolgens wordt de SPI-module geactiveerd en wordt in een volgende lus gewacht tot de BF -bit, die aangeeft dat een nieuwe byte van de robot ontvangen is, ’1’ wordt. De eerst verzonden byte door de robot bevat het turretadres en we controleren of deze byte het correcte turretadres bevat. Indien dit niet het geval is, wordt de SPI-module gedeactiveerd en wordt er opnieuw naar het Main-label gesprongen. Als het turretadres wel correct is, wordt gewacht tot de volgende byte ontvangen is. Op dezelfde manier worden alle bytes van het bericht, afkomstig van de robot, ingelezen en weggeschreven. We merken hierbij op dat, overeenkomstig het voorgeschreven KNET-busprotocol, elke ontvangen byte acknowledged wordt via een puls op de A3 -pin (die verbonden is met de PAI -pin van de Khepera II ). • Enkel de laatst ontvangen byte is echt belangrijk want die bevat het eigenlijke commando voor de turret9 . Alle mogelijke commando’s worden dan ook één voor één gecontroleerd en wanneer er één overeenkomt met het ontvangen commando, worden de overeenkomstige opdrachten uitgevoerd. Die opdracht kan het opstarten van een sonarmeting zijn of het doorsturen van de opgemeten data. In het geval van een sonarmeting (commando ’S’), worden de SRF05-modules sequentieel getriggerd en de duur van de echo-pulsen wordt opgemeten. Het opmeten van die duur gebeurt met behulp van de ingebouwde 16-bit timermodule. Die wordt achtereenvolgens: 1. gestart: ’1’ schrijven naar de T1CON -bit van het TMR1ON-register 2. gestopt: ’0’ schrijven naar diezelfde bit wanneer de echo ontvangen is 3. gereset: timer wordt terug op nul gezet • Om een byte terug te sturen naar de robot, maken we opnieuw gebruik van de ingebouwde SPI-module, waardoor we enkel de te versturen byte naar een welbepaalde geheugenlocatie hoeven te schrijven (SSPBUF) en de SPI-module ervoor zal zorgen dat deze byte bit per bit op een correcte manier verzonden wordt. Ook hier brengen we, overeenkomstig het KNET-busprotocol, een puls aan op de A3 -pin als we een byte willen verzenden. • Wanneer het antwoord verzonden is naar de robot, wordt ook hier de SPI-module gedeactiveerd en wordt teruggesprongen naar het Main-label, zodat gewacht kan worden op een volgend bericht van de robot.

3.6.2

Aandachtspunten

In deze paragraaf zullen we enkele punten bespreken die ons veel tijd gekost hebben in de ontwikkeling van de code. Het zijn vooral stukken code die betrekking hebben op de werking 8

pollen = inlezen en controleren De andere bytes, RXDAT A nr en RXDAT A len, staan respectievelijk voor het nummer van de boodschap (analoog aan het serienummer dat we bespraken in hoofdstuk 2) en de lengte van het bericht. 9


60

van het KNET-protocol en die op een andere manier werken dan beschreven in de oorspronkelijke template-file. We vermelden ze hier dan ook opdat de eventuele ontwikkeling van bijkomende extensieturrets in de toekomst eenvoudiger zou verlopen. SPI-module In paragraaf 3.3 bespraken we de algemene werking van het KNET-protocol. Alle aangesloten turrets bevinden zich in een slaaptoestand en wachten op een lage puls op de F7 -pin voor ze naar een nieuw inkomend bericht beginnen te luisteren. Deze berichten van de robot zullen we op de PIC16F877A ontvangen via de ingebouwde SPI-module. Deze module zorgt ervoor dat de opeenvolgende bits van een byte (8 bits), verstuurd via de SPI-pinnen naar de PIC16F877A, correct ingelezen worden op de klokflanken van het aangelegd kloksignaal. Eens de volledige byte ontvangen, wordt deze byte naar een geheugenlocatie op de microcontroller geschreven en wordt er een ’1’ geschreven naar de BF -bit in het SSPSTAT-register. Dit alles gebeurt op de achtergrond zodat de programmeur van de microcontroller enkel de BF -bit moet pollen om te controleren of een volledige byte ontvangen werd. De SPI-module moet helemaal in het begin10 geconfigureerd worden (bv. slave-modus selecteren), door een bepaalde bitconfiguratie naar het SSPCON-register te schrijven. Via dit SSPCONregister is het ook mogelijk de SPI-module te activeren of tijdelijk te deactiveren. Het is gebleken dat de communicatie tussen de robot en de microcontroller enkel werkt wanneer deze SPI-module geactiveerd wordt na het ‘zien’ van een lage puls op de F7 -pin én wanneer deze SPI-module onmiddellijk wordt gedeactiveerd na het ontvangen van een bericht. SDO-pin In figuur 3.2(a) is te zien dat alle pinnen geconfigureerd moeten zijn als input11 als de microcontroller zich in de slaaptoestand bevindt. Enkel wanneer het correcte turretadres ontvangen wordt, zal de microcontroller de SDO12 - en PAI-pin als output configureren. In de template-file waarover we het reeds hadden in paragraaf 3.6 en die we ontvingen van K-Team Corporation, wordt de SDO-pin echter van in het begin als output geconfigureerd. Oorspronkelijk was dit ook bij ons zo, maar dit bleek een probleem wanneer er nog een andere extensieturret (bv. de Radio Turret) werd aangesloten op de robot. De oorzaak hiervan was de volgende: aangezien de SDOpin van de Sonar Turret geconfigureerd was als output-pin, bleek deze elektrisch verbonden te zijn met de voeding. De SDO-pin van de Sonar Turret komt echter samen met de SDO-pin van de andere turret(s) en deze lijn vormt het MISO-signaal voor de robot. Wanneer deze andere turret nu informatie wou verzenden naar de robot, probeerde de robot deze bits te lezen van de MISO-pin. De robot las echter enkel ’1’-en omdat de MISO-pin via de Sonar Turret verbonden was met de voeding. 10

bij het opstarten en na een reset van de microcontroller Op elektrisch niveau wil dit zeggen dat deze pin noch aan de voeding, noch aan de grond hangt, maar een open-keten (hoge impedantie) vormt voor de buitenwereld 12 De SDO-pin op de microcontroller is verbonden met de MISO-pin van de Khepera II. 11


61

De code voor de microcontroller werd dan ook zo aangepast dat de SDO-pin in slaaptoestand als input-pin fungeert. Hierdoor werd het probleem opgelost. ADC-module Een laatste struikelblok situeerde zich bij het inlezen van de SRF05-modules, meer bepaald de linkse module. De Echo Output-pin van deze module is verbonden met de A5-pin van de microcontroller. Deze A5-pin is echter ook verbonden met de ingebouwde A/D13 -converter en om van deze pin een digitale I/O-pin (nodig om de SRF05-module uit te lezen) te maken, moeten we deze ingebouwde A/D-converter deactiveren. Dit gebeurt door helemaal in het begin van de code een welbepaalde bitconfiguratie naar het ADCON1-register te schrijven.

3.7


Zoals vermeld in paragraaf 3.3 is het aansturen van de Sonar Turret erg eenvoudig door gebruik te maken van het principe van een seriële turret. Er zijn wel enkele controlemechanismen ingebouwd, zodat men er steeds van kan uitgaan dat de microcontroller wel degelijk het correcte commando ontvangen heeft en dat de data die de robot inleest, de data is die de microcontroller verstuurd heeft. Een voorbeeld van zo’n veiligheidsmechanisme is het feit dat de robot controleert of het eerst ontvangen karakter van de microcontroller correct is. Het is namelijk zo dat elk commando volgens het KNET-protocol moet worden beantwoord met de ascii-code van het commando, maar dan als kleine letter (het commando zelf is meestal een hoofdletter). Indien de ontvangen letter niet overeenkomt met het verstuurde commando, wordt het commando opnieuw verstuurd. Bij het versturen van de opgemeten data (commando’s ’F’, ’G’ en ’H’) wordt voor de opgemeten data nog een extra byte meegestuurd vanop de microcontroller die een logische combinatie (XOR14 ) is van de andere twee verzonden bytes. Hiermee kunnen we controleren of het uitvoeren op de robot van de logische functie op de laatste twee ontvangen bytes hetzelfde resultaat geeft als de ontvangen eerste (extra) byte. Ten slotte zorgen we er ook voor dat de Radio Turret niet aangesproken wordt tijdens de sonar(direction)-functie (algoritme 3.2), omdat dit soms tot ongewenste resultaten kan leiden. Tijdens het testen werden bijvoorbeeld onbestaande boodschappen via de Radio Turret ontvangen wanneer de Sonar Turret aangesproken werd. Dit afspreken tussen de turrets gebeurt met behulp van de sonarRequest-variabele. Wanneer die door de sonar(direction)-functie op ’1’ wordt gezet, zal het proces dat instaat voor het ontvangen van boodschappen via de Radio Turret dit opmerken en stoppen met het controleren van de Radio Turret tot deze sonarRequestvariabele opnieuw ’0’ wordt. De C-code is te vinden op de bijgeleverde CD in de map Sonar Turret\C-code”. ” 13 14

A/D = Analoog-naar-Digitaal De XOR-operatie geeft true enkel en alleen als slechts één (en niet meer) van de operandi true is.


62

Algoritme 3.2 De sonar(direction)-functie op de Khepera II 1: error = 0 2: sonarRequest = 1 3: mess[2] = ’S’ 4: reserve channel 5: send command (mess) to turret and wait for answer (ans) 6: while (error sending OR ans[0]!=’s’) do 7: release channel 8: reset MSG-module (module for communicating with turrets) 9: reserve channel 10: send command to turret and wait for answer 11: end while 12: release channel 13: reset MSG-module 14: if (direction == 0) then 15: mess[2] = ’F’ 16: reserve channel 17: send command (mess) to turret and wait for answer (ans) 18: retry = 0 19: while (error sending OR ans[0]!=’f’ OR ans[1]!=(ans[2] XOR ans[3])) AND (retry < 25)) do 20: release channel 21: reset MSG-module (module for communicating with turrets) 22: reserve channel 23: send command to turret and wait for answer 24: retry + + 25: end while 26: if (retry == 25) then 27: error = 1 28: end if 29: save received measured values in sonarLef t 30: release channel 31: reset MSG-module 32: else if (direction == 1) then 33: mess[2] = ’G’ 34: the rest is the same as with command ’F’, but save value in sonarF ront 35: else if (direction == 2) then 36: mess[2] = ’H’ 37: the rest is the same as with command ’F’, but save value in sonarRight 38: else if (direction == 3) then 39: get all measured values by sending the commands ’F’, ’G’ and ’H’ sequentially 40: end if 41: sonarRequest = 0 42: return error


63

Figuur 3.9: Reflectie van een ultrasone bundel op een schuine muur volgens de wet van de reflectie: θ1 = θ2

3.8

Evaluatie van de Sonar Turret

Zoals we reeds eerder vermeldden, laat de Sonar Turret ons toe om zeer nauwkeurige, ruisvrije afstandsmetingen te doen. Dit is een zeer groot voordeel ten opzichte van de ingebouwde infraroodsensoren en gaf het ons de mogelijkheid om formatievorming te verwezenlijken met de Khepera II -robots.

3.8.1

Nadelen van de Sonar Turret

Een nadeel van de Sonar Turret dat we reeds bespraken, is het feit dat andere robots niet met een SRF05-module mogen gericht zijn naar de robot die meet in hun richting (omdat echo’s zo verloren kunnen gaan). Dit is echter pas mogelijk als de robots elkaars positie voldoende nauwkeurig kunnen inschatten en dit is niet altijd het geval, zodat bijkomende veiligheidsmechanismen ingebouwd moeten worden. We kunnen bijvoorbeeld steeds ook enkele graden links en rechts van de te meten richting een afstandsmeting uitvoeren. Een tweede nadeel van de Sonar Turret zijn de onbetrouwbare resultaten indien we de afstand tot een schuine muur proberen te meten. We bedoelen hiermee een muur waarvan de richting niet loodrecht staat op de kijkrichting van de gebruikte SRF05-module. De verklaring hiervoor is eenvoudig. Wanneer een ultrasone bundel de schuine muur bereikt, zal die bundel gereflecteerd worden en het gereflecteerde deel in een richting vertrekken bepaald door de wet van de reflectie (zie figuur 3.9). Zoals ook te zien op deze figuur, zal de gereflecteerde bundel op die manier de sensor op de Sonar Turret niet meer bereiken. De Sonar Turret zal hieruit besluiten dat er zich geen object bevindt in de richting waarin we de meting uitvoerden, hetgeen niet correct is. Dit probleem wordt nog versterkt door de aanpassingen die we gemaakt hebben aan de Sonar Turret om de bundelbreedte van de uitgestuurde ultrasone bundel te verkleinen. Toch was het


64

aanbrengen van deze aanpassingen noodzakelijk voor een nauwkeurige afstandsmeting in een bepaalde richting en de aanpassing kon dus niet ongedaan gemaakt worden. Bijgevolg is het probleem van de detectie van schuine muren een probleem waarmee we rekening moeten houden, maar dat we niet kunnen vermijden. Het grootste nadeel echter van de Sonar Turret is de tijdsduur die een meting in beslag neemt: gemiddeld vijf seconden per afstandsmeting. Het is niet de meting zelf die zoveel tijd in beslag neemt, maar de communicatie tussen de Khepera II en de Sonar Turret via het KNETprotocol. Zoals reeds besproken in paragraaf 3.6, bleken er zeer veel vragen te bestaan rond de precieze werking van de KNET-bus. Ook al is de KNET-bus nu ge¨ımplementeerd zoals ze beschreven staat in [15], toch blijkt ze helemaal niet zo goed te werken als bij de turrets die K-Team Corporation zelf ontwikkelde en die ook voor dit onderzoek beschikbaar waren (nl. de Radio Turret). De communicatie tussen de Khepera II en de Sonar Turret verloopt zeer traag en veel boodschappen gaan verloren of worden vervormd. Het probleem kan niet bij de microcontroller (PIC16F877A) liggen, aangezien die ons aangeraden werd door K-Team Corporation. We vermoeden een storing op het PCB door bijvoorbeeld overspraak tussen naburige signaallijnen. Een andere mogelijkheid is dat er timing-verschil zit in het KNET-busprotocol dat door ons ge¨ımplementeerd werd in vergelijking met het protocol dat K-Team Corporation zelf implementeert voor de turrets die zij ontwikkelen en dat dit voor een probleem zorgt. Om dit uit te zoeken zouden opnieuw uitvoerige tests uitgevoerd moeten worden met de Sonar Turret, maar hiervoor ontbrak de tijd tijdens deze scriptie. Met de veiligheidsmechanismen (cfr. paragraaf 3.7) die we ingebouwd hebben, werkt de Sonar Turret - zij het zeer traag - en dus zijn we onmiddellijk begonnen met de implementatie van formatievormingsalgoritmes zonder uit te zoeken of we de Sonar Turret sneller konden maken. Een totaal andere mogelijkheid om de Sonar Turret sneller te maken is het herontwerpen van de Sonar Turret. Deze mogelijkheid zullen we bespreken in de volgende paragraaf.

3.9

Nieuw ontwerp Sonar Turret (Rev. 1)

In de eindfase van dit scriptieonderzoek hebben we nagegaan of bij het ontwerp van een nieuwe Sonar Turret de communicatie via de KNET-bus vermeden kan worden. De inspiratie hebben we gehaald bij de sonarsensor die ontworpen is voor de Koala II 15 [16]. Het versturen van de opgemeten data van de turret naar de robot verloopt dan niet via de KNET-bus maar via de ingebouwde analoog-naar-digitaal converter van de Khepera II. Voor de aansturing van de turret vanop de robot werken we in dit geval niet met het principe van seriële extensieturrets, maar met het principe van een parallelle extensieturret (paragraaf 3.3). Het principe van aansturing en uitlezing werkt als volgt. We starten een sonarmeting via het commando var_put_extension(adres, 0) op de Khepera II. De microcontroller leest het adres dat aangelegd wordt door de Khepera II en controleert welke sonarmodule aangestuurd moet worden. Elke sonarmodule (links, vooraan of rechts) komt overeen met een ander adres dat dient 15

De Koala II is een andere mini-robot die door K-Team Corporation ontwikkeld werd.


65

aangelegd te worden door de Khepera II. De microcontroller start dan de correcte SRF05-module (die hoort bij het aangelegde adres) en meet de duur van de puls op de Echo Output-pin van de SRF05-module. Om deze opgemeten data door te sturen naar de robot zet hij de opgemeten tijd nu eerst om naar een analoge waarde via een digitaal-naar-analoog converter (zie paragraaf 3.9.1). De analoge waarde die de opgemeten tijd voorstelt, wordt dan naar een pin gestuurd van de Khepera II die intern verbonden is met een analoog-naar-digitaal converter (CH3 -/CH4 /CH5 -pin). Deze (opnieuw gedigitaliseerde) waarde kan dan in de code van de robot gebruikt worden na het uitvoeren van de ingebouwde functie sens_get_ana_value(CH_X).

3.9.1

De MAX530 DAC

Een digitaal-naar-analoog converter is helaas niet aanwezig op de gebruikte PIC16F877A. Een eenvoudig te gebruiken converter die zeer snel kan worden aangestuurd door de microcontroller is de MAX530 van Maxim [17]. De MAX530 is een 12-bits precisie digitaal-naar-analoog converter met parallelle ingangen, zodat 4096 (12 bits) verschillende analoge waarden kunnen gegenereerd worden tussen 0V en 5V. De MAX530 beschikt over acht data-ingangen die toelaten om de 12 bits in slechts twee cycli (eerst de laagste acht bits, dan de hoogste vier bits) naar het geheugen van de DAC te schrijven. Na het aanleggen van een lage puls (4 µs, 0V) aan de LDAC-pin, wordt de analoge waarde die overeenstemt met deze 12 bits aan de uitgang van de DAC gegenereerd.

3.9.2

PCB van de vernieuwde Sonar Turret

In figuur 3.10 is het layout-ontwerp te zien van de nieuwe Sonar Turret. We hadden ervoor kunnen kiezen om bij het nieuwe ontwerp ook een extra SRF05-module te plaatsen die de robot toelaat om ook achter zich een afstandsmeting uit te voeren. Tijdens de ontwikkeling van enkele formatievormingsalgoritmes (zie hoofdstuk 5) is gebleken dat dit tijd kan besparen (omdat de robot zich dan niet in die richting hoeft te draaien). Toch bleek dit achteraf geen goed idee omwille van het probleem van de echo’s die verloren gaan (paragraaf 3.5.1). Stel dat we een vierde SRF05-module plaatsen om de robot toe te laten achter zich te meten, dan zou de robot die opgemeten wordt, zich al zeer precies moeten positioneren ten opzichte van de robot die aan het meten is om geen risico te lopen op een verloren gaande echo. Dit zou dan enkel mogelijk zijn indien de robots elkaars positie en oriëntatie perfect kennen en zoals zal blijken uit hoofdstuk 5 is dit niet altijd het geval. We zien in figuur 3.10 heel wat meer signaallijnen dan in het vorige ontwerp (figuur 3.4). Dit is in de eerste plaats te wijten aan de data- en controlelijnen waarmee we de DAC aansturen (rechtsboven op de figuur) en in de tweede plaats aan de adreslijnen die komen van de Khepera II en die we moeten inlezen om te detecteren wanneer de robot een sonarmeting wenst en in welke richting. Dit is een rechtstreeks gevolg van het werken met een parallelle extensieturret in plaats van een seriële extensieturret.


66

Figuur 3.10: PCB-layout van de Sonar Turret Rev. 1

3.9.3

Code voor de microcontroller

In deze paragraaf geven we een schematisch overzicht van de Assembler-code16 waarmee de nieuwe Sonar Turret moet worden geprogrammeerd (zie ook Algoritme 3.3). • De code die zich bevindt voor het Main-label, zorgt ervoor dat de verschillende modules van de microcontroller correct geconfigureerd worden en dat alle variabelen die we verder zullen gebruiken ge¨ınitialiseerd worden. Verder worden ook alle I/O-pinnen correct geconfigureerd. • De code die zich na het Main-label bevindt, zal sequentieel en cyclisch doorlopen worden tot de voeding wegvalt of de microcontroller gereset wordt. De code begint met het pollen van de B4 -pin (deze is verbonden met de CSExt-pin van de Khepera II ). Dit gebeurt in een lus die wacht tot de B4 -pin laag (0V) komt. • Vervolgens wordt het door de Khepera II aangelegde adres ingelezen en wegschreven naar de variabele RXADDRESS en deze wordt vergeleken met alle mogelijke adressen die overeenkomen met de verschillende SRF05-modules van de Sonar Turret. Zo zal het aanleggen van adres ‘16’ aanleiding geven tot een afstandsmeting in de linkerrichting, adres ‘17’ aanleiding geven tot een afstandsmeting in de riching recht voor de robot, enz. 16

De volledige code is te vinden op de bijgeleverde CD in de map Sonar Turret Rev 1\PIC16877A Rev 1”. ”


Algoritme 3.3 PIC16F877A Rev. 1 1: initialise variables 2: initialise modules 3: initialise I/O-pins 4: Main label 5: loop 6: while (pin B4 high) do 7: wait 8: end while 9: Read address (RXADDRESS) generated by the Khepera II 10: if (RXADDRESS == ’16’) then 11: trigger left SRF05-modules and measure echo-time with 16-bit timer-module 12: save 16-bit timer-value in 2 bytes (T XDAT A low and T XDAT A high) 13: goto sendValuesDAC 14: else if (RXADDRESS == ’17’) then 15: trigger front SRF05-modules and measure echo-time with 16-bit timer-module 16: save 16-bit timer-value in 2 bytes (T XDAT A low and T XDAT A high) 17: goto sendValuesDAC 18: else if (RXADDRESS == ’18’) then 19: trigger right SRF05-modules and measure echo-time with 16-bit timer-module 20: save 16-bit timer-value in 2 bytes (T XDAT A low and T XDAT A high) 21: goto sendValuesDAC 22: else 23: goto Main 24: end if 25: sendValuesDAC label 26: generate 4 highest bits for DAC 27: generate low pulse on W R/CS-pin of DAC 28: generate 8 lowest bits for DAC 29: generate low pulse on W R/CS-pin of DAC 30: generate low pulse on LDAC-pin of DAC 31: end loop

67


68

• De desbetreffende SRF05-module zal dan gestart worden via een puls (12 µs, 5V) op de Trigger Input-pin en de duur van de echo zal gemeten worden op de Echo Output-pin via de ingebouwde 16-bit timermodule. • Deze 16-bit waarde zal vervolgens omgezet worden naar een 12-bit waarde (omdat de MAX530 slechts een resolutie heeft van 12 bits) en zal in twee cycli geschreven worden naar de DAC. De conversie van 16-bit naar 12-bit kan op verschillende manieren gebeuren, zodat de range en resolutie van de Sonar Turret aangepast kunnen worden door de microcontroller te herprogrammeren. • Ten slotte wordt er een negatieve puls (4µs, 0V) gegenereerd op de LDAC-pin zodat de analoge waarde aan de uitgang van de MAX530 verschijnt.

3.9.4

Aansturing vanop de Khepera II

De aansturing vanop de Khepera II blijft ook nu eenvoudig. Door het oproepen van de ingebouwde functie var_put_extension(adres, 0), waarbij het adres de waarden 16, 17 of 18 kan aannemen, kunnen we een sonarmeting uitvoeren in de gewenste richting. Via de functie sens_get_ana_value(3) (De DAC is aangesloten op de CH3 -pin van de Khepera II, dus moeten we hier als argument 3” gebruiken), kunnen we dan de analoge waarde, die de duur van de echo ” voorstelt, inlezen. We dienen er wel rekening mee te houden dat deze twee functies niet te snel na elkaar uitgevoerd mogen worden, om de turret voldoende tijd te geven om de sonarmeting uit te voeren en de analoge waarde te genereren. Een tweede mogelijkheid zou zijn om een I/O-pin van de microcontroller te verbinden met bijvoorbeeld de CH4 -pin van de Khepera II en de microcontroller deze pin enkel hoog (5V) te laten zetten wanneer de analoge waarde (op CH3 ) klaar is om ingelezen te worden. De Khepera II kan dan door het pollen van deze CH4 -pin (via sens_get_ana_value(4)) controleren of hij al een nieuwe analoge waarde op CH3 mag inlezen.

Hoofdstuk 4

Formatiegedrag met IR-sensoren Inhoudsopgave 4.1

De IR-sensoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.2

Formatievorming: doelstellingen . . . . . . . . . . . . . . . . . . . . . .

71

4.3

Nieuwe aanpak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

4.4

Evaluatie

85

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

In dit hoofdstuk bespreken we de algoritmes die ontwikkeld werden voor formatievorming met behulp van de ingebouwde IR-sensoren. De C-code die deze algoritmes implementeert op de robot is te vinden op de bijgeleverde CD in de map Formation with IR sensors” ”

4.1

De IR-sensoren

De Khepera II robot heeft acht IR-sensoren die verdeeld zijn over de robot zoals te zien is op figuur 4.1. Er zijn twee opvallende zaken aan de verdeling. Ten eerste staan de zijsensoren niet loodrecht op de hoofdrichting, maar maken ze een hoek van ongeveer 80 graden met de hoofdrichting. De hoofdrichting is de richting die in figuur 4.1 aangeduid is met de zwarte pijl. Dat de zijsensoren niet loodrecht op de hoofdrichting staan, zal bepaalde zaken bemoeilijken zoals doelstelling 3 in paragraaf 4.2. Ten tweede is het zicht naar achter veel beperkter, omdat daar maar twee sensoren staan in tegenstelling tot de zes die naar voor gericht zijn. De plaatsing van de sensoren geeft aan dat de Khepera II beter geschikt is om een andere robot te volgen of zijn weg te zoeken in een labyrint dan om bijvoorbeeld parallel te rijden naast een andere robot.

4.1.1

Metingen met de IR-sensoren

De IR-sensoren kunnen metingen uitvoeren volgens twee principes: 1. Ambient light: Hierbij wordt de sterkte van de infraroodcomponent (λ = 950 nm) die aanwezig is in het omgevingslicht door de sensor gemeten .

69

Hoofdstuk 4. Formatiegedrag met IR-sensoren

70

Figuur 4.1: IR-sensoren op de robot

2. Reflected light: Hierbij wordt, naast het ambient light, ook de sterkte van een weerkaatste uitgestuurde IR-bundel gemeten en wordt de som van de twee opgemeten waarden teruggegeven. Het ambient light geeft enkel aan hoe sterk de IR-component is in het omgevingslicht. Deze informatie was voor ons onderzoek irrelevant en werd verder dan ook niet opgevraagd. De reflectiewaarden zijn een indicatie voor de afstand tot een voorwerp (verder besproken in paragraaf 4.1.2). We spreken af dat, als vanaf nu over de IR-waarden gesproken wordt, we daarmee de gereflecteerde waarden bedoelen. De details van de sensoren staan beschreven in referentie [7, paragraaf 3.1.6], maar het is vooral belangrijk om te weten dat de acht sensoren sequentieel worden aangestuurd en ingelezen en dat dit vanuit de software op de robot niet kan worden gestopt. Of de robot de IR-waarden nu opvraagt of niet, de sensoren zullen blijven meten. Beide zaken komen later in de scriptie aan bod, omdat ze de werking van de sensoren bepalen in aanwezigheid van andere robots.

4.1.2

Interpretatie van de metingen

De gereflecteerde waarden liggen steeds tussen 0 en 1023 (10 bit getal: 210 = 1024) en geven een heel ruwe indicatie over de afstand van de robot tot een object. Als er geen voorwerp in de buurt van de robot staat, is de waarde niet nul. Afhankelijk van de sensor kan dit tussen 60 en 120 liggen, maar dit is voor elke sensor anders. In figuur 4.2 is een grafiek te zien van de IR-sensorwaarden, uitgezet in functie van de afstand tot een andere robot. We zien dat de waarden van de sensoren pas beginnen oplopen als de robot een andere robot op minder dan 3 cm nadert. De gereflecteerde waarde op grote afstand valt niet op nul maar blijft, zoals eerder vermeld, in de buurt van 100. Dit zal vanaf nu de achtergrondruis genoemd worden. Wanneer een object


71

zich op meer dan 3 cm bevindt, kan de gereflecteerde waarde niet meer onderscheiden worden van de achtergrondruis. Dit toont meteen het beperkte bereik aan van de IR-sensoren. De gereflecteerde waarde bij een voorwerp op één cm is de hoogste in de grafiek. De reden hiervoor is dat de IR-sensoren in de behuizing van de Khepera II verwerkt zitten en dat deze behuizing helemaal onderaan iets breder is. Hierdoor zullen de IR-sensoren, wanneer twee robots perfect tegen elkaar staan met hun behuizing, altijd op een afstand van 1 cm van elkaar blijven. De reden waarom de grafiek daalt bij nog kleinere afstanden is ons niet geheel duidelijk, maar heeft hoogstwaarschijnlijk te maken met de aanstuurelektronica die achter de IR-sensoren zit.

Figuur 4.2: Detecteren van een andere robot

4.2

Formatievorming: doelstellingen

In referentie [6, Sectie 7.2.14] werden met de hulp van de IR-sensoren al verschillende algoritmes ontwikkeld. Een eerste is bedoeld om een robot een muur te laten volgen. Een tweede bevatte een kleine aanpassing waardoor dit algoritme ook kon gebruikt worden om twee robots naast elkaar te laten rijden1 . Dit algoritme bleek echter niet in alle situaties te werken, maar we hebben getracht om op deze resultaten verder te bouwen. Het voordeel van deze ingebouwde IR-sensoren is dat ze zeer snel opeenvolgende metingen kunnen uitvoeren waardoor formatievorming in real-time (terwijl de robots rijden) in principe mogelijk wordt. De eerstvolgende uitbreiding hierop die we zelf implementeerden, had betrekking op het parallel naast elkaar rijden. Twee robots zullen vanuit een willekeurige positie starten en elkaar op een bepaalde plaats ontmoeten. Onder de voorwaarde dat ze geen obstakels op hun pad naar 1

Hierbij fungeert elke robot dan als een soort van rijdende muur voor de andere.


72

elkaar tegenkomen, zullen ze elkaar detecteren en stoppen. Vervolgens zullen ze proberen zich zo te oriënteren dat ze beide in dezelfde richting ‘kijken’2 . Er moeten dus vier doelstellingen gerealiseerd worden: 1. Doelstelling 1: Naar elkaar toe rijden en stoppen. 2. Doelstelling 2: Afspreken in welke richting ze zullen draaien. 3. Doelstelling 3: Draaien in de afgesproken richting en stoppen wanneer de zijkant naar de andere robot gericht is. 4. Doelstelling 4: Parallel rijden naast elkaar volgens het muurvolgen-principe. Doelstellingen 1 tot 3 werden los van elkaar getest, waarbij we telkens het algoritme uitvoerden op één robot en waarbij een kartonnen doos of stilstaande robot, de andere robot in het algoritme voorstelde. Na het realiseren van de vier doelstellingen kan het idee uitgebreid worden naar drie robots.

4.2.1

Doelstellingen 1 en 4

De uitwerking van de eerste doelstelling werd reeds beschreven in referentie [6], waarbij de robots een muur moesten vinden. Van zodra de sensorwaarden een bepaalde drempel overschrijden, stopt de robot. Ook de vierde doelstelling werd in het onderzoek van referentie [6] gerealiseerd, zoals eerder vermeld.

4.2.2

Doelstelling 2

De robots spreken af in welke richting ze zullen draaien. Om deze doelstelling te bereiken is er nood aan communicatie tussen de robots en hiervoor wordt de communicatiestructuur gebruikt die we bespraken in hoofdstuk 2. Als de robots na doelstelling 1 elkaar vinden, zullen ze een boodschap naar elkaar sturen met de volgende gegevens: • Het nummer van de sensor die de grootste waarde heeft (enkel de voorste zes sensoren worden in rekening gebracht, omdat de robot vooruit rijdt om de andere robot te zoeken) • De waarde van die sensor zelf • Een randomwaarde Elke robot kent op dat moment niet alleen zijn eigen drie waarden, maar ook die van de andere robot. Via deze informatie kan op een eenduidige manier bepaald worden in welke richting de robots, volgens het algoritme, moeten draaien, opdat ze uiteindelijk zullen alligneren. We zullen er in dit algoritme voor zorgen dat wanneer twee robots elkaar vinden met de voorste sensoren, beide in een verschillende richting draaien om zich uiteindelijk in dezelfde 2

De kijkrichting is hier gelijk aan de hoofdrichting die we reeds bespraken in paragraaf 4.1.


73

richting te positioneren. Als de robots in dezelfde richting draaien, kunnen ze ook alligneren, maar dan zal de ene robot veel meer moeten draaien. Naast een verspilling van tijd, zou hierdoor de uitvoering van doelstelling 3 niet meer mogelijk zijn door de plaatsing van de zijsensoren, maar dit wordt verder verduidelijkt in paragraaf 4.2.3. Het draaien is te zien in figuur 4.3. Als ze beide in dezelfde richting willen kijken, zijn er maar twee mogelijkheden: naar onder of naar boven. Als ze naar boven draaien, volgens de gestippelde pijlen, moet de linkerrobot in tegenwijzerzin draaien en de rechter in wijzerzin. In het andere geval is de situatie omgekeerd en hun draairichtingen ook.

Figuur 4.3: Draairichtingen van de robots

Tabel 4.1: Draaitabel voor een robot met 2 sensoren

eigen Max Sensor

ander Max Sensor 2

3

2

-

-1

3

1

-

We hebben een draaitabel opgesteld die afhangt van de eigen sensor met maximale waarde en die van de ander. De waarde −1 staat voor het draaien in wijzerzin, de waarde 1 voor draaien in tegenwijzerzin. Deze tabel is dezelfde voor alle robots. Ze is anti-symmetrisch, zodat ze in een andere richting zullen draaien met elkaars informatie. Dit wordt eenvoudig ge¨ıllustreerd bij een robot die enkel de voorste twee sensoren (2 en 3) gebruikt in tabel 4.1. Als ze een verschillende sensor hebben die maximaal is (zie figuur 4.4), dan zullen ze in een tegengestelde richting draaien, net omdat de tabel anti-symmetrisch is. In het geval dat bij de linkerrobot sensor 2 maximaal is en bij de rechter sensor 3, dan zullen ze beiden naar beneden willen kijken, omdat ze zo het minst moeten draaien. Na het raadplegen van tabel 4.1 zal de linkerrobot inderdaad in wijzerzin (-1 in de tabel) draaien en de rechter in tegenwijzerzin (1 in de tabel). Als de beide robots dezelfde sensor hebben met een maximale waarde, zullen ze eerst kijken of hun eigen sensorwaarde groter is dan die van de ander. De robot met de grootste waarde zal in tegenwijzerzin draaien en de ander in wijzerzin. Er is echter ook een kleine kans dat beide dezelfde sensorwaarde hebben en daarom kan dezelfde test nog eens uitgevoerd worden op hun randomwaarde om in elke situatie uitsluitsel te brengen.


74

Figuur 4.4: Ontmoeting met verschillende maximale sensor

Bij de test werden de robots op voldoende kleine afstand van elkaar gezet, zodat ze elkaar meteen detecteerden. Na het uitwisselen van de boodschappen draaiden ze beide steeds in de goede richting. Dit afspreken is een typisch voorbeeld van hoe de communicatie voornamelijk gebruikt zal worden. Doelstelling 2 wordt nog eens schematisch weergegeven in algoritme 4.1 vanaf het moment dat de communicatieboodschappen uitgewisseld zijn en beide robots over elkaars gegevens beschikken.

Figuur 4.5: Situatie na het draaien

4.2.3

Doelstelling 3

Opdat de robots naast elkaar zouden staan, kunnen ze draaien op twee manieren: over een vast aantal graden of tot een zijsensor maximaal wordt. In het eerste geval moet exact geweten zijn onder welke hoek de robots elkaar zullen ontmoeten. Bij de tweede mogelijkheid is dit niet het geval en zal de robot zich met zijn zijkant naar de andere robot kunnen richten vanuit eender welke startpositie. We kiezen dan ook voor deze tweede optie. De robots draaien ter plaatse rond3 en lezen de waarde van hun zijsensor uit. Als die hogere waarden aanneemt, zal de robot met zijn zijkant meer naar het voorwerp toegekeerd zijn. Als de waarden weer dalen, zal de robot zich van het voorwerp wegdraaien zoals te zien is in figuur 4.6. Het komt er dus op neer om een maximum te detecteren. Op dat moment moet de robot 3

Dit wordt gerealiseerd door aan beide wielen een tegengestelde snelheid te geven.


75

Algoritme 4.1 Doelstelling 2 1: if (own sensor maximal 6= sensor other maximal) then 2: Look up direction of rotation in the table 3: else 4: if (value own sensor maximal < value sensor other maximal) then 5: Rotate clockwise 6: else if (value own sensor maximal > value sensor other maximal) then 7: Rotate counterclockwise 8: else if (value own sensor maximal == value sensor other maximal) then 9: if (own random value < random value other) then 10: Rotate clockwise 11: else 12: Rotate counterclockwise 13: end if 14: end if 15: end if stoppen en staat hij met zijn zijkant naar het voorwerp gekeerd. Het is een probleem dat de zijsensoren niet helemaal op de zijkant staan, maar een beetje naar voor, zoals reeds eerder vermeld. De robot zal bijgevolg voorbij het maximum moeten draaien tot de IR-waarden onder een zeker niveau gezakt zijn. Dit niveau kan absoluut of relatief gedefinieerd worden ten opzichte van het maximum. Als we figuur 4.6 doorlopen van boven naar onder, dan draait de robot in tegenwijzerzin. Links staan de robotposities ten opzichte van de muur en rechts een kwalitatieve illustratie van het verloop van de sensorwaarden van sensor 5.

Figuur 4.6: Verloop van een zijsensor bij een muur

In realiteit ziet de grafiek er niet zo glad uit als in figuur 4.6. De ruwe waarden bevatten


76

veel ruis, zoals te zien is in figuur 4.7. Maximum vinden in real-time Er zijn twee manieren om het maximum in real-time te vinden. De eerste manier (algoritme 4.2) bestaat erin om te controleren hoeveel een waarde kleiner is dan de vorige opgemeten waarde. Als dit verschil groter is dan een bepaalde ruisdrempel4 , kan aangenomen worden dat het maximum reeds bereikt werd en de waarden al weer aan het dalen zijn. Dit algoritme leverde in onze situatie geen consistente resultaten op. Soms draaide de robot niet ver genoeg door en soms te ver. De reden hiervoor is de ruis, die een plotse piek kan veroorzaken in het signaal, zodat het algoritme er vroegtijdig vanuit gaat dat het maximum bereikt werd. Het is bovendien belangrijk dat de zijsensoren niet loodrecht op de zijkant staan. Hierdoor moet de robot niet alleen voorbij het maximum draaien, maar de mate van doordraaien moet zeer precies zijn, opdat de robot steeds op dezelfde positie zou stoppen. Dit kon niet gerealiseerd worden door enkel twee opeenvolgende waarden te bekijken. Deze eenvoudige methode, weergegeven in algoritme 4.2, kan in deze situatie dus niet gebruikt worden. In het algoritme staat read new IR value() voor de functie die de laatste sensorwaarde opvraagt. Uit experimenten is gebleken dat de waarde 30 voor het verschil tussen twee opeenvolgende metingen een goede keuze is. Die moet groot genoeg zijn, zodat plotse ruisschommelingen het mechanisme niet triggeren en tegelijk mag deze waarde ook niet te groot gekozen worden, opdat een echte daling nog gedetecteerd zou worden. Algoritme 4.2 Maximum vinden in real-time: differentieel 1: current sensor value = read new IR value() 2: repeat 3: previous sensor value = current sensor value 4: current sensor value = read new IR value() 5: until ((previous sensor value - current sensor value) > 30 ) 6: Maximum reached ⇒ Stop robot! De tweede manier (algoritme 4.3) bestaat erin om zelf het maximum te bepalen door rekening te houden met alle reeds opgemeten IR-waarden. Dit kan door de waarde van een tijdelijk maximum steeds te verhogen als een sensorwaarde voorkomt groter dan het tijdelijke maximum. Deze waarde is dan het nieuwe maximum. Indien de sensorwaarden onder een fractie van dit maximum duiken, werd het maximum bereikt. Door de fractie te veranderen, kunnen we regelen hoeveel de waarden moeten zakken en hoeveel de robot dus nog doordraait na het detecteren van een maximum op zijn zijsensor. De onderste grafiek in figuur 4.6 illustreert deze aanpak. Als de fractie zo wordt gekozen dat het niveau overeenkomt met de rode stip, dan zal de robot stoppen bij de eerste sensorwaarde die kleiner is dan die rode stip. Algoritme 4.3 beschrijft het idee waarbij het stopniveau bepaald wordt door zowel de fractieparameter als het bereikte maximum. De fractieparameter moet zo gekozen worden dat de robot net genoeg doordraait om perfect gepositioneerd te zijn met zijn zijkant. 4

Dit is de maximale amplitude van de ruiscomponent die aanwezig is in het opgemeten signaal.


77

Het verder doordraaien om exact parallel te eindigen met het object naast de robot, heeft evenwel gevolgen op de te kiezen draairichting. Om de robot met zijn rechterzijde ergens naar toe te richten, wordt er gebruikt gemaakt van sensor 5. In dit geval moet de robot in tegenwijzerzin draaien zodat hij nog even verder zal draaien in tegenwijzerzin en zo net op zijn rechterzijkant zal eindigen. In het geval dat de robot zich met zijn linkerkant wil positioneren via sensor 0, moet hij in wijzerzin draaien. De ruis vormt bij deze manier van werken een aanzienlijk probleem, omdat de onzekerheid op het maximum en de fractie toeneemt, waardoor het moeilijk is de robot consequent op dezelfde plaats te laten stoppen. Daarom werd ervoor gekozen om de sensorwaarden in real-time uit te middelen. Algoritme 4.3 Maximum vinden in real-time: tweede methode 1: maximum = 0 2: f raction = 0.80 3: repeat 4: current sensor value = read new IR value() 5: if (current sensor value > maximum) then 6: maximum = current sensor value 7: end if 8: until (current sensor value < (f raction ∗ maximum)) 9: Maximum reached ⇒ Stop robot!

Uitmiddelen in real-time De ruwe sensorwaarden bij het draaien naar een voorwerp, worden weergegeven in figuur 4.7.

Figuur 4.7: Sensorwaarden zonder uitmiddeling al draaiend bij een voorwerp

Er zit een duidelijk lijn in de sensorwaarden die oplopen naarmate de robot zich meer draait in de richting van het voorwerp. We zien echter ook dat de sensorwaarden een belangrijke


78

ruiscomponent bevatten. De grootte van deze ruissprongen blijft normaal onder de 30, wat ook de waarde van het verschil verklaart tussen twee opeenvolgende waarden in algoritme 4.2. De tweede manier om het maximum te vinden (paragraaf 4.2.3) zou aanzienlijk betere resultaten opleveren met kleinere ruiscomponenten. Daarom werd ervoor geopteerd om de sensorwaarden uit te middelen met behulp van een Exponential Moving Average mechanisme [18]: EM A = ([sensorwaarde − EM A(vorig)] × gewicht) + EM A(vorig)

(4.1)

De mate waarin het lopend gemiddelde be¨ınvloed wordt door een nieuwe meetwaarde hangt af van de parameter ‘gewicht’. Een voorbeeld waarbij het EMA-mechanisme toegepast werd op een reeks IR-waarden, is te zien in figuur 4.8.

Figuur 4.8: Sensorwaarden met een lopend gemiddelde (i.c. parameter gewicht: 0.0645)

Dankzij het uitmiddelen werd doelstelling 3 veel betrouwbaarder uitgevoerd, zodat de robot bijna altijd met zijn zijkant parallel aan het voorwerp stopte. In de rest van dit hoofdstuk wordt dit EMA-principe dan ook op alle sensorwaarden toegepast. Het nadeel van EMA is dat de robot grote veranderingen in zijn sensorwaarden iets trager opmerkt, omdat het verleden een verzachtende invloed heeft op het EMA. Een voordeel is dat een veel kleinere stijging van de sensorwaarden al meteen mag ge¨ınterpreteerd worden als het naderen van een voorwerp. Het belangrijkste voordeel is echter het gladdere verloop, wat het makkelijker maakt om een marge in te stellen als er iets gedetecteerd moet worden.

4.2.4

Problemen bij de realisatie van de gezamelijke doelstellingen

De vier doelstellingen werkten naar behoren toen ze apart getest werden met een kartonnen doos of een uitgeschakelde robot. De volgende stap was het uittesten van de combinatie van de vier afzonderlijke algoritmes waarbij de robots recht tegenover elkaar gezet werden als startpositie,


79

zodat ze bij het recht vooruit rijden elkaar zeker zouden vinden. De testen verliepen echter niet helemaal zoals gepland. Vreemd genoeg ging het meestal al fout bij doelstelling 1. Dit is nochtans het meest eenvoudige programma, omdat de robot enkel moet rijden tot zijn sensorwaarden oplopen. De robots stopten vaak wanneer de afstand tussen hen beide nog veel te groot was. Na het herhaaldelijk uitvoeren van het experiment, bleek dat elk experiment tot één van de drie volgende klassen behoort: 1. De sensorwaarden lopen normaal op en de robots detecteren elkaar op zo’n 2 cm. 2. De sensorwaarden lopen sterk op wanneer de robots zich nog op grote afstand van elkaar bevinden en de robots stoppen bijgevolg te vroeg. 3. De sensorwaarden gaan naar nul, zodat de robots botsen. Het grote verschil met het testen van de aparte doelstelling was het feit dat we nu, bij het testen van het totale algoritme, telkens werkten met twee robots die hetzelfde algoritme uitvoerden. De problemen die opdoken, bleken dan ook de schuld te zijn van de tweede robot. Wanneer beide robots werken, voeren ze voortdurend metingen uit met hun IR-sensoren. Dit zorgde in ons geval voor be¨ınvloeding tussen de IR-sensoren van verschillende robots.

Figuur 4.9: Situatie waarbij sensoren elkaar kunnen be¨ınvloeden

De verklaring voor deze be¨ınvloeding is waarschijnlijk dat de IR-bundel van de ene robot op de IR-sensoren van de ander invalt en zo de waarden van de laatste be¨ınvloedt. De observatie in de voorgaande paragraaf laat uitschijnen dat het probleem niet zuiver van ruimtelijke aard is, aangezien het fenomeen soms niet opduikt als de robots recht naar elkaar toerijden hoewel er op die manier altijd een vorm van overlapping5 is. De zaken liggen dus iets subtieler, omdat de sensoren sequentieel gecontroleerd worden (paragraaf 4.1). Dit gebeurt om de 2.5 ms per IR-sensor, zodat om de 20 ms de acht sensoren gecontroleerd worden. Overlapping zal dus niet enkel ruimtelijk, maar ook in de tijd moeten gebeuren. Als de sensor van de ene robot een IR-bundel uitstuurt die op een sensor van de 5

Er zal altijd minstens één bundel van een bepaalde IR-sensor gericht zijn op een sensor van de andere robot.


80

ander terechtkomt op het moment dat de andere robot deze sensor net inleest, is de kans op be¨ınvloeding groot. Dit is te zien in figuur 4.9: de sensoren met groene stippen kunnen be¨ınvloed worden door een bundel afkomstig van de rechterrobot. Als het meten links en het sturen rechts tegelijk gebeurt, dan krijgen deze sensoren geen verzwakte gereflecteerde bundel binnen, maar wel één van de andere robot die enkel geattenueerd is door propagatie in lucht. Dit zal dan een hoger signaal opleveren dan verwacht, wat het oplopen van de sensorwaarden op grote afstand verklaart. Er is natuurlijk ook een kans dat op het moment dat een bundel invalt op een deel van de sensoren van een andere robot, deze robot andere sensoren aan het inlezen is, zodat er geen be¨ınvloeding is (afgebeeld in figuur 4.10: de vier sensoren die op dat moment ingelezen kunnen worden (met blauwe stip), liggen buiten het bereik van de inkomende bundel). Door het grotere aantal sensoren vooraan zal de kans dat de sensoren elkaar be¨ınvloeden wanneer ze recht op elkaar af rijden relatief groot zijn. Dit blijkt ook uit de experimenten, waarbij er een kans was van twee op drie dat er iets fout liep. Het onterecht dalen van de sensorwaarden is een heel stuk moeilijker te verklaren. De enige verklaring die we konden bedenken is de volgende. We weten dat het opmeten van een gereflecteerde waarde eigenlijk uit twee fases bestaat. In een eerste fase wordt het ambient light opgemeten en in een tweede fase wordt een IR-bundel uitgestuurd en wordt de gereflecteerde waarde opgemeten. De totale waarde is dan de som van de ambient light-waarde en de gereflecteerde waarde. Om het dalen van de totale waarde te verklaren, gaan we uit van het feit dat de ambient lightwaarde kleiner wordt naarmate er meer IR-licht aanwezig is. Wanneer er nu een IR-bundel op de sensor valt tijdens het opmeten van de ambient light-waarde, zal die dus naar nul gaan en zal bijgevolg ook de totale waarde naar nul gaan (waarbij we ervan uitgaan dat ook de gereflecteerde waarde zeer klein is, omdat er geen object in de buurt is).

Figuur 4.10: Situatie waarbij sensoren elkaar niet kunnen be¨ınvloeden


4.3

81

Nieuwe aanpak

In het voorgaande deel werd geschetst hoe de sensoren zowel in tijd als in ruimte moeten overlappen om be¨ınvloeding te krijgen. Eens de robot in een ongewenst regime zit, zal hij er normaalgezien in blijven, omdat de sensoren van de beide robots aan dezelfde snelheid gecontroleerd worden. Er bestaat echter een mogelijkheid om de robots vanuit de software te resetten, waarbij het mogelijk is dat de robot in een goed regime terechtkomt, omdat er geen overlapping in de tijd meer is. Dit komt overeen met de overgang van figuur 4.9 vóór het herstarten naar figuur 4.10 na het herstarten. Er is echter ook een kans dat de robot opnieuw in een ongewenst regime terechtkomt. We blijven de robot dan herstarten totdat een goed regime bereikt wordt. Eéns in een goed regime, kan de robot hopelijk zijn normale programma vervolgen zonder problemen. Deze belangrijke veronderstelling vormde de basis voor de oplossing die in de volgende paragrafen geschetst zal worden.

4.3.1

Dalende waarden opvangen

Dalende waarden opvangen kan eenvoudig door te controleren of de waarden onder een bepaalde drempel zakken. We moeten deze drempel wel per sensor apart en dynamisch6 bepalen, omdat niet elke sensor in elke startsituatie dezelfde hoeveelheid achtergrondruis meet. Het kiezen van deze drempel gebeurt door bij het opstarten de robot eerst 100 metingen te laten doen en de laatste EMA-waarde te nemen als referentiewaarde. De grens om dalende waarden te vinden is dan bijvoorbeeld veertig lager dan de referentiewaarde en de grens om een voorwerp te detecteren veertig hoger. Door een correcte keuze van deze bovengrens, kan men de afstand bepalen waarbij de robots elkaar zullen detecteren. Hoe kleiner die grens, hoe eerder ze elkaar zullen vinden. Als de grens te groot gekozen wordt, zullen de robots botsen. Het geval van dalende waarden is gemakkelijk op te sporen, omdat de waarden enkel door ruis wat onder de referentiewaarde gaan. Indien het regime van dalende waarden gedetecteerd wordt, herstart de robot zichzelf zoals te zien is in algoritme 4.4. Na het opstarten zal de robot opnieuw 100 metingen doen om op die manier een nieuwe referentiewaarde te bepalen. Hierdoor krijgen we ook een nieuwe boven- en ondergrens. De kans bestaat dat de robot tijdens deze eerste 100 metingen reeds in een ongewenst regime zit of terechtkomt en waarden opmeet die in de buurt van nul liggen. Hieruit kan hij dan besluiten om een zeer lage ondergrens te kiezen, wat niet wenselijk is. Om dit op te vangen is er een minimumwaarde voorzien voor de ondergrens. Het regime van dalende waarden wordt ge¨ıllustreerd in figuur 4.11. Het herstarten van de robot wordt in de figuur telkens aangegeven met een rode stip. In het eerste geval starten de waarden op een normaal niveau, worden ze op een bepaald ogenblik steeds kleiner, tot ze onder de ondergrens zakken, waarna de robot herstart. Na de herstart komt de robot opnieuw in een ongewenst regime terecht, aangeduid in het groen, 6

Met dynamische willen we hier zeggen dat de waarde van de drempel niet voorgeprogrammeerd wordt.


82

Algoritme 4.4 Dalende waarden opvangen 1: Measure 100 sensor values with EMA 2: ref erence value = last EMA value 3: lower bound = (ref erence value − 40) 4: if (lower bound < 20) then 5: lower bound = 20 6: end if 7: upper bound = (ref erence value + 40)

13:

repeat current sensor value = read new IR value() if (current sensor value < lower bound) then Value too small ⇒ Restart robot! end if until (current sensor value > upper bound)

14:

Maximum reached ⇒ Stop robot! and proceed to objective 2

8: 9: 10: 11: 12:

waarbij de waarden al veel te klein zijn bij het herstarten van de robot en na de eerste 100 waarden zijn ze dit nog steeds, waardoor de robot meteen zal herstarten. Daarna zijn de waarden opnieuw normaal.

4.3.2

Stijgende waarden opvangen

Het is veel moeilijker om een ongewenst regime van stijgende sensorwaarden te detecteren, omdat het niet te onderscheiden is van de situatie waarbij de IR-sensoren een voorwerp detecteren, tenzij de sensorwaarden echt abnormaal hoog zijn. Om dit ongewenst regime consequent te kunnen detecteren, hebben we nood aan een extra sensor die onafhankelijk van de IR-sensoren kan werken. In hoofdstuk 3 hebben we de ontwikkeling van zo’n sensor (Sonar Turret) besproken en die wordt dan ook gebruikt om uit deze impasse te geraken. We beschouwen het experiment dat de robot recht op de andere robot af rijdt en dit valt uiteen in twee gevallen. Detecteert de robot een voorwerp via de IR-sensoren, dan kan hij via de Sonar Turret controleren of er echt een andere robot in de buurt staat. Is dit niet het geval, dan zal de robot herstarten en van voorafaan beginnen met algoritme 4.5. Een extra veiligheid kan ingebouwd worden bij het herstarten, waarbij de robot in een regime kan terechtkomen met waarden die onmiddellijk veel te groot zijn. Als de referentiewaarde groter is dan 250, zou dit willen zeggen dat de robot eigenlijk al gebotst is. In dit geval zal de robot meteen herstarten. Dat deze extra test belangrijk is, kan afgeleid worden uit figuur 4.12. Omdat de waarden voor sensor 3 steeds te groot waren, moest de robot 15 keer na elkaar herstarten, tot hij in een regime kwam met normale waarden zoals aangeduid is in het groen, rechts op de figuur. Het herstarten is te zien aan de nulwaarden op de figuur, aangegeven door rode stippen. Dit bewijst meteen ook het nut van de eerste 100 metingen waarbij pas na deze 100 metingen de referentiewaarde vastgelegd wordt, omdat de eerste waarden duidelijk niet representatief zijn. De robot is telkens heel regelmatig na 101 metingen herstart zoals te zien is op de figuur.


83

Figuur 4.11: Dalende waarden bij de robot

De figuur 4.12 toont maar één geval van oplopende waarden, want het kan ook dat de waarden rustig oplopen tot ze de bovengrens overschrijden, zoals in figuur 4.13. Het herstarten is opnieuw aangeduid met rode stippen. De waarden stijgen drie keer, maar de eerste twee keer is er nog geen object in de buurt. Uit de figuur blijkt dat de robot dit op basis van de sensorwaarden alleen niet kan achterhalen. Dit probleem is enkel op te vangen met behulp van een onafhankelijke sensor, zoals de Sonar Turret.

4.3.3

Bijkomende problemen

Robotdetectie vanuit verschillende richtingen In paragraaf 4.3.1 werden dalende waarden op een algemene manier opgevangen. Voor stijgende waarden klopt algoritme 4.5 echter enkel als de robots recht op elkaar af rijden. Het algoritme volstond niet voor situaties waar de robots elkaar naderen vanuit willekeurige richtingen. Dit is te zien in figuur 4.14. Afhankelijk van de sensor (rood/groen) waarop het object wordt gedetecteerd, zal de richting waarin de Sonar Turret moet meten anders zijn. In het geval dat een object via de rode sensor gedetecteerd wordt, moet de Sonar Turret in de richting van de rode sensor meten (links voor de robot), in het andere geval moet hij in de richting van de groene sensor (recht voor de robot) meten. Het globale probleem is dat er eigenlijk zeer veel verschillende situaties mogelijk zijn en dat elke situatie op een andere manier dient aangepakt te worden. Dit leidt tot een zeer onoverzichtelijk algoritme waarbij de kans groot is dat nog steeds situaties over het hoofd worden gezien.


84

Figuur 4.12: Te grote waarden bij het heropstarten van de robot

Uit experimenten is bovendien gebleken dat de Sonar Turret-metingen weer oplopen als ze te dicht (ongeveer 2 cm, wat niet zoveel verschilt van de maximum range van de IR-sensoren) bij de andere robot komen, zodat het moeilijk te achterhalen is of de robots net iets verder of net heel dicht bij elkaar staan. Be¨ınvloeding bij doelstelling 3 Ondanks de problemen die hierboven beschreven zijn, werd tijdens de simulaties, door het aanbrengen van de verschillende veiligheidsmechanismen, zo’n 9 op 10 keer doelstelling 1 bereikt. Er werd dan overgegaan tot het testen van doelstellingen 2 en 3 met twee robots. Helaas bleek ook hier de be¨ınvloeding tussen de IR-sensoren invloed te hebben op de werking van het algoritme. Het grote verschil met doelstelling 1 is het feit dat hier niet zo eenvoudig herstart kan worden. Dit is bijna onmogelijk, omdat de robot geen toestand kan bijhouden van voor zijn herstart en zo niet kan achterhalen waar hij zich bevond in zijn algoritme (doelstelling 1, 2, 3 of 4). Het herstarten van de robot zou enkel een goede oplossing zijn als de robot in één keer in een goed regime kon komen en daar ook in bleef. Dit is dus niet het geval, waardoor het herstarten eigenlijk geen zin heeft.

4.3.4

Bijkomende oplossingen

De nieuwe aanpak uit de voorgaande paragraaf heeft dus niet het gewenste resultaat opgeleverd. De oplossing die het meest eenvoudig is, komt van de Sonar Turret. Deze kunnen weliswaar


85

Figuur 4.13: Langzaam oplopende sensorwaarden

elkaar ook be¨ınvloeden, maar de robots kunnen onder elkaar afspreken wie wanneer de Sonar Turret mag gebruiken, zodat be¨ınvloeding kan vermeden worden. Bij de Khepera II robots kunnen de IR-sensoren niet afgezet worden, zodat deze optie niet mogelijk is. Eventueel zou in de toekomst een aparte IR-turret gebouwd kunnen worden, maar omwille van de bestaande Sonar Turret is dit eigenlijk overbodig. Een andere oplossing zou zijn om IR-sensoren te gebruiken die elkaar niet be¨ınvloeden, door een verschillende golflengte of codering te gebruiken. Ook dit is enkel mogelijk door de ontwikkeling van een nieuwe (IR-)extensieturret.

4.4

Evaluatie

De hierboven aangehaalde oplossingen waren in het tijdsbestek van dit onderzoek niet meer mogelijk. Bovendien maken de algoritmes uit hoofdstuk 5 enkel gebruik van de Sonar Turret en boekten we daar mooie resultaten mee. Er werd dan ook geopteerd om het spoor van formatievorming met IR-sensoren te verlaten en de aandacht helemaal te richten op die met behulp van Sonar Turrets. De IR-sensoren in de huidige configuratie zijn onbetrouwbaar, omdat ze elkaar be¨ınvloeden en met onbetrouwbare sensoren is formatievorming niet mogelijk.


Algoritme 4.5 Stijgende waarden opvangen 1: Measure 100 sensor values with EMA 2: ref erence value = last EMA value 3: lower bound = (ref erence value − 40) 4: if (lower bound < 20) then 5: lower bound = 20 6: end if 7: upper bound = (ref erence value + 40) 8: 9: 10: 11: 12: 13: 14: 15: 16:

repeat current sensor value = read new IR value() if (current sensor value < lower bound) then Value too small ⇒ Restart robot! end if if (current sensor value > 250 ) then Value too big ⇒ Restart robot! end if until (current sensor value > upper bound)

if (Distance measured with sonar > 3 cm) then Bogus detection ⇒ Restart robot! 19: else 20: Maximum reached ⇒ Stop robot! and proceed to objective 2 21: end if 17: 18:

Figuur 4.14: Bijkomende gevallen

86

Hoofdstuk 5

Formatievorming met de Sonar Turret Inhoudsopgave

5.1

5.1

Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

87

5.2

Robots detecteren en formatie vormen . . . . . . . . . . . . . . . . . .

89

5.3

Formatie behouden met verschillend interactiegedrag

. . . . . . . . .

94

5.4

Formatie behouden met verschillend autonoom gedrag . . . . . . . . .

99

Inleiding

In dit hoofdstuk bespreken we de algoritmes die ontwikkeld werden voor formatievorming met behulp van de Sonar Turret. De C-code die deze algoritmes implementeert op de robot is te vinden op de bijgeleverde CD in de map Formation with Sonar Turret” ” Aangezien deze algoritmes gebruik maken van de Sonar Turret, werken ze, om interferentieproblemen tussen ultrasone golven te vermijden, met een beurtensysteem waarbij tussen de robots onderling wordt afgesproken wie de volgende in de rij is die zijn Sonar Turret mag gebruiken. Op die manier vermijden we dat bijvoorbeeld de Sonar Turret van één robot een ultrasone puls opvangt van een andere robot in plaats van een echo van zijn zelf verstuurde ultrasone puls. Naast het feit dat de metingen van de Sonar Turret heel wat tijd in beslag nemen, heeft dit beurtensysteem mede tot gevolg dat de formatievorming niet meer in real-time (terwijl de robots rijden) kan gebeuren. Dit beurtensysteem werd ge¨ımplementeerd door, telkens wanneer een robot klaar is met zijn afstandsmetingen, hem een bericht te laten versturen naar alle andere robots met de boodschap dat hij de sonar pas een volgende keer zal gebruiken als hij van alle andere robots zo’n zelfde boodschap ontvangen heeft. Een algemeen schema van het beurtensysteem is te vinden onder Algoritme 5.1 en onder Algoritme 5.2. Er is dus een vaste volgorde bij de robots die om beurt de Sonar Turret gebruiken en deze volgorde wordt doorheen het ganse algoritme behouden. Deze volgorde wordt helemaal in het 87

Hoofdstuk 5. Formatievorming met de Sonar Turret

Algoritme 5.1 Algemene werking van het beurtensysteem: algoritme-proces 1: loop 2: while !(otherRobotsReady) do 3: wait 4: end while 5: otherRobotReady = (SIZE F ORM AT ION − 1) 6: otherRobotsReady = 0 7: ... 8: Do 1 cycle of algorithm 9: ... 10: for (1 ≤ i ≤ SIZE F ORM AT ION ) do 11: if (i 6= ownID) then 12: send message to robot[i] that robot[ownID] is ready 13: end if 14: end for 15: end loop

Algoritme 5.2 Algemene werking van het beurtensysteem: luister-proces 1: loop 2: wait for incoming message msg from Radio Turret 3: if (msg == READY-message) then 4: otherRobotReady − − 5: if (otherRobotReady == 0) then 6: otherRobotsReady = 1 7: end if 8: else 9: ... 10: end if 11: end loop

88


89

begin, bij het opstarten van de robots, afgesproken tussen de robots onderling. Ze doen dit door elk afzonderlijk een willekeurig getal te genereren (m.b.v de C-functies rand() en srand(seed)) en dit naar de andere robots door te sturen. Wie het grootste getal genereerde wordt de eerste in rij, diegene met het tweede grootste getal wordt de tweede in rij enz. In de volgende paragrafen zullen we eerst een algoritme bespreken waarbij de robots vanuit een willekeurige positie elkaar opzoeken om tot een driehoeksformatie te komen. Daarna bespreken we twee verschillende algoritmes om de robots in een bepaalde richting te laten rijden, met behoud van deze formatie.

5.2

Robots detecteren en formatie vormen

In deze paragraaf bespreken we een algoritme dat ontwikkeld werd om de Khepera II -robots vanuit een willekeurige startpositie elkaar te laten vinden, naar mekaar toe te laten rijden en een driehoeksformatie te laten vormen. We zullen trachten een gelijkzijdige driehoek te vormen waarbij de afstand tussen de middelpunten van elk paar robots ongeveer 30 cm bedraagt. Hierbij wordt enkel gebruik gemaakt van de Sonar Turret die we bespraken in hoofdstuk 3. We zullen eerst het algemene schema en de theoretische werking bespreken. Vervolgens bespreken we de praktische implementatie van het algoritme en de problemen die hierbij opdoken.

5.2.1

Algemene werking

Zoals reeds besproken in de inleiding van dit hoofdstuk, kunnen de robots slechts om beurt hun sonar gebruiken om geen last te hebben van interferentie tussen de verschillende sonarmodules. Het algoritme is dan ook op die manier opgebouwd. We gaan ervan uit dat er één robot blijft staan op zijn initiële positie. Dit is geen strikte voorwaarde; men kan er voor kiezen om ook die ene robot eerst naar een bepaalde positie te laten rijden en vervolgens het algoritme te laten starten. Dit heeft echter geen invloed op het algoritme dat volgt. Het algoritme begint bij deze ene robot (die we vanaf nu robot 1 noemen). De beslissing over welke robot deze taak krijgt, wordt onder de robots zelf genomen op dezelfde basis van het willekeurig getal dat ook vermeld werd in de inleiding van dit hoofdstuk. Van zodra vaststaat wie robot 1 wordt, laat robot 1 aan robot 2 weten dat hij mag starten met het zoeken van robot 1. Robot 1 wordt dan voor de rest van dit algoritme een soort van slaaf en voert enkel opdrachten uit die hij ontvangt door communicatie met de andere twee. Robot 2 begint robot 1 te zoeken en doet dit door eerst robot 1 sonarmetingen te laten uitvoeren om de tien graden en dit over in totaal een hoek van 360 graden. Robot 1 beschikt dan uiteindelijk over 36 opgemeten afstanden die hij doorstuurt naar robot 2. Robot 2 begint dan met dezelfde handeling en meet ook 36 afstanden over 360 graden. Aangezien robot 2 ook over de opgemeten afstanden van robot 1 beschikt, kan hij deze vergelijken met zijn eigen opgemeten afstanden en kan hieruit proberen een conclusie te trekken over de richting waarin robot 1 zich bevindt. Wanneer er een opgemeten afstand blijkt te zijn die nagenoeg identiek is op beide robots, besluit robot 2 hieruit dat robot 1 in de richting te vinden is waarin


90

hij deze meting deed en begint hij in die richting te rijden totdat hij op een voldoende dichte afstand (ongeveer 30 cm) genaderd is van robot 1. Vervolgens laat hij aan robot 3 weten dat deze mag beginnen met robot 1 te zoeken. Ook robot 3 zal 36 afstanden meten en vergelijken met de ontvangen data van robot 1. Ook hij probeert de richting te vinden waarin robot 1 zich bevindt en nadert in die richting robot 1. Wanneer hij robot 1 voldoende genaderd is, probeert hij zich echter ook ten opzichte van robot 2 op een correcte manier te positioneren zodat de vooropgestelde formatie bereikt wordt.

5.2.2

Praktische implementatie

Een eerste stap in de praktische implementatie was het nagenoeg letterlijk omzetten van het theoretische algoritme naar code voor de Khepera II. Marge voor identieke afstanden Uit de eerste tests bleek al onmiddellijk dat opgemeten afstanden door verschillende robots nooit volledig identiek zijn. Dit kan eenvoudig verklaard worden door de beperkte resolutie die we nemen om afstanden op te meten. We meten namelijk slechts om de 10 graden, dus de kans is klein dat twee robots elkaar op dezelfde manier zullen zien. We dienen dan ook een marge in te bouwen om twee afstanden als identiek te beschouwen. Valse detectie identieke afstanden Het gebruik van zo’n marge vergroot echter de kans op een valse detectie van identieke afstanden. Een object (geen robot) dat op bijna dezelfde afstand staat als de te detecteren robot, heeft ook een kans om herkend te worden als een robot. Deze situatie is niet te vermijden. We bedachten hiervoor de volgende oplossing1 . Stel dat robot 2 probeert om robot 1 te detecteren en hiervoor verschillende identieke afstanden gevonden heeft. Met identieke afstanden bedoelen we hier afstanden gemeten op verschillende robots die (ongeveer) dezelfde waarde hebben. We zullen er dan niet onmiddellijk van uitgaan dat de eerst gevonden afstand de correcte is, maar voor elk van de gevonden identieke afstanden een controle uitvoeren op valse detectie. Deze controle gebeurt door robot 2 in de gevonden richting te laten rijden over een welbepaalde afstand en de meting opnieuw te laten uitvoeren door robot 2 en robot 1. Robot 1 zal zich hierbij dan ook draaien in de richting waarin hij robot 2 verwacht. Deze richting zal beslist worden door robot 2 (uit de 36 waarden van elk van beide robots) en robot 2 zal die richting ook terugsturen naar robot 1. Robot 1 stuurt zijn opgemeten afstand dan opnieuw door naar robot 2 en die zal daaruit dan beslissen of de richting die hij gekozen had correct was. Indien de richting niet correct was, zal robot 2 terugkeren naar zijn initiële positie en een volgende gevonden richting uitproberen op dezelfde manier. Dit proces herhaalt zich tot de doorgestuurde afstandsmeting van robot 1 overeenkomt met de afstandsmeting van robot 2. 1

We gebruiken hier en ook in de volgende paragrafen steeds robot 2 om het probleem uit te leggen, maar ook op robot 3 zullen dezelfde problemen opduiken en zullen we dezelfde oplossingen gebruiken.


91

Onnauwkeurige positiebepaling Een probleem dat reeds beschreven werd in referentie [6, sectie 5.2] is de onnauwkeurige positiebepaling waarover de Khepera II beschikt. In het algoritme dat we hierboven beschreven, geeft dit problemen bij het draaien over een bepaald aantal graden en bij het vooruit of achteruit rijden over een bepaalde afstand. Deze bewegingen worden geprogrammeerd met behulp van de ingebouwde functie mot_new_position_2m(posLeftWheel, posRightWheel). Die laat toe om de wielen van de Khepera II een welbepaalde rotatie te laten uitvoeren. Dit zorgt in principe voor een afstand die de robot zal afleggen of, indien we voor het linker- en rechterwiel een tegengesteld argument meegeven, een rotatie van de robot. We kunnen echter geen rekening houden met het doorslippen van de wielen en dus leidt deze functie niet steeds tot het gewenste gedrag. De oplossing die we hiervoor bedachten is dat we bij het controleren van een identieke afstand, niet enkel een meting uitvoeren in de richting die we controleren, maar ook telkens 5 en 10 graden links en rechts daarvan. Dit doen we zowel bij robot 1 als robot 2, zodat we uiteindelijk over tien gemeten afstanden (vijf van robot 1 en vijf van robot 2) beschikken op robot 2 die we moeten vergelijken en op basis waarvan we beslissen of de gecontroleerde richting correct is. Derde meting Na de aanpassingen die we besproken hebben in de vorige paragrafen, vonden de robots elkaar reeds af en toe. Toch werden er nog enkele situaties gevonden waarin robot 2 een obstakel verkeerd detecteerde als zijnde robot 1. Om dit te vermijden werd nog een derde meting toegevoegd waarbij robot 2 opnieuw een bepaalde afstand verder rijdt in de richting waarin hij denkt dat robot 1 zich bevindt. Opnieuw wordt er een afstandsmeting uitgevoerd door robot 1 en 2 en stuurt robot 1 zijn afstandsmeting door naar robot 2. Robot 2 controleert dan een derde keer of deze twee afstanden identiek zijn (binnen een bepaalde marge) en enkel indien deze identiek zijn, concludeert hij dat de correcte richting gevonden is. Ontwijkgedrag door robot 2 Waneer beide robots (2 en 3) de richting gevonden hebben waarin ze robot 1 zien, zullen ze in die richting rijden tot ze robot 1 tot op een voldoende korte afstand genaderd zijn. Daarna stellen ze zich in de correcte driehoeksformatie op ten opzichte van robot 1. Wanneer we stellen dat robot 1 de top vormt van de driehoeksformatie, zal robot 2 de hoek linksonder vormen en robot 3 de hoek rechtsonder. Stel dat het verschil tussen de richting waarin robot 2 robot 1 nadert en de richting waarin robot 3 robot 1 nadert te klein is, dan kan er eventueel een probleem ontstaan wanneer robot 2 en robot 3 zich tegelijk verplaatsen naar hun uiteindelijke positie in de formatie. Daarom is er een extra veiligheid ingebouwd in het algoritme om dit eventuele probleem op te vangen. Eerst en vooral zullen robot 2 en robot 3 niet tegelijk robot 1 naderen, maar zullen ze dit om beurt doen en zal robot 2 hiermee eerst starten. Voor hij hieraan begint, zal hij aan robot 1 vragen wat de richtingen zijn waarin hij robot 2 en robot 3 gevonden heeft. Uit deze gegevens zal robot 2 dan een beslissing nemen over het al dan niet inbouwen van een ontwijkgedrag voor


92

Figuur 5.1: Ontwijkgedrag door robot 2

robot 3. Als de hoek tussen robot 2 en robot 3 te klein is, zal robot 2, wanneer hij in de richting van robot 1 rijdt, een kwartcirkel rond robot 1 rijden (figuur 5.1) om op die manier de hoek tussen hem en robot 3 te vergroten, zodat er geen probleem meer kan ontstaan als robot 3 robot 1 wil naderen. De richting (wijzerzin of tegenwijzerzin) waarin de kwartcirkel afgelegd wordt, zal robot 2 afleiden uit de gegevens die hij ontving van robot 1. Finale formatievorming Robot 2 staat nu op een gekende afstand (ongeveer 25 cm) van robot 1. Robot 3 zal nu ook tot op die afstand rijden van robot 1 en zal dan trachten robot 2 te vinden door in een cirkel rond robot 1 te rijden tot hij robot 2 op zijn weg vind. De cirkelstraal is aangepast aan de gekende afstand (25 cm) tussen robot 1 en 2. Als robot 3 robot 2 gevonden heeft, zet hij zich op de goede postie zodat hij rechtsonder staat in de driehoek en als laatste de formatievorming voltooid. Deze laatste stap in de formatievorming is te zien in figuur 5.2.

5.2.3

Resultaten

De rechtstreekse implementatie van het theoretische algoritme gaf helemaal niet het gewenste resultaat. Obstakels werden verkeerdelijk als robot gedetecteerd en de robots bevonden zich op het einde helemaal niet in de correcte formatie. De aanpassingen die we besproken hebben in


93

Figuur 5.2: Laatste stap in de formatievorming

paragraaf 5.2.2 werden dan ook aangebracht en uiteindelijk werd de gewenste formatievorming bekomen. Er zijn echter wel enkele voorwaarden verbonden aan de initiële positie van elk van de robots opdat ze met behulp van het hierboven beschreven algoritme elkaar zouden vinden en in de correcte formatie zouden komen. Ten eerste moet elk van de robots elkaar kunnen ‘zien’ (m.a.w er is nood aan een Line of Sight). Dit houdt niet alleen in dat er zich geen obstakels tussen de robots mogen bevinden, maar ook dat er zich geen robot tussen de andere twee mag bevinden2 (initiële lijnformatie). Een tweede voorwaarde voor de initiële positie van de robots is dat ze zich op voldoende afstand van elkaar moeten bevinden. Tijdens de tweede en derde controle van de gevonden identieke afstanden, rijdt robot 2/3 namelijk in de richting van robot 1 en hij controleert hierbij niet of de ruimte voor de afstand die hij hiervoor moet afleggen wel beschikbaar is. Stel dat de robots zich te dicht in elkaars buurt bevonden bij de start van het algoritme, dan kan het gebeuren dat robot 2/3 deze afstand niet kan afleggen en het dus tot een botsing zou komen tussen robot 2/3 en robot 1. Hiervoor zou een veiligheidsmechanisme (zoals we er bijvoorbeeld één zullen zien in paragraaf 5.4.2) ingebouwd kunnen worden. De voorwaarden voor de initiële positie kunnen gerust vermeden worden met bijkomende veiligheidsmechanismen. Zo zouden de robots helemaal in het begin elk om beurt kunnen rijden 2 Robot 1 mag zich wel tussen robot 2 en robot 3 bevinden, omdat robot 2 en robot 3 beiden onafhankelijk robot 1 zullen zoeken, maar wanneer bijvoorbeeld robot 2 zich tussen robot 1 en robot 3 bevindt, zal robot 3 robot 1 niet meer kunnen vinden via afstandsmetingen.


94

Figuur 5.3: (links) Positie voor het uitvoeren van het formatievormingsalgoritme (rechts) Positie na het uitvoeren van het formatievormingsalgoritme

naar een plaats waar ze voldoende ruimte rond zich hebben om het algoritme uit te voeren. De tweede voorwaarde zou dan geen probleem meer mogen vormen. Als de robots op een lijn staan, kunnen ze dit detecteren als robot 1 maar één robot kan vinden. In dat geval kan de robot die niet gevonden werd, verder rijden tot hij uit de lijnformatie is. Ook andere oplossingen zijn mogelijk omdat geen enkele van de aangehaalde problemen van fundamentele aard is. Ze werden niet opgelost in ons onderzoek omdat we beperkt waren in tijd en het volgende probleem wilden aanpakken, namelijk de robots in formatie houden. Rekening houdend met de huidige beginvoorwaarden, hebben we verschillende geslaagde experimenten uitgevoerd. Een voorbeeld hiervan zien we in figuur 5.3. Links zien we de startpositie van de drie robots en rechts hun positie na de uitvoering van het algoritme. We zien dat de correcte formatie gevormd werd.

5.3

Formatie behouden met verschillend interactiegedrag

Eens de robots elkaar gevonden hebben en een driehoeksformatie gevormd hebben, willen we ze natuurlijk een volgend doel geven, bijvoorbeeld een richting uit rijden waarbij deze formatie behouden blijft. Twee algoritmes die we hiervoor ontwikkeld hebben, bespreken we in deze en


95

de volgende paragraaf. Deze algoritmes bestaan telkens uit twee delen. Eén deel zorgt voor het het interactiegedrag (de robots blijven in formatie). Het tweede zorgt voor het autonoom gedrag, zodat de robot nog een ander doel heeft, naast het behouden van de formatie.

5.3.1

Algemene werking

In dit eerste algoritme starten de robots in een gelijkzijdige driehoek en zijn ze initieel allemaal in dezelfde richting georiënteerd3 (zie figuur 5.3 rechts). Het algoritme is gebaseerd op een zeer eenvoudig principe: elke robot controleert de afstanden tot de andere robots; de robot differentieert drie verschillende situaties waarbij hij telkens een ander gedrag zal vertonen: • (Interactiegedrag) Is de afstand tot een andere robot te groot, dan zal de robot in de richting van deze te ver verwijderde robot rijden. • (Interactiegedrag) Is de afstand tot een andere robot te klein, dan zal hij in de tegenovergestelde richting rijden. • (Autonoom gedrag) Zijn alle afstanden tot de andere robots binnen een bepaalde marge, dan zal de robot in een voorgeprogrammeerde richting4 rijden. We zien dus dat het autonoom gedrag dus voor iedere robot hetzelfde is, maar slechts uitgevoerd wordt als de robot zich, binnen een bepaalde marge, in de formatie bevindt. Het interactiegedrag wordt uitgevoerd wanneer de robot te ver verwijderd is van zijn positie in de formatie. Omdat de robots allemaal dezelfde oriëntatie hebben, dient dit interactiegedrag wel voor iedere robot op een andere manier geprogrammeerd te worden. De robot linksonder zal bijvoorbeeld rechts van hem en rechtsboven van hem moeten meten om de afstanden te weten tot de andere twee robots, terwijl de andere twee robots in die richtingen geen robots detecteren.

5.3.2


Onnauwkeurige positiebepaling Wanneer een robot de afstanden wil meten tot de andere twee, zal hij die metingen uitvoeren in de richting waarin hij de andere twee verwacht te staan. Dit is natuurlijk een open-loop situatie en door de onnauwkeurige positiebepaling, zou dit, zonder extra veiligheden in te bouwen, snel tot problemen kunnen leiden. Daarom hebben we voor de onderste twee robots in de formatie een veiligheidsmechanisme ingebouwd waarbij ze, vóór het meten van de afstand tot de andere, zich eerst correct positioneren ten opzichte van de andere. Dit doen ze door drie opeenvolgende metingen te doen: één in de richting waarin ze denken dat de andere robot staat, één vijf graden links daarvan en een laatste vijf graden rechts daarvan. De robot positioneert zich dan in die richting waarin hij de minimale afstand opmat. Hierdoor zullen de onderste twee robots zich beter ten opzichte van elkaar positioneren. Ook voor de bovenste robot in de formatie 3

Dit is niet geheel waar, omdat in de praktijk de bovenste robot in de driehoek omgekeerd georiënteerd start en ‘vooruit rijden’ voor hem dus eigenlijk ‘achteruit rijden’ betekent. Dit is echter enkel zo omdat de robot dan niet voortdurend 180 graden moet draaien om de andere twee robots te zien. 4 Deze richting is in dit geval voor iedere robot dezelfde en voor de eenvoud wordt recht vooruit gekozen.


96

kan zo’n gedrag ge¨ımplementeerd worden, maar dit werd niet gedaan om de uitvoeringstijd van het algoritme niet nog meer te vergroten5 ; we rekenen erop dat deze robot zich correct zal positioneren door zijn interactiegedrag. Gelijktijdige beweging Zoals we reeds vermeld hebben in de inleiding (paragraaf 5.1) van dit hoofdstuk, werken we steeds met een beurtensysteem waarbij de robots elk om beurt een cyclus van het algoritme uitvoeren en daarna wachten tot de andere twee robots ook een cyclus van het algoritme uitgevoerd hebben. Stel dat een cyclus zou bestaan uit het opmeten van de verschillende afstanden (tot de andere robots), een beslissing nemen over welke beweging gemaakt zal worden en het uitvoeren van deze beweging. Stel nu dat alledrie de robots voor hun cyclus correct in formatie staan. De robots zullen dan alledrie beslissen om hun autonoom gedrag uit te voeren, wat correct is. Er kan echter een probleem ontstaan. Wanneer bijvoorbeeld de bovenste en de rechtse robot in de formatie hun beweging reeds uitgevoerd hebben en de linkse robot begint aan zijn metingen, zal hij de rechtse robot niet meer vlak naast zich opmeten, maar rechts voor zich. Dit komt natuurlijk doordat de rechtse robot zijn cyclus al doorlopen heeft en de beweging reeds uitgevoerd heeft. De linkse robot zal daaruit echter besluiten dat zijn initiële oriëntatie niet correct was en zal zich heroriënteren ten opzichte van de rechtse robot (cfr. paragraaf 5.3.2: onnauwkeurige positiebepaling). Dit is niet de correcte beslissing omdat hij hoogstwaarschijnlijk wel correct georiënteerd stond, maar het is een gevolg van het feit dat de rechtse robot reeds een cyclus meer uitgevoerd had. De manier waarop dit probleem opgelost wordt, is het scheiden van enerzijds de metingen zelf en de beslissing over de beweging die genomen moet worden op basis van die metingen en anderzijds het bewegen van de robot. De metingen en het beslissen worden elk om beurt gedaan volgens het bovenvermelde beurtensysteem, maar de robots zullen de eigenlijke beweging pas uitvoeren op het moment dat ze weten dat iedere robot zijn beweging uitvoert. Hiervoor wordt opnieuw gebruik gemaakt van het willekeurig getal waarmee de volgorde in het beurtensysteem in het begin bepaald werd (paragraaf 5.1). Door het ontvangen van boodschappen van andere robots waarin staat dat die robots klaar zijn met zijn cyclus van het algoritme, kan een (ontvangende) robot bepalen wanneer het weer de beurt is aan de eerste6 robot in het beurtensysteem. Op dat moment zullen alle robots hun beweging uitvoeren. Formatie herstellen Na tien cycli van autonoom gedrag en interactiegedrag voor elke robot, volstond het interactiegedrag niet meer om de formatie te behouden. Daarom besloten we dat om de drie cycli een extra algoritme moet worden uitgevoerd dat ervoor zorgt dat de formatie hersteld wordt. In dit algoritme blijft één van de robots staan, terwijl de andere twee zich na elkaar zullen herpositioneren ten opzichte van de robot die blijft staan. De praktische implementatie van dit herpositioneren gebeurt als volgt. Eerst controleert de robot of de robot waarmee hij zich 5 6

Iedere extra sonarmeting zorgt namelijk voor aanzienlijke vertraging. De robot die initieel, bij het opstarten van de robots, de eerste beurt kreeg.


97

zal heroriënteren zich in de richting bevindt waarin hij die verwacht. Dit doet hij door met de Sonar Turret te scannen over een hoek van 50 graden, met de richting waarin hij de andere robot verwacht als bissectrice van deze hoek. Hij positioneert zich dan in de richting waarin hij een minimale afstand opgemeten heeft. Daarna laten we de robot in die richting rijden tot hij op een welbepaalde afstand (ongeveer 5 cm) van de andere robot staat (dit is mogelijk door uit te gaan van de afstandsmeting die gedaan werd in die richting). Vervolgens laten we de robot scannen met de Sonar Turret om de twee uiterste punten van de andere robot te zoeken7 . De robot oriënteert zich dan in de richting van de bissectrice van de hoek tussen deze twee uiterste punten en besluit hieruit dat hij correct geheroriënteerd is ten opzichte van de andere robot. Vervolgens zal de robot in die richting achteruit rijden tot hij op de goede afstand (30 cm) staat van de stilstaande robot. Dit volstaat voor de eerste robot die aan de beurt is, maar voor herpositionering van de tweede robot is een complexer algoritme nodig. De hoek tussen de twee richtingen waarin de stilstaande robot de andere ziet moet 60 graden zijn, opdat de formatie een gelijkzijdige driehoek zou vormen. Om de richtingen te achterhalen waarin de andere twee zich bevinden, zal de stilstaande robot de twee andere scannen om de bissectrice tussen hun uiterste twee punten te vinden. Als de hoek tussen die twee richtingen niet 60 graden is, geeft de stilstaande robot de opdracht aan de tweede robot om zich te verplaatsen, zodat de hoek wel 60 graden wordt. Het verplaatsen van de tweede robot gebeurt in een cirkelboog rond de stilstaande robot (figuur 5.4). Pas dan mag de tweede robot achteruit rijden over de goede afstand (30 cm). Als de beide robots zich geherpositioneerd hebben, kan het normale algoritme met interactieen autonoom gedrag weer verder uitgevoerd worden. Ontwijken van obstakels In het experiment reed de driehoeksformatie vooruit met één robot (robot 1) op kop. Deze robot kan de omgeving voor zich scannen met de Sonar Turret en op die manier obstakels detecteren. Als hij bijvoorbeeld een obstakel rechts detecteert, kan robot 1 beslissen om de ganse formatie naar links te laten draaien, zodat de formatie het obstakel ontwijkt. Het algoritme is zo opgebouwd dat de formatie zes richtingen uitkan, afhankelijk van de richting waarin het obstakel gedetecteerd werd: • 90 graden naar links • 45 graden naar links • Rechtdoor (geen ontwijkgedrag) • 45 graden naar rechts • 90 graden naar rechts 7

Door telkens om de vijf graden een meting te doen en het verschil te controleren met de vorige meting, kan bepaald worden wanneer het uiteinde van de andere robot bereikt is, namelijk op het moment dat er een aanzienlijk verschil is tussen twee opeenvolgende metingen.


98

Figuur 5.4: Herpositionering van de tweede robot ten opzichte van de eerste (stilstaande) robot, zodat de gelijkzijdige driehoeksformatie hersteld wordt.

• Achteruit Bij het draaien over 90 graden komt er een andere robot op kop (robot 3 in plaats van robot 2 in figuur 5.5), zodat die robot op dat moment de omgeving opmeet en de beslissingen neemt over het ontwijken van obstakels. Het is duidelijk dat de robot op kop een speciale positie inneemt in de formatie. Eigenlijk is hij de leider van de formatie en hoewel de rol kan doorgegeven worden, blijft er altijd één robot de leider.

5.3.3

Resultaten

Met het bestaande algoritme kan de driehoeksformatie behouden worden, maar is er wel altijd één robot de leider. Het doel van ons onderzoek was eigenlijk om een formatie te creëren waarin de robots gelijkwaardig zijn, wat op de hierboven beschreven manier dus niet mogelijk is. Op het moment dat het ontwijken van obstakels voor de formatie zou worden getest, kwam onze promotor met het idee om het interactiegedrag voor de robots gelijk te maken, zodat de robots wel gelijkwaardig zijn in de formatie. Dit was een zeer interessante oplossing en de focus van het onderzoek werd dan ook meteen verlegd. We zullen dit beschrijven in de volgende paragrafen.


99

Figuur 5.5: Draaien van de formatie over 90 graden (de robots in lichtere kleur geven de situatie weer van voor het draaien)

5.4 5.4.1

Formatie behouden met verschillend autonoom gedrag Algemene werking

In dit tweede algoritme starten de robots opnieuw in een gelijkzijdige driehoek, maar nu hebben ze elk een verschillende oriëntatie. We zorgen ervoor dat elke robot naar één andere robot kijkt. Robot 1 kijkt naar (is met zijn hoofdrichting georiënteerd in de richting van) robot 2, robot 2 naar robot 3 en robot 3 opnieuw naar robot 1. Het interactiegedrag bestaat er dan in dat elke robot bij elke cyclus van het algoritme zich heroriënteert ten opzichte van de robot waar hij initieel naar keek. Het autonoom gedrag is in dit algoritme voor iedere robot anders. Bij iedere robot wordt een (al dan niet verschillende) richting voorgeprogrammeerd. Dit is de richting waarin de robot elke cyclus van het algoritme over een bepaalde afstand zal rijden. Als we deze initiële, autonome richtingen goed kiezen voor de drie robots, dan kunnen we ervoor zorgen dat de volledige formatie in dezelfde richting zal bewegen. Dit is echter geen noodzakelijke voorwaarde en we kunnen ook totaal willekeurige richtingen geven aan de drie robots. Aangezien in dit algoritme de autonome richting van elke robot eenvoudig kan worden aangepast, leek het ons zinvol om op die manier ook obstakelontwijking in te bouwen in het algoritme. Elke robot zal op het einde van elke cyclus kijken in zijn autonome richting of er nog voldoende ruimte aanwezig is om ook de volgende keer in die richting verder te kunnen rijden. Is dit niet het geval, dan zal de robot zijn autonome richting aanpassen zodat het obstakel kan worden ontweken.


100

Figuur 5.6: Uitvoering van het algoritme formatie behouden met verschillend autonoom gedrag” waar” bij alle robots elke om beurt een volledige cyclus uitvoeren. De rode pijlen geven het autonoom gedrag aan, de blauwe het interactiegedrag en de zwarte de ‘kijkrichting’ van elke robot.

5.4.2


Ook in dit algoritme zullen we gebruik maken van het gelijktijdig bewegen-principe. Hierbij zullen we ervoor zorgen dat de robots hun autonoom gedrag telkens gelijktijdig uitvoeren, terwijl het interactiegedrag en de obstakeldetectie nog steeds door elke robot om beurt zal gebeuren. De reden waarom we dit doen is omdat de driehoeksformatie anders moeilijker te behouden is. Dit wordt onmiddellijk duidelijk uit figuren 5.6 en 5.7. Op de eerste figuur wordt de volledige cyclus (interactiegedrag, obstakeldetectie en autonoom gedrag) om beurt uitgevoerd door elke robot. We zien dat de vooropgestelde gelijkzijdige driehoeksformatie volledig verloren gaat tijdens de uitvoering van het algoritme. Dit komt omdat elke robot een cyclus achter loopt op de robot die voor hem aan de beurt was en die door zijn autonoom gedrag zich alweer verwijderd heeft uit de formatie. In figuur 5.7 daarentegen zien we een heel andere situatie. Hierbij zullen alle robots tegelijk hun autonoom gedrag uitvoeren. Dit heeft tot gevolg dat, onder de voorwaarde dat hun autonoom gedrag in dezelfde richting gebeurt, hun interactiegedrag bijna niet zal moeten compenseren voor het uit formatie geraken door het autonoom gedrag. We zien dan ook dat de gelijkzijdige driehoeksformatie veel strakker behouden blijft. Herori¨ entatie Bij de heroriëntatie controleert de robot of de robot waarmee hij zich zal heroriënteren zich in de richting bevindt waarin hij deze verwacht8 . Dit doet hij door met de Sonar Turret te scannen over een hoek van 50 graden, met de richting waarin hij de andere robot verwacht als bissectrice 8

De andere robot kan zich in een licht verschillende richting bevinden door het uitvoeren van zijn autonoom gedrag in de vorige cyclus of door het probleem van het doorslippen van de wielen zodat de positiebepaling onnauwkeurig was.


101

Figuur 5.7: Uitvoering van het algoritme formatie behouden met verschillend autonoom gedrag” waar” bij alle robots tegelijk hun autonoom gedrag uitvoeren. De rode pijlen geven het autonoom gedrag aan.

van deze hoek. De richting van de kortste afstandsmeting vormt dan de nieuwe richting waarin de robot zich heroriënteert. Na de heroriëntatie controleert de robot of ook de afstand tot de andere robot nog steeds binnen een bepaalde marge is. Is dit niet het geval, dan rijdt de robot in de richting van de andere robot of indien nodig, in de tegenovergestelde richting, naargelang de afstand die opgemeten werd. Een probleem dat opdook tijdens de experimenten, is dat wanneer de robot eventueel achteruit moet rijden, dit niet altijd mogelijk is. Soms staat de robot in de buurt van een obstakel en kan hij niet over de volledige afstand achteruitrijden. Om dit op te vangen, pasten we het algoritme als volgt aan. Op het moment dat de robot achteruit wil rijden, zal hij zich nu eerst omdraaien en een afstandsmeting doen in de richting waarin hij wil rijden. Hieruit zal hij dan kunnen besluiten of dit mogelijk is of niet. Blijkt dat niet mogelijk, dan zal de robot enkel rijden over de afstand die hij ter beschikking heeft. Herori¨ entatie ten opzichte van twee robots In het oorspronkelijke ontwerp van het algoritme was het de bedoeling dat elke robot zich zou heroriënteren (interactiegedrag) ten opzichte van de robot voor zich9 . Uit de simulaties bleek echter dat dit niet voldoende was om de correcte formatie te behouden, zeker als de autonome richtingen van de verschillende robots niet op elkaar afgestemd waren. De driehoeksformatie wordt dan teveel uit elkaar getrokken, zodat het ge¨ımplementeerde interactiegedrag niet volstond om de formatie te corrigeren. We hebben dan het algoritme aangepast opdat elke robot zich niet alleen ten opzichte van de robot voor zich zou heroriënteren, maar ook ten opzichte van de andere robot in de driehoeksformatie. Dit leidde tot veel betere resultaten, waarbij de driehoeksformatie perfect behouden bleef in elke omstandigheid. 9

Zoals reeds vermeld in paragraaf 5.4.1 start elke robot georiënteerd naar een andere robot in de formatie.


102

Vermijden van deadlock Het obstakelontwijkgedrag houdt in dat we, telkens we een obstakel detecteren in de autonome richting waarin we willen rijden, de autonome richting zullen aanpassen door er 90 graden bij op te tellen. Tijdens enkele experimenten is echter gebleken dat de formatie in een hoek kan terecht komen waarbij de robot die zich het verst in de hoek bevindt geen enkele richting kan detecteren waarin hij voldoende ruimte voor handen heeft om zijn autonoom gedrag uit te voeren. In elke richting waarin hij zich draait, ziet hij ofwel een muur ofwel een andere robot uit de formatie. Zonder enig veiligheidsmechanisme dat hiervoor een uitweg zoekt, zal de robot eindeloos telkens 90 graden draaien, een meting doen in die richting en concluderen dat hij opnieuw 90 graden moet draaien, omdat er onvoldoende ruimte is. De oplossing om deze zogenaamde deadlock te vermijden is controleren of we, tijdens het aanpassen van de autonome richting, niet al 360 graden gedraaid zijn. Indien we inderdaad al 360 graden gedraaid zijn, dan zullen we deze cyclus van het algoritme voor deze robot beëindigen zonder het autonoom gedrag uit te voeren. De kans is groot dat de andere robots uit de formatie wel een richting zullen vinden waarbij ze uit de hoek geraken en de robot die vastzat op die manier (wanneer de andere robots voldoende van de hoek verwijderd zijn) ook uit de hoek kan geraken. Aanpassen van autonome richting bij herori¨ entatie Door heroriëntatie van een robot, veranderen we eigenlijk ook zijn autonome richting, gezien vanuit een assenstelsel dat onafhankelijk is van de oriëntatie van deze robot. De autonome richting van een robot is namelijk relatief gedefinieerd ten opzichte van de oriëntatie van deze robot en wanneer deze robot zichzelf heroriënteert, verandert de autonome richting relatief ten opzichte van deze robot niet, maar de richting ten opzichte van het absolute assenstelsel wel. Om de autonome richting in het onafhankelijke assenstelsel toch min of meer constant te houden, moeten we dus telkens wanneer de robot zich heroriënteert, deze autonome richting aanpassen.

5.4.3

Resultaten

Ook bij dit algoritme zijn enkele voorwaarden verbonden aan de omgeving opdat het algoritme correct zou verlopen. Zo mag de omgeving niet toelaten dat een robot achter een hoek verdwijnt (na uitvoering van zijn autonoom gedrag bijvoorbeeld) zodat de andere robots hem kwijtraken. Een voorbeeld hiervan is te zien in figuur 5.8. Robot 1 zal zijn autonoom gedrag uitvoeren in de richting van de pijl en zal op die manier robot 2 kwijtgeraken.


Figuur 5.8: Omgeving waarbij robots elkaar kunnen kwijtgeraken

103

Hoofdstuk 6

Conclusies en perspectieven Inhoudsopgave

6.1

6.1

Conclusies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

104

6.2

Perspectieven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

106

Conclusies

Het uiteindelijke doel van dit onderzoek was algoritmes te implementeren op de Khepera II robots die ervoor zorgen dat de robots in een welbepaalde formatie kunnen komen en ook blijven, terwijl ze zich voortbewegen in een onbekende omgeving. Om dit doel te bereiken dienden echter eerst enkele belangrijke randproblemen opgelost te worden.

6.1.1

Communicatie

Eén van die randproblemen was de ontwikkeling van betrouwbare communicatie tussen de robots. De Khepera II kan communiceren via twee verschillende extensieturrets. In hoofdstuk 2 hebben we eerst communicatie via de High Speed Radio Turret besproken. Deze turret laat enkel communicatie1 toe tussen een robot en een PC en dus dienden we een volledige controle-eenheid op de PC te implementeren die de boodschappen van elke robot doorstuurt naar de andere robots waarmee de PC in verbinding staat (broadcast-mechanisme). Op de PC werd hiervoor met de programmeertaal Java gewerkt die toelaat om verschillende threads naast elkaar te laten werken wat nodig is om tegelijk berichten te kunnen ontvangen van verschillende robots. Verder werd ook een controlemechanisme ingebouwd dat ervoor zorgt dat alle berichten van robot naar PC en omgekeerd beantwoord worden met een acknowledgement zodat betrouwbare communicatie kan gewaarborgd worden. Dit volledige communicatieprotocol dat ontwikkeld werd in het kader van deze scriptie bevat echter heel wat parameters die ingevuld moesten worden. De perfecte parametercombinatie werd pas op het einde van dit onderzoek gevonden zodat voor het formatievormingsgedeelte van dit onderzoek niet met deze High Speed 1

via een draadloze Bluetooth-verbinding

104

Hoofdstuk 6. Conclusies en perspectieven

105

Radio Turret werd gewerkt om de communicatie te verzorgen tussen de robots. In paragraaf 2.2 werd de communicatie met behulp van de Radio Turret besproken. Die laat rechtstreekse communicatie toe tussen robots, zonder dat de boodschappen langs een PC om moeten. Aangezien hier geen controle-eenheid moest ontworpen worden om boodschappen door te geven tussen de robots, was de implementatie een stuk eenvoudiger. Hoewel de Radio Turret standaard al beschikt over een mechanisme om verloren boodschappen te detecteren en desgevallend een retransmissie van het bericht te doen, werd ook hier nog een extra controlemechanisme ingebouwd waarbij, net zoals bij de High Speed Radio Turret (paragraaf 2.1), iedere boodschap beantwoord dient te worden met een acknowledgement.

6.1.2

Sonar Turret

Een tweede belangrijk randprobleem was het gebrek aan sensoren op de Khepera II om nauwkeurige afstandsmetingen uit te voeren. Die zijn nodig om te werken vanuit het principe van relatieve positiebepaling, waarbij we elke robot situeren ten opzichte van de andere robots in de formatie. Eén van de grote voordelen van de Khepera II -robots is echter dat ze over de mogelijkheid beschikken om met behulp van extensieturrets hun functionaliteit uit te breiden. In het kader van dit onderzoek werd dan ook zo’n extensieturret gecreëerd die beschikt over ultrasone sensoren (SRF05-module) die toelaten om zeer precieze afstandsmetingen uit te voeren. In hoofdstuk 3 werd de ontwikkeling van deze Sonar Turret uitgebreid behandeld waarbij we op het einde ook de nadelen besproken hebben, die zich vooral situeren op het vlak van snelheid. Het KNETprotocol waarmee de Khepera II communiceert met de extensieturret bleek hier een grote rol in te spelen. We hebben dan ook een mogelijkheid beschreven om de Sonar Turret te herontwerpen waarbij het KNET-protocol niet gebruikt wordt.

6.1.3

Formatievorming

Eens deze twee belangrijke voorbereidende stappen genomen waren, kon overgegaan worden tot de ontwikkeling van algoritmes voor formatievorming in dit multi-robot systeem. In een eerste fase werd een algoritme ontwikkeld dat enkel gebruik maakt van de IR-sensoren op de Khepera II. Ondanks hun beperkte bereik tot een paar centimeter, bieden ze het voordeel dat ze heel snel en continu kunnen meten. Hierdoor kunnen de robots blijven rijden en hun gedrag in real-time aanpassen, zodat in theorie de formatie behouden kon blijven tijdens het rijden. Er is echter gebleken dat de IR-sensoren van de verschillende robots elkaars metingen be¨ınvloeden, waardoor hun sensorwaarden onbetrouwbaar worden. De robots kunnen bijgevolg hun gedrag niet baseren op de IR-sensorwaarden; formatievorming was op die manier dus niet mogelijk. De later ontwikkelde algoritmes maken dan ook enkel gebruik van ultrasone metingen. Deze werden besproken in hoofdstuk 5. Naast een algoritme om de robots vanuit een willekeurige positie in de vooropgestelde driehoeksformatie te laten komen, werden ook algoritmes ontwikkeld om hen in die formatie hun omgeving te laten verkennen. Hierbij werd ook de mogelijkheid ingebouwd om obstakeldetectie en bijhorend ontwijkgedrag uit te voeren. Bij deze laatste algoritmes werd telkens uitgegaan van twee concurrerende systemen die werken op elke robot. Eén

Hoofdstuk 6. Conclusies en perspectieven

106

systeem probeert ervoor te zorgen dat de formatie behouden blijft, terwijl het andere ervoor zorgt dat de robots hun omgeving verkennen en eventuele obstakels ontwijken. Deze twee systemen werden op twee verschillende manieren ge¨ımplementeerd. In het eerste algoritme zorgden we ervoor dat het gedrag om de omgeving te verkennen en obstakels te ontwijken hetzelfde is voor elke robot. Het gedrag om in formatie te blijven verschilt dan bij elke robot. Hierdoor ligt echter wel de positie die een robot in een formatie inneemt, vast. Dit heeft tot gevolg dat de robot die vooraan rijdt in de formatie een speciale functie krijgt, omdat hij bijvoorbeeld bepaalt hoe de ganse formatie een obstakel ontwijkt. Deze speciale rol kan doorgegeven worden tussen de robots, maar zal altijd door één robot uitgeoefend worden. In het tweede algoritme dat we ontwikkelden, is het net omgekeerd en is het gedrag om in formatie te blijven hetzelfde voor elke robot, terwijl elke robot wel op een eigen manier de omgeving kan verkennen. De laatste aanpak zorgt ervoor dat de robots echt gelijkwaardig zijn in de formatie, zodat dit het meest interessante traject is om op verder te bouwen in de toekomst.

6.2

Perspectieven

Hoewel in dit onderzoek reeds heel wat werk werd verricht op het vlak van formatievorming, is er toch nog bijkomend onderzoek vereist om de ontwikkelde algoritmes te optimaliseren (vooral naar snelheid) en nieuwe algoritmes te implementeren. Die zouden bijvoorbeeld kunnen toelaten om van formatie te veranderen of het aantal robots in de formatie dynamisch aan te passen. De bestaande communicatie, met de gesuggereerde uitbreidingen, biedt voldoende ondersteuning om dit te realiseren. Om de ontwikkelde algoritmes sneller te kunnen uitvoeren, zou de Sonar Turret best geherfabriceerd worden waarbij men het KNET-protocol ofwel vermijdt, ofwel verder optimaliseert en betrouwbaarder (en dus sneller) maakt. Daarnaast zou het gebruik van beeldverwerking een nieuw scala van mogelijkheden bieden waarbij robots onderscheiden kunnen worden van andere objecten en de omgeving beter ge¨ınterpreteerd kan worden. Aan de keuze van de camera moet uiteraard grondig onderzoek voorafgaan waarbij de verschillende mogelijkheden bekeken worden, maar wij raden op het eerste gezicht de CMUcam Vision Turret2 aan, omdat deze als enige toelaat de beeldverwerking op de extensieturret zelf te doen en niet op een afzonderlijke PC. In dat laaste geval zou de robot de beelden eerst naar een PC moeten sturen om ze daar te laten verwerken. Dit zou een aanzienlijke vertraging introduceren en de robot minder autonoom maken dan bij de door ons voorgestelde camera. Het onderzoek kan dus verschillende richtingen uit.

2

http://www.k-team.com/kteam/index.php?site=1&rub=3&upPage=108&page=17&version=EN

Bibliografie [1] Michael J. B. Krieger, Jean-Bernard Billeter, and Laurent Keller. Ant-like task allocation and recruitment in cooperative robots. Nature, pages 992–995, August 2000. [2] Soraya Kouadri Mostéfaoui and Michele Courant. Collective adaptation of a heterogeneous communicating multi robot system. In Proceedings of the International Arab Conference on Information Technology, pages 1038–1044, University of Qatar, Doha-Qatar, December 2002. [3] M. Matskin. Distributed Artificial Intelligence and Intelligent Agents. Syllabus bij de gelijknamige cursus, KTH, Stockholm, 2005. [4] A. Maye and P. Bureau. High speed radio turret user manual. http://ftp.k-team.com/ khepera/documentation/KheBTManual.pdf, 2004. [5] K-Team. Radio turret user manual. http://ftp.k-team.com/khepera/documentation/ RadioTurretManual.pdf, 1999. [6] B. Senepart. Formatievorming in multi-robot systemen. Master’s thesis, Universiteit Gent, 2005. [7] K-Team.

User

manual.

http://ftp.k-team.com/khepera/documentation/

Kh2UserManual.pdf, 2001. [8] K. Thiel. Steuerung eines mobilen autonomen roboters mit selbstorganisierenden karten. Master’s thesis, Fachhochschule Konstanz, 2004. [9] K-Team. Radio base user manual. http://ftp.k-team.com/khepera/documentation/ RadioBaseManual.pdf, 1999. [10] K-Team.

Bios

manual.


KheperaBIOSRefManual.pdf, 1999. [11] P.Bureau.

Programming manual.


Kh2ProgrammingManual.pdf, 2002. [12] Thomas Bräunl. Embedded Robotics. Springer, 2003. [13] The Institute of Electrical and Electronics Engineers. IEEE 802.3: Standard for Carrier Sense Multiple Access with Collision Detection (CSMA/CD), 2002.

107

Bibliografie

108

[14] E. Franzi. Khepera bus and turret specifications. http://ftp.k-team.com/khepera/ documentation/KheperaBus.pdf, 2000. [15] E. Franzi.

K-net communication protocol specifications.

http://ftp.k-team.com/

khepera/documentation/KheperaNET.pdf, 2000. [16] K-Team. Sonar user manual. http://ftp.k-team.com/koala/sonar/SonarManual.pdf, 2001. [17] MAXIM. +5v, low-power, parallel-input, voltage-output, 12-bit dac. http://pdfserv. maxim-ic.com/en/ds/MAX530.pdf, 1999. [18] B. Schrauwen, M. D’Haene, D. Verstraeten, and D. Stroobandt. Framework for compact fpga implementations of spiking neurons. Technical report, Electronics and Information Systems Department, Ghent University, Belgium, 2004.

Formatievorming in multi-robot systemen

Recommend Documents