cfiséty22.3
`
`.5In:3.2?
`22:1tr.
`
`3,.E:
`
`.,W?.?.sx
`3%...
`
`v:3
`
`Emzsfix
`922.:pf..
`
`fr;,
`
`u3
`
`tér.
`
`a_g
`
`“_mM,;
`
`17,:x3”
`
`is
`
`Bf,hg
`
`Pr"
`ecasffe Posi am
`
`End
`
`Eng
`
`.
`
`“muX.23%
`
`3*":Z:*z~:~: '
`
`“Liz.,42..
`
`;.7
`
`1454.;4.;s.,
`
`wcwW$.,,(,.::\
`
`

`
`538
`
`Chapter 28 *9 Searching for Precision
`
`introduction
`
`This third and last chapter of Part HI is dedicated to c ontests based on some spe~
`cific ability. Occasionally, speed is important, too, but not as much as in the com-
`petitions described in Chapter 26, and while two or more robots may perform at
`the same time on the same field, physical Contact is not the main goal as was the
`case in the competitions of Chapter 27.
`These abilities include what in Part I we describe
`cl as the most challenging
`tasks for MINDSTORMS robots: finding and
`grabbing objects (Chapter 11), and
`knowing precise positioning (Chapter 13).The
`need to use them in a contest
`makes your mission even more demanding:You must consider the interference
`that comes from sharing the playing field with other robots, that may voluntarily
`or involuntarily disturb the action of your robot. The recipe for success is the
`same as proposed in the previous two chapters.This applies to any kind of con-
`test: study the rules, define a strategy, make a few assumptions about the oppo-
`nents, build a prototype, experiment with it, test the software carefully
`and
`rebuild everything from scratch until you are satis
`fied. In other words, you need
`some ideas, some skills, and lots of patience!
`The last challenge described in the chapter——~Soccer——shows an interesting
`variation on the theme of object finding: It is the object itself——the ball——that
`guides the robot to its position, through the emission of IR light You will dis-
`cover that this change in the nature of the problem is enough to simplify the
`robots requirements considerably, to the point where its sofiware isn’t so different
`from that used to implement the simple light following algorithm of Chapter 18.
`
`Precise Positioning
`
`V
`, or ietuin, to a
`specific poi.nt. The robot whose degree of error is smallest, wins.You can define
`many implementations of that simple statement, each one with its own peculi
`ari-
`ties.As always, even a small change in the rules can have radical effects on the
`ficulty of the challenge.A Very simple version is: Starting fiom
`a predefined
`point, the robots must move forward until they hit an obstacle, then turn in place
`180° and return to the spot where they began.The obstacle will be the same, at
`the same distance from the start for all the robots, and the cont
`est may require
`many runs with different distances. It’s important that the rules specify that the
`robots must turn 180° before returning to the starting point, otherwise most of
`them will simply go in reverse!
`
`dif-
`
`
`
`
`
`

`
`Searching for Precision - Chapter 28
`
`539
`
`‘With either one solution or the other, you may manage to go straight, but
`you still have to turn precisely 180°.This is the most critical point, because even
`a small error in the angle will leave your robot very far from the starting point.
`Do you remember What We said about tuning the turning ability of the Logo
`Turtle in Chapter 23? Use the distance between the wheels to adjust the turning
`angle so the U—Turn is equal to a whole number of counts of your sensor.
`Thorough testing is, as always, your ticket to success.
`A challenge based on positioning may be made significantly more complex
`by simply adding more segments and checkpoints to the route. For example,
`instead of a round trip you can prepare a triangular path~——ask the robots to stop
`in an.y vertex and measure the deviation between their actual position and the
`expected one. Each robot should have an easily identifiable part to use as :1 refer-
`ence point for measuring the starting and ending points of the journey——for
`example, a vertical axle with one end very close to the ground.
`
`E:3
`
`
`
`
`
`
`lfyou’re the one who decides the rules, calibrate the difficulty of the contest by
`setting the limit on the number of parts admitted. For example, a dual differential
`drive like our LOGO Turtle can be very precise, but requires two differential gears
`and a rotation sensor. Limiting the equipment to just the l\/HNDSTORMS set will
`make the contest fair to a larger number of participants, but more difficult.
`Have you any initial ideas about how‘ you would make a precise run—and—
`fetch robot with only l\/llNDSTOR.MS parts? At this point in the book you
`should have many ideas, however, let’s do this exercise together. Starting from the
`mobility configuration, you can proceed by a process of elimination: steer, tri-
`cycle, and synchro drives don"t turn in place; sl<id—steer does but introduces track
`slippage, which is very bad for precise positioning; dual differential drive won’t
`work because of the lack of a second differential gear, thus you end up with the
`tried~and—true differential drive, with its handicap in going straight.
`The first approach that comes to our mind requires you emulate two rotation
`sensors with the touch sensors, and monitor the turns of the right and left wheels
`so as to keep them synchronized. (You still have the light sensor for the bumper!)
`Getting ideas from Chapter 8, you can also use a diflerential gear to monitor the
`difference in speed between the two wheels (Figure 8.2).The light sensor could
`face a sort of black and white disc connected to the differential, so you will drive
`the robot more or less like a line follower, slowing one of the" motors when it
`reads too black and the other when it reads too white.
`
`
`
`
`
`
`
`

`
`
`
`Chapter 28 - Searching for Precision
`
`Finding and Coiiecting Things
`In l999,]oel Shafer proposed a tou
`gh challenge unlike any that had been pre-
`sented in the LEGO community p
`reviously. In it, a robot had to navigate the
`room, pick up three empty soda ca
`ns, and return to the starting point. Active nav-
`igational aids, like beacons, were not alloWed.]oel’s was a remote challenge, that
`is, there wasn’t any specific place or time for the event, rather the participants had
`to send pictures and clocumentations of their robot and its program.
`_]oel’s challenge was new and tough; it created a lot of traffic in the
`
`
`
`E
`
`h 0 ened the Wa
`to similar
`P
`Y
`com etitions of a Vet demandin nature.\7Ve’ll ex lore some variations on these
`P
`Y
`5
`P
`types of competitions in the following sections, and describe some of the naviga-
`tion and search techniques you could employ.
`
`Maxwell's Demons
`
`cold ones in a room, supposedly
`contradicting the second law of thermodynamics. In Davids challenge, each robot
`must distinguish black LEGO cubes fi‘om white ones, and push as many white
`cubes as possible to its side of the playing field while at the same time pushing as
`many black cubes as possible to its opponents side.
`This is a very complex challenge that requires your robot be able to:
`I Navigate the playing field.
`
`Find the cubes.
`
`5 Recognize their color.
`
`5 Capture them.
`
`Push them into the proper territory.
`
`
`
`

