LIST OF FIGURES

Figure p


2.1: Triangulation of a convex polygon................................................... ..................6

2.2: Triangulation of a non-convex polygon. The area ADC is negative and is subtracted
 from area A B C ....................................................... 6

2.3: A sam ple 64x64 resolution m ap .............................................................................. 7

2.4: Illustration of line-of-sight m ethod..............................................................................8

2.5: Preliminary implementation of the line-of-sight algorithm................ .............. ....10

2.6: The shadow area is the grey area behind the obstacle. ................................................10

2.7: Resulting shadow areas for a simple two robot system (20x20 grid) ..........................11

2.8: A plot of the shadow areas for a single robot placed at every point on the map
 (except obstacle locations) ......... .. ............... .................................... .............. 12

2.9: Illustration of the 'linesintersect' method A file contains a list of all line segments
 that m ake up each obstacle in the m ap..................................... ....... ............... 14

3.1: B C/A B = G olden Section R atio............................................. ................................... 18

3.2: Illustration of the Golden Section Method ........................................ ............... 19

4.1: Single-peak function .................. .................. ................. ......... .. ............ 26

4 .2 : D ouble-peak function .......................................................................... .....................27

4.3: Sample string types and biased roulette wheel .................................... ............... 28

4.4: Binary String Representation of Robot's (x,y) Position.............................................. 30

4.5: Genetic Algorithm Flow Diagram ............................................................................ 32

5.1: Sam ple GU I w written in V C++......... ................... ......... ................................ 34

5.2: R results for M apl ................. .. ........ ....... .................... ............ 35