`
`Searching for Precision - Chapter 28 54'}
`
`Though a very attractive challenge, we at ItLUG decided to start with a
`slightly simplified version where the colors of the cubes don’t matter, just their
`numbers,
`
`
`
`Stealing the Cube
`
`
`
`
`
`
`
`
`
`
`During a given time period (three minutes) each robot must try and accumulate
`as many cubes as possible on its side of the playing field, taking them either from
`the central border line where they are placed at the beginning or from the oppo-
`nent’s f1eld.The robot can use only one RCX and one light sensor, but there is
`no limit to the number of other original LEGO parts and sensors that can be
`used; non—LEGO custom devices are not allowed.
`
`As in Davids original rules, the cubes are made of six 2 X 4 bricks arranged
`in three interlaced layers of two bricks.The cubes are topped with tiles so as to
`make them perfectly smooth and cubic.
`Our field has a white side, a black side, and a gray border. We decided on a
`very restrictive size limit for the robots:They must fit into a space 20 x 20 studs
`square. Other rules state that the robots must push or hold just one cube at a
`time; they can push more than one if this happens by chance, but cannot be
`explicitly designed to do this. Each match starts with seven cubes placed along
`the borderline and the robots situated on their respective sides.
`This challenged immediately proved very difficult.The first obstacle we had
`to face was navigating a three~color playing f1eld.As we explained in Chapter 4,
`the LEGO light sensors reads the average rcflection of a small area, thus making it
`impossible to tell a black~white borderline region fiom a gray one. How would
`you have done it? The simplest answer required that the competitors increase the
`complexity of the code a bit and test two or more closed readings of the sensor,
`accepting the value only when they were stable.Theory is one thing, practice
`another: keeping the robots inside the field was not easy, but almost everybody
`succeeded in the task.
`
`
`
`The next difficulty came fiom the cubes. Chapter ll describes how to use
`proximity detection to search for objects, but this technique is not applicable to
`two robots at the same time, because their IR emissions interfere with each other
`and alter the reliability of the readings.Add to this the fact that only one light
`sensor was allowed, which was necessary to navigate the field, and this definitely
`excludes proximity detection. Everyone decided to use touch sensors to monitor
`collisions with the cubes-in other words, the robot would navigate the pad until
`they ran into a cube. Unfortunately, the objects couldn’t be detected with a
`
`
`
`
`
`
`
` 'il.'l.fi‘erFin*:.p.-7£'i:nx'.-4‘Av‘I‘sw1i:r.vi!:‘.yhI'w?'ri'rv§-wt-‘sifiiwzéwi-|~:fi£§‘*&{-77:.r'£-‘u‘-.¥?l<‘lTv*
`
`
`
`
`

`
`
`
`Chapter 28 ° Searching for Precision
`
`simple front bumper, because they were too lightweight and slippery to exert any
`pressure on the touch sensor. We saw many different techniques offered as solu~
`tions to this: Our robot, the one shown in Chapter 11 (Figure 11.1.2), used a top
`bumper activated by the height of the cube. Other competitors adopted different
`harvesting systems——for example, a sort of gate that closed when a cube was
`inside, or a lever that blocked the cube against one side of the robot.
`Most of the robots based their search for the cubes on a purely random navi-
`gation, While the more sophisticated ones used a limited knowledge of their posi—
`tion in regard to the borderlines of the field, applying the dead~reckoning
`techniques described in Chapter 13.The idea of using relative positioning
`methods was good, and the colors of the different areas of the field provided some
`external references to reset the errors that internal odometry would inevitably
`accumulate. If a robot knows its position, it can more efficiently scan the field,
`passing precisely once——and only once—through any point. Unfortunately, the
`approach didn’t end up Working very Well, and proved no b etter than random
`navigation. The problem came from collisions: each time a robot was hit by the
`opponent, it got its position and orientation slightly changed, and this was enough
`to make the internal position information totally unreliable.
`
`
`
`
`
`
`
`
`
`
`, ¢.駫3§~ain,i
`i
`.
`.
`-
`‘
`Iay‘LnGbOfiY.elSe*.‘had thought ,0f;‘HiS"—r’Db0i;W€fii'
`I
`t,h;é’vj,2;¢i;i;;§.iii.ne?‘between thé.fiei,ds; wjhegrethe‘ I
`,1
`A
`W
`. Set up, then? 'tu'_rnéd'i9QJdeg,‘r,éés. a7nCl‘fo'lioiAzeoi the line at
`I
`, ;kickinjg* the tin;
`into its _fieid'.: gAft_er}ja raw se5cjo,nds7,» most’
`were -i_nfsfide._‘:it—s ’teiEri'tory, and -the spawn‘: had ,tio),_figh't‘_ _a "
`'- ‘I\Jo't‘.“ 'r2sfiejd«,w'ith1_th1iis» initial -adva_n‘i;ag“e,’ cau"jao%_s robot, ‘conti_nfu_;eC}i
`the o\pponen1TiS' fieidwith le‘thai- prec'isii:iin,‘_pl.romptiy
`"i‘;'fj Carryingeifiys’gcapttfred ,fcube to iitS“sid;é...»_it
`.priovi_e';d_'.by Ffa-r tolhelthe
`I}5?5i0“t9'95ie’C°mPail???-.'_».{J
`=
`:
`-~
`1»
`2
`t
`1
`.
`”
`‘f1T_his cziicelageiiin Aprovesthoviziditferent ‘setsi-.0‘? rules .affect a"com'peti-
`_ °ftion:- if the staffing position of thécubes had lbefein r_anciom,_ori itiauhchirig =
`been Zfcfbiddeti, Guido cou_lc'in*t have used his tri'ci<.—_ _»
`
`=
`
`l
`
`
`
`

`
`Searching for Precision ° Chapter 28 543
`
`Variations on Coiiecting
`The theme of finding and collecting objects admits infinite variations.The size
`and shape of the objects have a strong influence on the architecture of the robots.
`Marbles, for example, are quite different from empty soda cans or LEGO cubes,
`because they tend to roll away at the slightest touch, thus requiring a very cau-
`tious approach.
`Also, instead of placing two robots in the playing field at the same time, you
`can organize the challenge so just one robot runs at a time, evaluating its perfor-
`mances against time. For example, counting the number of objects collected during
`a prearranged interval, or measuring the time it needs to harvest all of them.
`
`Pinging Soccer
`
`Soccer, in an extremely simplified form, is a rather suitable game for small robots.
`By “simplified” we mean that the robots don’t actually kick the ball but instead
`push it toward the goals. Other simplifications include the absence of fouls, throw-
`ins, and all other rules except for the one that says each goal scores a point.
`The required abilities would be similar to those explained earlier about
`finding and collecting objects, with the difference being that —‘there’s only one
`object, the ball, for two teams who must take it and score a goal. However, with
`the adoption of a special field and a special ball, you can trim down the essential
`skills to a level where even an inexperienced child, with some tips, can program a
`basic robot to play the game.
`In i999, during the first l\/lindfest at MIT, we saw a very entertaining version
`implemented by Henrik I-lautop Lund and Luigi Pagliarini fi*om the LEGO Lab
`at the University ofAarhus. The field was covered with a simple linear gradient,
`black at one end and white at the other, and there were raised edges all around,
`with gaps to represent the nets.The players featured a single RCX with five sen~
`sors: three light and two touch (the light and touch sensors were combined in
`pairs on the same port as described in Chapter 4). One light sensor, facing down,
`allowed simple navigation on the field, while the other two, facing forward, were
`aimed at finding the ball. The touch sensors were connected to bumpers in order
`to detect collisions with the edges or with other players.
`The ball was a special, active ball: two to three inches in diameter, made of
`clear plastic, it was filled with rechargeable batteries and IR LEDS so to be easily
`detected by light sensors. The reasons that Lund and Pagliarini used two fiont
`light sensors is that they were able to program a simple method of finding the
`
`
`
`
`
`
`
`
`
`

`
` Chapter 28 ° Searching for Precision
`
`ball.\X/ith two sensors, they could make the robot turn in place until both the
`sensors read a very high value, and that was the direction of the ball.The standard
`chassis of the robot and simple commands allowed young children to program
`their soccer players with different strategies without having to Worry too much
`about the details.
`
`We replicated this setup with Marco Berti a few months later, scheduled to
`be shown during an exhibition in Italy Like the originals, the robots were differ-
`ential drive, but with two light sensors instead of three. The front of the robots
`was shaped so as to push the ball while going forward.
`Building your own soccer player is not a difficult task-———you’ll find the greater
`challenge is in the construction of the ball.\lVe used one of those clear plastic
`balls found in toy Vending machines for children, the kind that usually have a
`little prize inside. The making of the inner electronics requires some experience
`in soldering and in assembling small parts. Fit the inside with as many IR LEDS
`as possible, and with rechargeable batteries of your choice. Drill small holes in the
`surface of the ball to include a female connector and a small switch so you can
`turn it on and of and recharge the batteries without opening it. This is the most
`difficult part of the job, because you must keep the surface smooth and the COG
`as close as possible to the center ofthe ball so it rolls smoothly (Figure 28.1)
`Figure 28.‘? Marco Berti’s 3R Ball
`
`
`
`

`
`Searching for Precision - Chapter 28
`
`545
`
`
`
`The field may be improved using the two attractors gradient described in
`Chapter 13.This geometric pattern has the property that, if you follow the
`darkest path from any of its points, you arrive at the black attractor, while if you
`choose the clearest path, it drives you to the white one. Using such a pattern, it’s
`very easy for the robots to reach the goals that correspond to the attractors by
`employing a very simple navigation algorithm.
`The program is not too difficult to write. Make your robot turn in place
`searching for the ball until it finds it (the algorithm is actually very similar to the
`one we described in Chapter 18 to implement light following). If it doesn’t, make
`it move a bit in any random direction and look around again.T\X/hen it finds the
`ball, it moves forward to catch it and then starts going toward the opponents net.
`
`Summary
`
`The competitions we talked about in this chapter require some abilities that, in
`Part I of the book, we described as the most challenging to implement: finding
`objects and knowing where you are.
`If these activities demonstrated here prove difficult to implement when you
`build a robot for yourself, situating them in the context of a competition makes
`your mission even more diff1cult.This happens because you must push the per-
`formance of your robot to its maXinium.You have to consider all the details,
`optimize the software, and reach the highest possible level of reliability. However,
`most of the hitches derive from the fact that your robot is not alone in the field,
`and the interference with its opponent will disturb its behavior. For example, IR
`proxiniity detection can’t be used by two robots at the same time, and dead reck-
`oning calculations to estimate the position of the robot may be frustrated by col-
`lisions against the opponent.
`The Soccer competition we described in this chapter is a good example of
`how a few changes can radically affect the solution to a problem. It also shows
`the practical application of two techniques described in Chapter 13 regarding
`absolute positioning: the use of an IR beacon, and a pad with a special pattern
`that eases navigation. In fact, the IR ball guides the robot to it, and after the
`robot gets the ball, it can find the way to the goal following the gradient on the
`pad.Tl1is simplification is so effective, that the software of the robot becomes
`similar to a simple algorithm we covered earlier in the book: light following.
`in this kind of competition, the contest sponsor can also suggest, or impose, a
`standard chassis built with just MINDSTORMS parts. This would move the chal-
`lenge of the contest completely to the software side.
`
`
`
`
`
`

`
`Chapter 28 ° Searching for Precision
`
`Cube collecting or soccer playing requires a complex behavior made of many
`different actions that need to be coordinated together well. If you decide to take
`up the challenge, we suggest you think both your hardware and software in terms
`of subsystems.This Way they will be easier to test, debug, and maintain.\X/rite
`your program with a top level supervisor that manages small subrout_ines corre-
`sponding to the basic actions the robot has to perform: navigation, object detec-
`tion, and object collection. Mastering this kind of challenge Won’t be easy, but as
`with most difficult things in life, your satisfaction will be directly proportional to
`the effort you expendl