PAGE 1 MULTIPLE VEHICLE POSITIONING SIMULATION AND OPTIMIZATION By ERICA FRANCES ZAWODNY A THESIS PRESENTED TO THE GRADUATE SCHOOL OF THE UNIVERSITY OF FLORIDA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE UNIVERSITY OF FLORIDA 2003 PAGE 2 Copyright 2003 by Erica Frances Zawodny PAGE 3 ACKNOWLEDGMENTS I would like to thank Dr. Carl Crane for being the chairperson of my committee and for providing advice and encouragement throughout. In addition, I would like to thank Dr. John Schueller and Dr. Gloria Wiens for serving on my committee and offering their expertise. I would especially like to thank Donald MacArthur for his undying support and encouragement throughout this experience. I thank my parents, Joe and Yvonne, and my brother, Nikolas, for all of their love, support, and encouragement. iii PAGE 4 TABLE OF CONTENTS page ACKNOWLEDGMENTS.................................................................................................iii LIST OF FIGURES...........................................................................................................vi ABSTRACT.......................................................................................................................ix CHAPTER 1 INTRODUCTION...........................................................................................................1 Multiple Robot Positioning and Communication...........................................................1 Optimization...................................................................................................................2 2 MODELING THE PROBLEM........................................................................................5 A Map of Points..............................................................................................................5 Polygon Triangulation Approach.............................................................................6 Grid Based Approach...............................................................................................6 Initial Line-of-Sight Method...........................................................................................7 Initial Shadow Area Calculation...................................................................................10 Line-of-Sight and Shadow Area Method Revisited......................................................12 Line Segment Intersection Method........................................................................13 Line-of-Sight Determination..................................................................................14 Shadow Area Calculation.......................................................................................15 Preliminary results.................................................................................................15 3 AN OVERVIEW OF OPTIMIZATION TECHNIQUES..............................................17 Background...................................................................................................................17 Golden Section Method................................................................................................18 Gradient Techniques.....................................................................................................21 Steepest Descent...........................................................................................................21 Monte Carlo Integer Programming...............................................................................23 4 GENETIC ALGORITMS..............................................................................................25 Traditional Methods versus Genetic Algorithms..........................................................25 Simple Genetic Algorithm............................................................................................27 iv PAGE 5 Reproduction..........................................................................................................28 Crossover...............................................................................................................28 Mutation.................................................................................................................29 Genetic Algorithm Implementation..............................................................................29 5 EXPERIMENTS AND RESULTS................................................................................33 Graphical User Interface...............................................................................................33 6464 Resolution Maps................................................................................................34 Map One.................................................................................................................34 Map Two................................................................................................................36 Map Three..............................................................................................................39 Map Four................................................................................................................41 Map Five................................................................................................................42 Map Six..................................................................................................................44 256256 Resolution Maps............................................................................................46 Map One.................................................................................................................47 Map Two................................................................................................................49 Map Three..............................................................................................................51 Map Four................................................................................................................53 Map Five................................................................................................................55 Map Six..................................................................................................................57 Exhaustive Search Technique versus Genetic Algorithm Technique...........................60 Comparison #1.......................................................................................................60 Comparison #2.......................................................................................................62 Comparison #3.......................................................................................................63 6 SUMMARY AND CONCLUSION..............................................................................66 APPENDIX A SOURCE CODE FOR FINAL ALGORITHM............................................................69 B MAP MAKER SOURCE CODE..................................................................................93 LIST OF REFERENCES...................................................................................................97 BIOGRAPHICAL SKETCH.............................................................................................98 v PAGE 6 LIST OF FIGURES Figure page 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 ABC...........................................................................................................6 2.3: A sample 6464 resolution map.....................................................................................7 2.4: Illustration of line-of-sight method.................................................................................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 (2020 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 lines_intersect method A file contains a list of all line segments that make up each obstacle in the map.......................................................................14 3.1: BC/AB = Golden Section Ratio......................................................................................18 3.2: Illustration of the Golden Section Method.....................................................................19 4.1: Single-peak function.......................................................................................................26 4.2: Double-peak function.....................................................................................................27 4.3: Sample string types and biased roulette wheel...............................................................28 4.4: Binary String Representation of Robots (x,y) Position.................................................30 4.5: Genetic Algorithm Flow Diagram..................................................................................32 5.1: Sample GUI written in VC++.........................................................................................34 5.2: Results for Map1.............................................................................................................35 vi PAGE 7 5.3: Map 1 convergence rates for 2-5 robots after 100 generations.......................................36 5.4: Results for Map 2............................................................................................................37 5.5: Map 2 convergence rates for 2-5 robots after 100 generations.......................................38 5.6: Results for Map 3............................................................................................................39 5.7: Map 3 convergence rates for 2-5 robots after 100 generations.......................................40 5.8: Results for Map 4............................................................................................................41 5.9: Map 4 convergence rates for 2-5 robots after 100 generations.......................................42 5.10: Results for Map 5..........................................................................................................43 5.11: Map 5 convergence rates for 2-5 robots after 100 generations.....................................44 5.12: Results for Map 6..........................................................................................................45 5.13: Map 6 convergence rates for 2-5 robots after 100 generations.....................................46 5.14: Sample ppm file and header information (first 3 lines)................................................47 5.15: Results for Map 1..........................................................................................................48 5.16: Map 1 convergence rates for 2-5 robots after 200 generations.....................................49 5.17: Results for Map 2..........................................................................................................50 5.18: Map 2 rates of convergence for 2-5 robots after 200 generations................................51 5.19: Results for Map 3..........................................................................................................52 5.20: Map 3 rates of convergence for 2-5 robots after 200 generations................................53 5.21: Results for Map 4..........................................................................................................54 5.22: Map 4 rates of convergence for 2-5 robots after 200 generations................................55 5.23: Results for Map 5..........................................................................................................56 5.24: Map 5 rates of convergence for 2-5 robots after 200 generations................................57 5.25: Results for Map 6..........................................................................................................58 5.26: Map 6 rates of convergence for 2-5 robots after 200 generations................................59 5.27: Results for Comparison #1...........................................................................................61 vii PAGE 8 5.28: Results for Comparison #2...........................................................................................62 5.29: Convergence Rates for Comparison #2........................................................................63 5.30: Results for Comparison #3...........................................................................................64 viii PAGE 9 Abstract of Thesis Presented to the Graduate School of the University of Florida in Partial Fulfillment of the Requirements for the Degree of Master of Science MULTIPLE VEHICLE POSTIONING SIMULATION AND OPTIMIZATION By Erica Frances Zawodny May 2003 Chair: Carl D. Crane, III Major Department: Mechanical and Aerospace Engineering There is a wealth of research being performed in the area of autonomous vehicles. Much of the research involves development of platforms and integration of computers and various sensors to create an intelligent robot. With the development of multiple robotic agents comes an interest in multiple robot interaction. There are two limiting factors with this type of research: robot cost and robot size. Therefore, much of the research is performed in simulation initially and later implemented on actual systems. In order to optimally place robots throughout a region an algorithm should first be developed and tested in simulation. Related work has been done on optimal placement of sonar beacons throughout a region for a beacon based navigation system. There are several issues that need to be addressed when positioning multiple robots. The number of robots to be placed, the size of the region, the obstacle locations within the region, and sensor limitations are all important issues that are addressed in the solution of this problem. In addition, the optimization technique chosen will have ix PAGE 10 significant effect on the results and the time it takes to determine a solution. This raises the issue of how to determine where the robots should be positioned for a given environment. This particular problem is an optimal placement type of problem. Problems of this nature and search problems can be solved using genetic algorithms. Genetic algorithms are a type of directed, randomized search technique that is conceptually analogous to the process of natural selection as seen in nature. This thesis utilizes genetic algorithms to solve this multiple robot placement problem. The software developed can be applied to any map containing known obstacles and a user-specified number of robots. The program will try to minimize the combined shadow area (area that is not visible to any of the robots) for a specified number of robots by placing them at different locations until an acceptable solution is found. The result of this research is software that can take a two-dimensional map with known obstacle locations and determine where to position multiple robots such that maximum coverage is ensured and line-of-sight communication among the robots is maintained. A graphical user interface allows ease of use and displays results to a window. This work can be extended to the three-dimensional case where the terrain and elevation are taken into account. In addition, it could later be implemented on a multiple agent ground vehicle system or air-ground vehicle system. x PAGE 11 CHAPTER 1 INTRODUCTION A variety of research is being done in the area of autonomous mobile robots. Much of this research involves the development of platforms and integration of computers and various sensors to create an intelligent robot. With the development of multiple robotic agents comes an interest in multiple robot interaction. Researchers in this area explore how robots interact with one another and their surroundings. Different experiments have been performed in simulation and have been implemented on multiple robot systems [5]. Actual implementation has been on a smaller scale due to cost constraints. Therefore, simulation plays an invaluable and important role in this type of research. Different algorithms may be tested in simulation before implementation on a multi-agent system. Multiple Robot Positioning and Communication This research focuses on a scenario where a mobile robot will operate in an obstacle-strewn environment and must maintain line-of-sight communication with the operator control unit. This line-of-sight communication will be facilitated by using mobile communication repeater robots to chain together a total line-of-sight path from the mobile robot to the operator control unit. The objective of this research is to determine where to best position the communication repeater robots to maximize the area of the region in which the mobile robot can operate while maintaining communication to the operator control unit. Positioning and placement of multiple communications repeater robots depends on several factors: the number of robots to be positioned, the size of the 1 PAGE 12 2 search space (map) and location of obstacles within the map, and communication. While maximum coverage of the map is desired it is also necessary that the communication repeater robots maintain line-of-sight communication among one another. Optimal positioning of all robots requires maximizing coverage while maintaining line-of-sight communication. When positioning the robots they must be able to communicate to at least one additional robot. Lastly, the scope of this research is limited to a two-dimensional case where the region of operation and the obstacles can be represented by polygons. One area of concern involving this type of simulation problem is the need to have a general approach such that it can apply to different maps, a different number of robots and different types (shapes) of obstacles. This problem is addressed by modeling the map using a grid-based approach. The map is discretized into grid points and the obstacles within the map are represented by a series of grid points. The robots can be placed at any of these grid points as long as they do not coincide with an obstacle. This method eliminates the need for calculating complex areas and provides a simplified technique for representing the desired map. Optimization Another area of concern is the how to determine the position of all robots such that they satisfy the stated requirements. This is an optimal placement problem and can be solved using many different techniques and an overview of these techniques is presented in Chapter 3. There are several variables in this problem: number of robots, size of the search space (map), and number of obstacles in the map. Due to this variability, genetic algorithms will be used to determine optimal robot positioning. PAGE 13 3 Genetic algorithms are directed, randomized search techniques that are conceptually analogous to the process of natural selection in nature. A genetic algorithm library, GAlib [12], will be implemented to perform reproduction, crossover, and mutation. The initial population will be selected randomly and will consist of the desired number of robots and their corresponding positions. Possible solutions are represented by fixed-length strings of bits. The best-fit individuals are determined from a fitness function and they are selected for reproduction to form the next generation. The fitness function measures how well the map is covered by the current robot configuration. Mutation is introduced by flipping a bit in a randomly chosen string. This process is repeated in succession until an acceptable solution is obtained. This research will use a genetic algorithm to determine the optimal robot positions for a given map. It should be noted that while genetic algorithms provide a method to finding a solution to a particular problem, it might not always be the globally optimal solution. The benefit of using genetic algorithms over other optimization techniques is that the algorithm will always converge to a solution albeit not always optimal, and will converge in a relatively short time for a fairly large search space. Traditional optimization techniques require a well-defined function that can be optimized and convergence can take time, but in most instances the optimal solution will be found. This software will allow the user to select the number of robots and a map. The program interprets the map and then proceeds to minimize the combined shadow area or unseen area. This area is the cumulative area that cannot be seen by any of the robots for the current robot configuration. Minimization of the shadow area allows for the maximum map coverage. The algorithm will terminate when it obtains the optimal PAGE 14 4 solution, a shadow area of zero, or after it cycles through a specified number of generations. A graphical user interface will be used to display the solution and the map along with the shadow area, if any. Additional statistics are saved to a data file for analysis. PAGE 15 CHAPTER 2 MODELING THE PROBLEM There were several areas that were addressed before programming the simulation commenced. It was decided that the Visual C++ programming package would be used for all programs and graphics. The next step was to determine how to represent a map and obstacles contained within a computer program. Another element of the problem was determining if line-of-sight is maintained between at least two robots. Finally, there is the issue of determining the combined robot shadow areas, i.e. the region where line-of-site communication is not maintained. All of these issues will be addressed in detail throughout this chapter. It was desired to be able to represent this problem in the most general manner. The generality will allow the algorithm to scale easily to account for larger maps or a greater number of robots. A Map of Points A significant amount of effort has been put into how to represent a map and the obstacles contained within. Assuming that the boundary edges of the map are known and the obstacles are known, the initial step was calculating the area of the obstacles and later, the shadow regions. 5 PAGE 16 6 Polygon Triangulation Approach The initial approach that was considered was to determine the exact area of each obstacle and the corresponding shadow area using polygon triangulation. This involves breaking a polygon into triangular sections, determining the area of each triangle, and then summing the areas [9]. This method is straightforward when the polygon is convex (see figure 2.1). When dealing with a non-convex polygon a negative area must be calculated and then subtracted from the surrounding boundary (see figure 2.2). This method provides a very reliable estimation of the areas but became computationally intensive when calculating the shadow areas. 4 7 5 3 2 1 0 ABC D N egative Area 6 Figure 2.2 Figure 2.1 Figure 2.1: Triangulation of a convex polygon Figure 2.2: Triangulation of a non-convex polygon. The area ADC is negative and is subtracted from area ABC. Grid Based Approach This method simplifies the map to a grid of M N points. The obstacles contained within the map can be modeled by a matrix of 1s and 0s. All the grid points that make up an obstacle are represented by a while empty space is indicated as . PAGE 17 7 Figure 2.3: A sample 6464 resolution map This simplification greatly reduces area calculations and eliminates the need to differentiate between convex and non-convex polygons. A sample map is shown in figure 2.3. The map information is stored in a file that contains the points (x,y) that make up the obstacles. The program reads this file and is able to display the map to the screen graphically. An added benefit this method provides is the ease in displaying the graphics to the application window. A matrix can represent the map in figure 2.3 and the robots can be placed at points within the matrix, other than those occupied by obstacles. Initial Line-of-Sight Method Robot communication is an area that is essential to robot development. Whether robots are communicating with a human operator or amongst themselves, there are limitations. Much of the time the limiting factor is that the robot must maintain line-of-sight to be able to communicate. Line-of-site communications is often a mission PAGE 18 8 requirement for security of command and control and for this reason recent advances in communications such as wireless Ethernet that are typically omni-directional are not considered. This work is based on the premise that the robots must maintain line-of-sight in order to communicate with a base station or another robotic entity. Therefore, initial steps were taken to develop an algorithm that determines if line-of-sight exists between two robots. Line of sight is determined for two robots whose positions are known. Simply put, it is necessary to determine if a line segment drawn between the two robots intersects any of the known obstacles. With the grid-based approach, this can be done rapidly by starting at robot 1s position and then moving to the next adjacent grid position that moves closer to robot 2s position. A start angle (q start ) is calculated based on the (x,y) positions of the two robots. The current angle (q current ) is initialized to the start angle and the current position (x c ,y c ) is initialized to the position of robot 1. The value of the Figure 2.4: Illustration of line-of-sight method Robot 1(x1,y1)Robot 2(x2,y2)270 North0 East90 North180 WestIIIIIIIV start angle 270 South PAGE 19 9 starting angle will determine which direction to traverse, north, south, east or west (see figure 2.4). This method will determine if there is an unobstructed path between the two robots. The algorithm divides the map into four quadrants. For example, if q current is between 0 and 90 (quadrant I) and less than q start then x c will be incremented by one, indicating a move due east. Otherwise, y c is incremented by one, indicating a move due north. The algorithm proceeds in a similar fashion when q current is in a different quadrant of the map. The algorithm is terminated when x c or y c is equal to the x or y position of robot two. Another matrix is created that is the same size as the map that contains the line-of-sight information. A indicates the position of robot 1 and robot 2 in the matrix. If line-of-sight exists all intermediate points have a value of in the matrix as well. The rest of the points have a value of . This method is beneficial because it minimizes the number of calculations. Instead of having to scan all of the points in the map, it is only necessary to check the points between the two robots in question. A preliminary graphical user interface was created to demonstrate the line-of-sight algorithm (see figure 2.5). The user is able to enter the locations of robot 1 and robot 2. The squares indicate the robot positions and the collection of points represent obstacles. The points connecting the two robots are filled in to indicate the line-of-sight path. This method was initially tested on a simple 2020 grid but is easily applicable to larger areas. PAGE 20 10 Figure 2.5: Preliminary implementation of the line-of-sight algorithm Figure 2.6: The shadow area is the grey area behind the obstacle. Initial Shadow Area Calculation Determining the shadow areas posed a difficult problem because the area behind an obstacle is being calculated. The first issue was trying to formulate the area to be calculated (see figure 2.6). The polygon triangulation method would add complexity to the problem because a polygon would first have to be created using projected lines and the boundary of the map. In contrast, the grid method allows for easy area calculation. PAGE 21 11 Once the shadow area has been determined the grid points designated as shadow are simply summed together. The technique used to determine the shadow areas is borrowed from the line-of-sight method discussed earlier. A robot is placed at a specified grid point and the remaining grid points are checked to see if line-of-sight exists. If line-of-sight does not exist the grid point is in a shadow region. Once again, a matrix is developed that contains all of the shadow points for each robot. The overall shadow area can be determined by combining the data for each robot into a single matrix. This is done using the Boolean logic operator AND on the matrices. This results in a single matrix that contains the shadow area information for a specific map and robot configuration. This method has been applied to a two-robot system in a 2020 grid (see figure 2.7). More results are presented in Chapter 5. Figure 2.7: Resulting shadow areas for a simple two robot system (2020 grid) This method was applied to a single robot on a 5050 grid in order to visualize where the maximum shadow areas occur. The robot was placed at every point in the matrix and PAGE 22 12 the corresponding total shadow areas were calculated at each point. The shadow areas were saved to a data file and later analyzed using MATLAB. Threedimensional plots were created (see figure 2.8) that contain the x and y locations of the robot and the corresponding total shadow area. These plots are used to visualize where the maximum and minimum shadow areas occur. Points occupied by an obstacle have a maximum shadow area, which assumes the entire map is a shadow region. Figure 2.8: A plot of the shadow areas for a single robot placed at every point on the map (except obstacle locations) Although this method provides a reasonable estimate of the shadow areas, it takes approximately seven minutes to determine a solution for a single robot. Optimization of this method is imperative once multiple robots are introduced. Line-of-Sight and Shadow Area Method Revisited After experimenting with the line-of-sight method mentioned earlier, it was decided that this method proved to be entirely too slow for this application. Due to the nature in which the line-of-sight function is used, the speed to determine a solution is of utmost PAGE 23 13 importance especially when various robots are considered. The line-of-sight method and thus, the shadow area method had to be revisited for further optimization. Line Segment Intersection Method A method was devised that accounts for the line segments that comprise the obstacles contained within the map. Therefore, a file containing all of the obstacle line segments was created. Using the obstacle line segments, the current robot position, and another arbitrary point or robot position it could be determined if there was an unobstructed path between the robot and the point in question. At this point, it was necessary to write a function that could determine if two lines intersect. Further research revealed a function written by Mukesh Prasad [1] that determines if two line segments intersect. A total of four (x,y) pairs are passed into the lines_intersect function. The first two pairs (x 1 y 1 x 2 y 2 ) represent the first line segment and the second two pairs represent the second line segment (x 3 y 3 x 4 y 4 ). The following line equation is used in the function: (2.1) 0111 cybxa The function proceeds to calculate the coefficients of the line equation, a 1 b 1 and c 1 121yya 211xxb 21121yxyxc (2.2) (2.3) (2.4) The function then performs a calculation that determines if the endpoints of the second line segment, (x 3 ,y 3 ) and (x 4 ,y 4 ), lie on the same side of the first line segment. If this is true, the line segments do not intersect. If this is false, a calculation is performed which determines if the endpoints of the first line segment, (x 1 ,y 1 ) and (x 2 ,y 2 ), lie on the same PAGE 24 14 side of the second line segment. If this is true, the line segments do not intersect and if this is false, the line segments do intersect. This is achieved with a simple sign check. The x and y values of point three (x 3 ,y 3 ) are placed into the line equation (eqn. 2.1) joining points one and two. The same is done for the fourth point. The equations below are used: (2.5) (2.6) 313131rcybxa 414141rcybxa For example, if the signs of r 3 and r 4 are the same then the two line segments in question do not intersect. This means that point three and point four lie on the same side of the first line segment. The original function returns the actual point of intersection. Modifications were made to the function to return a value of if the segments do intersect and a if they do not intersect. Figure 2.9: Illustration of the lines_intersect method A file contains a list of all line segments that make up each obstacle in the map. robot 1 (xr1, yr1) robot 2 (xr2, yr2) intersection x1, y1 x2, y2 x3, y3 x4, y4 obstacle line segment Obstacle Line Segment List x1, y1, x2, y2 x2, y2, x4, y4 x4, y4, x3, y3 x3, y3, x1, y1 . . xn-1, yn-1, xn, yn Line-of-Sight Determination For this particular problem the line-of-sight criteria is defined as a single robot being able to see at least one other robot. Line-of-sight among a pair of robots can be determined using the lines_intersect function explained previously. Assuming that the PAGE 25 15 positions for two robots are known, it can be determined if the path between the two robots is obstructed. This is accomplished by checking for intersection between the robot path and all obstacle line segments (see figure 2.9). Shadow Area Calculation The shadow area is calculated by calling the lines_intersect function to check for possible intersection between the robot path and all obstacle line segments. The shadow area function checks a single robot and an arbitrary point for possible intersection with the obstacle line segments. If intersection exists, a matrix containing the combined shadow area is set to at that arbitrary point. This is done for all robots and the combined shadow area is calculated simply by adding all of the cells set to in the shadow area matrix. The final algorithm proceeds to place the robots at grid points in the map and then calculate the corresponding shadow area. However, a problem arises when a grid point that lies within an obstacle is chosen. If a grid point contained within an obstacle is selected, the algorithm will return the maximum shadow area for that particular robot position, i.e. the total number of grid points for that particular map. Preliminary results These methods have been applied to the single robot case in which a robot is placed at a point and the shadow area is calculated for that particular position. After implementing the lines_intersect function for the single robot case all possible shadow areas are calculated for a 5050 grid in approximately 18 seconds. This is a vast improvement from the previous method, which took seven minutes. An exhaustive search technique was applied to the two-robot case. Every possible two-robot configuration was checked for the line-of-sight criteria and the corresponding PAGE 26 16 combined shadow area was calculated, again for a 5050 grid. This entire process took approximately 11 hours to complete. From this preliminary experiment it can be learned that the exhaustive search technique is not ideal for this type of problem. The next chapter will discuss how a genetic algorithm search approach can be used to significantly decrease the time required to obtain an optimal placement for multiple communication repeater robots to minimize the resulting shadow area. PAGE 27 CHAPTER 3 AN OVERVIEW OF OPTIMIZATION TECHNIQUES This goal of this chapter is to discuss different types of optimization techniques and to provide examples and applications of the techniques. A general overview of these techniques provides insight into the nature of this particular problem and the thought process involved to arrive at the final solution. This chapter is by no means inclusive of all optimization techniques but provides a general discussion of some of the techniques used in industry and academia. Background Optimization techniques are used throughout industry and applications include designing aircraft wings, economic analyses, airline scheduling, and internet search engines to name a few. Much of the optimization techniques in use today can trace their origins back to World War II. During this time any technique that increased the efficiency of the war effort was extremely important especially when faced with a limited number of people, machines, and supplies [2]. Due to this need, large-scale optimization techniques were developed to deal with the massive logistical problems raised when having to organize millions of troops and their associated gear and weaponry. During this time all calculations were done manually. With the invention of the digital computer, the speed at which calculations are performed and the amount of calculations possible increased dramatically. The digital computer revolutionized the field of practical optimization. 17 PAGE 28 18 Golden Section Method The golden section method can be used for estimating the maximum, minimum, or zero of a one-variable function. The function is assumed to uni-modal, but does not necessarily have to have continuous derivatives. In contrast to polynomial curve fitting techniques, the rate of convergence for the golden section method can be determined. This method is reliable for poorly conditioned problems but a well-conditioned problem will not converge any more rapidly. The golden section recurs in nature as an aesthetic ratio and throughout history as a number to which mysterious properties were attributed [11]. This ratio is the ratio of the base to the height of the Great Pyramid. Leonardo da Vinci added to the popularity with his studies on proportions of the human body. He found that this ratio was the distance from the navel to the ground divided by the distance from the top of the head to the navel of the optimum human body (see figure 3.1). Figure 3.1: BC/AB = Golden Section Ratio C B A PAGE 29 19 A function, F, is a function of the independent variable x. The value of x that will minimize F is to be determined. There are lower and upper bounds that bracket the minimum, X L and X U The function F has been evaluated at X L and X U and therefore the corresponding values of F L and F U are known. Figure 3.2: Illustration of the Golden Section Method Y U YL Y1 Y 3 Y2 XL X1 X2 X 3 X U The golden section method proceeds by choosing two intermediate points between X L and X U (see figure 3.2). As stated earlier, the function is assumed to be uni-modal, therefore X 1 or X 2 will form a new bound on the minimum. Because F 1 is greater than F 2 it forms a new lower bound, which produces a new set of bounds X 1 and X U X 1 is the new lower bound and a new point X 3 is chosen and evaluated for F 3 When comparing F 2 PAGE 30 20 and F 3 F 3 is greater and X 3 replaces X U as the upper bound. This process continues iteratively until the bounds are narrowed to a desired tolerance. For this particular method the golden section is used as a sequence for dividing the interval of the interior points to find the minimum value of the function, F, with as few function evaluations as possible. The golden section ratio is .38197 or 38%. This iterative procedure can be applied once a convergence criterion has been determined; this criterion will indicate when the process has converged to an acceptable solution. An initial interval of uncertainty has been defined, as X U -X L and it may be desired to reduce the interval by a fraction, of the initial interval or by a magnitude x. is referred to as a local tolerance and x as an absolute tolerance because it is independent of the initial interval. The relative tolerance can be defined as follows: LUXXx (3.1) This tolerance, can be converted to a maximum number of function evaluations in addition to the three required to evaluate F L F 1 and F U This can be done because the interval is reduced by the golden ratio, (38%), for each function evaluation. Therefore, for a specified tolerance, : (3.2) )3()1(N where N is the total number of evaluations. Solving the equation for N yields: (3.3) 3ln*078.23)1ln(ln N Choosing the value of is left to the programmer. For example, if it is desired to reduce the interval to 2% of the initial interval (=0.02) then N = 8.13+3 = 11.1312 function PAGE 31 21 evaluations. N can now be used as a convergence criterion. The iteration process is terminated when a total of N function evaluations have been performed. Note that N may take on fractional values and should be rounded up to the next higher integer. Although the golden section algorithm has been developed to determine the minimum of a one-variable function, the maximum of a function can be determined simply by minimizing the negative of the function. Gradient Techniques The rate of convergence of an optimization technique for a particular problem is dependent upon the initial parameters selected. If poor initial parameters are chosen, the optimization technique converges very slowly and is rendered useless. Depending on the technique chosen the initial parameters will dictate the speed at which a solution is determined as well as the validity of the final solution. A combination of optimization techniques may be applied initially. A slow algorithm may be tried and once approaching the minimum, switch to a technique that is much faster. Initially, a decision is made as to which direction to proceed. Then, a decision is made on how far to proceed in that direction. The latter, is determined by a set of rules and steepest descent is an example of this. Steepest Descent For any optimization procedure an initial guess x must be made for the parameter value. This guess can then be modified to x+x in order to reduce an error function, E(x). Here x is a vector that contains the n design parameters and the objective is to find the values of these parameters that minimizes the objective function F(x). The steepest descent technique chooses x so as to be traveling in a downhill direction (i.e. direction PAGE 32 22 which reduces the error function), approaching a minimum. Due to the fact that x is a vector it is described by two quantities: a magnitude and a direction. In order to choose the direction of x the dot product is applied. Definition of the dot product: a = (a 1 a 2 ,., a n ) b = (b 1 b 2 ,.,b n ) (3.4) a b = abcos (3.5) Where aand b is the magnitude of a and b, respectively, and is the angle between the two vectors. The dot product may be applied to the following relation: E(x+x) E(x) + E T x (3.6) The last term in equation 3.6 may be written as: E T x = (3.7) nnxxExxExxE ....2211 This is the dot product of the gradient E and the parameter change x. Therefore, a unit vector x will produce a maximum change if it points in the direction of the gradient and a minimum (negative change) if it points in the negative direction of the gradient. The steepest descent method uses this information by choosing the x to point in the negative gradient direction. The steepest descent technique proceeds as follows: 1. An initial set of parameters x is chosen, which results in an error E(x). 2. The gradient E is calculated at point x. The parameter direction changes are chosen to be in the direction of the negative gradient: x = E ( is a positive constant) (3.8) 3. This process is iterated until the desired minimum is reached. In an optimization problem it is usually desired to find a global minimum and avoid getting trapped in a local minimum. Failing to find the global minimum is not just a PAGE 33 23 difficulty associated with steepest descent; any optimization technique can be plagued by this problem [4]. Monte Carlo Integer Programming Exhaustive search methods for solving optimization problems will produce the optimal solution, however, as the search space increases it is doubtful that the solution will be determined in a reasonable amount of time. A more efficient method might require checking only a sample of possible solutions and then selecting the best solution out of the sample population. Therefore, random samples of feasible solutions are chosen and the corresponding (maximum or minimum) best solution from the random sample is determined. This method is known as Monte Carlo integer programming. There is some concern regarding the goodness of the answer obtained using this method mainly attributed to the random nature in which the samples are selected [3]. However, based on the statistics of the objective function, the random samples follow the probability distribution of the possible solutions for the integer-programming problem. Suppose the following function is to be maximized: (3.9) 5432125242322212336510xxxxxxxxxxP99ix where 0 (i=1) There are five variables in the above equation with values ranging from 0 to 99. This means there are a total of 100 5 possible points to check (10,000,000,000). Although computers are becoming faster, some computers may be burdened by this many calculations. The Monte Carlo technique will check a random sample of the 100 5 points for a feasible solution. For example, a random sample of one million points is evaluated and the point with the maximum value will be deemed the solution to the problem. PAGE 34 24 For the line-of-sight communications problem, the evaluation of the objective function is a time consuming process. For example, if n communicator repeater robots are to be positioned, there are 2n design variables, i.e. the x and y coordinates for each of the repeater vehicles. Evaluating the objective function for each possible set of robot positions requires calculating the total shadow area for this particular configuration, which is a lengthy process. Since for this application the partial derivatives of the objective function with respect to the design variables cannot be determined analytically, many optimization approaches such as the steepest descent method must be ruled out. For practical purposes, a random search algorithm must be implemented such as a random search direction method, the Monte Carlo search method, or a genetic algorithm approach method. This latter method was used in this problem and the next chapter will describe the genetic algorithm approach. This randomized approach will produce a near optimal solution. Although the optimal solution is not necessarily obtained, the speed at which a solution is determined is greatly reduced. PAGE 35 CHAPTER 4 GENETIC ALGORITMS Genetic algorithms are search algorithms based on the mechanics of natural selection and genetics. They efficiently use previous information to determine new search points with improved performance. John Holland and his colleagues developed this technique at the University of Michigan in 1975. The theme of much of the genetic algorithm research has been robustness and the balance between efficiency and the strength necessary for survival in a variety of environments. In sophisticated artificial systems, features common in biological systems such as self-repair, reproduction, and self-guidance barely exist. The following quote by John Holland captures the plight of many in the field of computer and design optimization: Living organisms are consummate problem solvers. They exhibit a versatility that puts the best computer programs to shame. This observation is especially galling for computer scientists, who may spend months or years of intellectual effort on an algorithm, whereas organisms who come by their abilities through the apparently undirected mechanism of evolution and natural selection. [7, p. 1] Traditional Methods versus Genetic Algorithms Calculus-based methods have been studied extensively and can be divided into two main classes: indirect and direct. The indirect methods seek local extrema by solving a set of (usually) non-linear equations resulting from setting the derivative or gradient of the objective function equal to zero. This method is extremely useful for a single-peak function as shown in figure 4.1. 25 PAGE 36 26 Figure 4.1: Single-peak function Direct methods seek local optima by moving in a direction related to the local gradient. This is similar to the method of steepest-descent discussed in Chapter 3. Both methods are local in scope, that is, the optimum is the best in a neighborhood of the current point. In terms of the direct search methods the multiple peak function shown in figure 4.2 proves to be a bit of a challenge. In this case it would be difficult to determine which peak to climb and once an alleged solution is found it is not known whether it is a local or a global optimum. In addition, search and optimization problems can be multi-modal, noisy search spaces that can be rife with discontinuities. The calculus-based methods are practical for certain types of problems. PAGE 37 27 Figure 4.2: Double-peak function Genetic algorithms require that the parameter set of the problem be coded as a finite length string. In addition, an objective function is necessary to measure how fit a current solution is compared to the rest of a population. The search is guided using probability and random choice. As the generations pass, strings associated with improved performance will predominate and as the mating process progresses strings are combined in new ways generating more sophisticated solutions [6]. Simple Genetic Algorithm A simple genetic algorithm involves complex copying of strings and swapping of partial strings. An initial population is chosen, usually at random. It is often necessary to define a set of simple operations that take this initial population and generate successive populations that improve over time. PAGE 38 28 Reproduction Reproduction is the first step of the genetic algorithm. During this process individual strings are copied according to their objective function values, or fitness values. Copying strings according to this measure means that strings with higher fitness values have a greater probability of propagating through the next generation. This is an artificial version of natural selection. In terms of an algorithm, reproduction may be implemented in several ways. Goldberg creates a biased roulette wheel where each current string in the population has a slot proportional to its fitness [6]. An illustration of this idea is shown in figure 4.3. String # String Fitness % of Total 1 11011 385 45.9 2 10001 141 16.8 3 00110 62 7.4 4 10101 251 29.9 Total 839 100 4 1 3 2 Figure 4.3: Sample string types and biased roulette wheel A simple spin of the weighted roulette wheel yields the reproduction candidate, which is solely based on fitness values and the overall probabilities. Using this method, more highly fit strings have a greater number of offspring in the succeeding generation. Once a string has been selected for reproduction an exact replica of the string is created and it is then entered into the mating pool, resulting in a tentative new population. Crossover After reproduction, simple crossover proceeds in two steps. Members of the new population are mated at random. Next, each pair of strings undergoes crossover: a position i along the string is selected at random between 1 and then string length (L) PAGE 39 29 minus one [1, L-1]. Swapping all characters between i+1 and L forms two new strings. For example: S 1 = 1 1 0 | 1 1 Note: The | character indicates the crossover site. S 2 = 1 0 0 | 0 1 i is chosen at random to be 3. After crossover two new strings are formed which are part of the new generation. The new strings are as follows: S 1 = 1 1 0 0 1 S 2 = 1 0 0 1 1 Mutation Mutation is necessary because, even though reproduction and crossover effectively search and recombine, there are occasions when there can be a loss of genetic material. In addition, mutation adds extra variability to the existing population. Mutation alone does not generally advance the search for a solution, but it does provide insurance against the development of a uniform population incapable of further evolution [7, p. 3]. In the simple genetic algorithm, mutation usually has a very small probability and simply corresponds to a random alteration of the value of a string position. Because mutation rates are low, it can be considered a secondary mechanism of genetic algorithm adaptation [6]. Genetic Algorithm Implementation A significant portion of this research was devoted to developing a method to measure how well the current robot configuration covered the region to minimize the shadow area while making sure that every communications repeater robot was within line-of-sight of another. In order to gauge the results obtained from the genetic algorithm it was necessary to develop an efficient and robust objective function. In particular, the PAGE 40 30 combined shadow area area that is not visible to any of the robots was measured for a robot configuration using this objective function. The objective function not only takes into account the shadow area of each robot but it also has to incorporate the line-of-sight criteria. It was decided that line-of-sight communication was maintained as long as there was an unobstructed path between the robot in question and at least one other robot. After a solid objective function was developed, a string representation of the robot positions was developed. It can be noted that the map resolution correlates directly to the number of bits used in the binary string. For example, for the 6464 map, there are a total of 4096 data points. Therefore, in order to represent all of the corresponding x and y robot positions using a binary string there had to be a total of 12 bits (2 12 = 4096). The most significant six bits represent the robots x position and least significant six bits represent the robots y position (see figure 4.4). The position of each repeater robot is represented using the binary string representation. X 1 X 2 X 3 X 4 X 5 X 6 Y 1 Y 2 Y 3 Y 4 Y 5 Y 6 Figure 4.4: Binary String Representation of Robots (x,y) Position A series of maps were generated with greater resolution in order to demonstrate the expandability of the method and the versatility of the genetic algorithm. These maps had a resolution of 256256, which corresponds to 65,536 data points a considerably larger search space than the aforementioned. Due to the increased number of data points, the number of bits in the string was increased to 16 bits (2 16 = 65,536). A similar binary string as that in figure 4.4 was used with the addition of two more bits to both the x and y component of the string. The software for this work used the GAlib genetic algorithm package, written by Matthew Wall at the Massachusetts Institute of Technology [12]. This library required an PAGE 41 31 objective function and a solution that could be represented in a single data structure. The library is broken into two primary classes: a genome and a genetic algorithm. Each genome represents a single solution to the problem. The actual genetic algorithm defines how the evolution should take place. The genetic algorithm uses the objective function to determine how fit each genome is for survival. Genome operators, which are built into the genome, and selection strategies, which are built into the genetic algorithm, are used to generate new individuals. This library incorporates several different types of genetic algorithms such as: simple, steady state, and incremental. The simple genetic algorithm proceeds to create an entirely new population of individuals every generation and automatically advances the best individual to the next generation. The steady state genetic algorithm uses an overlapping population. That is, the user is allowed to specify how much of the population may be replaced in the next generation. When using an incremental genetic algorithm, the next generation consists of only one or two children. In addition, methods are defined for how the new generation should be integrated into the overall population. For purposes of this research, the simple genetic algorithm was chosen because previous work could easily be adapted to the format required by the library. The diagram in figure 4.5 illustrates the overall program flow in terms of the genetic algorithm. The next chapter will present the results of applying this algorithm to the problem at hand. Several test cases will be examined and discussed. PAGE 42 32 Random InitialPopulationSelection EvalulateFitness Reproduction(Based onFitness) Crossover Randomlyselectmates frommatingpool Randomlychoosecrossoversite andcreate newindividual Mutation Select individual,flip bit END(New Population) NOYESSets of robot configurations arerandomly generatedCalculates the combined shadowarea for each robot configurationin the population using theobjective functionA new mating pool is created basedon the fitness of each robotconfiguration (the more fit propagatethrough the generations) Done foreachgeneration Figure 4.5: Genetic Algorithm Flow Diagram PAGE 43 CHAPTER 5 EXPERIMENTS AND RESULTS This chapter describes the experiments that were run to test the feasibility of the multiple vehicle positioning simulation program. A series of maps were created at two different resolutions. There were a total of twelve maps, half of which were of 6464 resolution and the other half were of 256256 resolution. For both types of maps the algorithm was run for a two, three, four, and five communications repeater robot configuration. The results were saved to a file and displayed visually. This chapter has a section for each of the different resolutions and subsections within containing results from the individual maps. In addition, there is a section that compares the genetic algorithm technique to an exhaustive search technique and presents the corresponding results. All maps were generated using a map program that was written in C. All measurements are in units of pixels and can be adjusted to fit the needs of the user.. Graphical User Interface The graphical user interface (GUI) was created using the Visual C++ programming package. It should be noted that the GUI program only displays the 6464 resolution maps. It was necessary to create a GUI that was visually appealing as well as user-friendly. Some other features of the program are that the user is able to choose from six different maps, enter the desired number of robots, view the corresponding robot positions, and visualize the resulting shadow area. The total processing time is displayed as well. A sample of the GUI is shown in figure 5.1. 33 PAGE 44 34 Figure 5.1: Sample GUI written in VC++ Robot Position Obstacle Shadow Area 6464 Resolution Maps Map One The first map that was analyzed was somewhat simplistic and was initially used for testing the algorithm. This map was created manually, simply by creating a file that contained all of the points that make up each obstacle. This file is then read into the optimization program and positioning of the desired number of robots proceeds using this map. For all maps of 6464 resolution the convergence criterion was specified to be the best solution after 100 generations. PAGE 45 35 The genetic algorithm is constantly trying to improve the results obtained from the objective function by combining the most fit offspring of each generation. For this map, as more robots are added to the solution, the better the overall coverage of the map. Figure 5.2a: Map 1, 2 Robots, Shadow Area = 82 Figure 5.2b: Map 1, 3 Robots, Shadow Area = 11 Figure 5.2c: Map 1, 4 Robots, Shadow Area = 7 Figure 5.2d: Map 1, 5 Robots, Shadow Area = 1 Figure 5.2: Results for Map1 PAGE 46 36 The results from map one are relatively encouraging. As more robots are added to the solution, there is a decrease in the shadow area, which implies that the coverage of the map is improved. Figures 5.2a-d depicts the final results for that particular map with two through five robots. A plot of the shadow areas versus the processing time is shown in figure 5.3. As more robots are added to the problem, the processing time increases and the shadow area decreases. A solution is obtained for five robots in a time of 13 seconds. As the complexity of the map increases the processing time increases slightly, by a matter of seconds. The algorithm converges when it cycles through all of the 100 generations. 6080100120140bined Shadow Area 2 Robots 3 Robots 4 Robots 5 Robots 020400246810121416Time (sec)Com Figure 5.3: Map 1 convergence rates for 2-5 robots after 100 generations Map Two This map is slightly more complicated than map one, in that it has more obstacles. This map was generated using a simple program that reads in a file containing PAGE 47 37 the number of obstacles, the coordinates for the center points and the corresponding radius of each obstacle. This method limited the shape of the obstacles to being square yet overlapping several obstacles could create other shapes. The results for map two are shown in figure 5.4. Figure 5.4a: Map 2, 2 Robots, Shadow Area = 24 Figure 5.4b: Map 2, 3 Robots, Shadow Area = 9 Figure 5.4c: Map 2, 4 Robots, Shadow Area = 0 Figure 5.4d: Map 2, 5 Robots, Shadow Area =0 Figure 5.4: Results for Map 2 PAGE 48 38 The four-robot configuration seems to be the optimal situation with a shadow area of zero. The five-robot configuration results in a shadow area of zero also, which is an intuitive result. As more robots are added to the solution, the better the coverage of the search space. The algorithm converged after cycling through 100 generations of the genetic algorithm. Plots of the shadow areas versus time are shown in figure 5.5. 68101214 5 Robots 020406080100120140160180200024Time (sec)Combined Shadow Area 2 Robots 3 Robots 4 Robots Figure 5.5: Map 2 convergence rates for 2-5 robots after 100 generations The five-robot configuration converged in 15 seconds and the solution of four robots converged in 10 seconds. A recurring theme in this work is that the genetic algorithm will provide near-perfect results. That is, the optimal solution will not always be obtained but something close to optimal will be obtained. The final solution will be dependent on how long the algorithm runs for and ultimately the number of generations that are iterated through to get a final solution. PAGE 49 39 Map Three Map three is a simple map with square obstacles. Again, this map and the rest of the maps referenced were generated using the map-making program. The results are shown in figure 5.6. Figure 5.6a: Map 3, 2 Robots, Shadow Area = 78 Figure 5.6b: Map 3, 3 Robots, Shadow Area = 25 Figure 5.6c: Map 3, 4 Robots, Shadow Area = 3 Figure 5.6: Results for Map 3 Figure 5.6d: Map 3, 5 Robots, Shadow Area = 26 PAGE 50 40 The results obtained from this map are interesting because the best solution is found to be the four-robot configuration. With a total shadow area of three grid points this solution outperforms the five-robot configuration. By visual inspection, the four-robot configuration appears to cover more of the map area, which is confirmed by the algorithm. Plots of the shadow areas versus time are shown in figure 5.7. The four-robot configuration took a total of 11 second to converge and the five-robot configuration took a total of 15 second to converge. Once again, the algorithm terminates after it has cycled through 100 generations in the genetic algorithm. 400450500 05010015020025030035002468101214Time (sec)Combined Shadow Area 2 Robots 3 Robots 4 Robots 5 Robots Figure 5.7: Map 3 convergence rates for 2-5 robots after 100 generations PAGE 51 41 Map Four This map also contains square obstacles; the main difference being that they are all the same size and the arrangement is not randomized as in the previous example. This search space is slightly more complex due to the number of obstacles present and the circular arrangement throughout the space. The results are shown in figure 5.8. Figure 5.8a: Map 4, 2 Robots, Shadow Area = 220 Figure 5.8b: Map 4, 3 Robots, Shadow Area = 108 Figure 5.8c: Map 4, 4 Robots, Shadow Area = 27 Figure 5.8d: Map 4, 5 Robots, Shadow Area = 32 Figure 5.8: Results for Map 4 PAGE 52 42 By visual inspection of the two-robot case, this arrangement of obstacles within the search space limits the robot positions such that they still fulfill the line-of-sight criteria. The algorithm successfully positions the robots for all four scenarios. It is interesting to note that the four-robot configuration has a resulting shadow area of 27 and the addition of another robot does not improve this result. Therefore, if the objective were to minimize the shadow area and minimize the number of robots used, then the solution to this problem would be the four-robot configuration. The convergence rates for each scenario are shown in figure 5.9. 250300350400450500 Shadow Area 05010015020005101520Time (sec)Combined 2 Robots 3 Robots 4 Robots 5 Robots Figure 5.9: Map 4 convergence rates for 2-5 robots after 100 generations Map Five This map contains different sized square obstacles that are randomly placed throughout the search space. For this particular space the five-robot configuration has the lowest shadow area. This is an intuitive result and is primarily due to the placement of a PAGE 53 43 robot in the right-hand corner of the map. Doing so eliminates any unseen area along the right-hand side of the map (see figure 5.10). Figure 5.10a: Map 5, 2 Robots, Shadow Area = 334 Figure 5.10b: Map 5, 3 Robots, Shadow Area = 145 Figure 5.10c: Map 5, 4 Robots, Shadow Area = 38 Figure 5.10d: Map 5, 5 Robots, Shadow Area = 0 Figure 5.10: Results for Map 5 PAGE 54 44 The five-robot configuration provides the optimal solution for this search space. It is intuitive to think that addition of more robots to the solution should maximize the coverage area and for this situation this does occur. The addition of more robots results in a gradual decrease in the shadow areas and eventually a shadow area of zero is achieved. The convergence rates are shown in figure 5.11. 200300400500600700Combined Shadow Area 0100024681012Time (sec.) 2 Robots 3 Robots 4 Robots 5 Robots Figure 5.11: Map 5 convergence rates for 2-5 robots after 100 generations Map Six This is one of the more complex maps that were processed. There are quite a few obstacles of varying sizes and there is an obstacle created from two square obstacles. The algorithm does not appear to have any problems with this shape. This map was designed to push the limits of the algorithm, specifically the line-of-sight criteria. With this many PAGE 55 45 obstacles present the algorithm still positions the robots such that the line-of-sight criteria is fulfilled. The results are presented in figure 5.12. Figure 5.12a: Map 6, 2 Robots, Shadow Area = 549 Figure 5.12b: Map 6, 3 Robots, Shadow Area = 396 Figure 5.12c: Map 6, 4 Robots, Shadow Area = 120 Figure 5.12d: Map 6, 5 Robots, Shadow Area = 3 Figure 5.12: Results for Map 6 PAGE 56 46 The rates of convergence are shown in figure 5.13. Although this is a somewhat complicated map the time in which a solution is calculated does not suffer. For the five-robot case a solution is found in 18 seconds. 1002003004005006007008009001000Combined Shadow Area 2 Robots 3 Robots 4 Robots 5 Robots 0024681012141618Time (sec) Figure 5.13: Map 6 convergence rates for 2-5 robots after 100 generations 256256 Resolution Maps The higher resolution maps were created and tested in order to demonstrate that the algorithm is applicable to larger search spaces. This demonstrates that this algorithm could be used on an actual aerial image of an area where corresponding robotic vehicles would be positioned. For this particular application the algorithms were run on a Linux platform. This was done in the interest of time. Due to the increased search space and the number of maps that are analyzed it was easier and faster to create a script file that would cycle through PAGE 57 47 each map and save the corresponding results to a file. A GUI was not created, however the corresponding results and data were saved in a ppm (portable pixmap) file format that could be opened and viewed at a later time. This file format is relatively easy to encode, as it is the most simplistic format for color images (see figure 5.14). P6 256 256 255 0 255 63 9 85 2A Figure 5.14: Sample ppm file and header information (first 3 lines) The first line indicates the ppm type, which can either be a binary or ASCII format. The second line contains the height and width of the image. For these images the height and width are the same. The third line contains the maximum RGB values contained within the image. The rest of the file contains all of the RGB values for each pixel in the image. The results for the higher resolution maps will be presented in the next six sections Map One The first map or search space that was tested consisted of a single obstacle placed in the center of the space. This is an extremely simplistic search space and yields interesting results as more robots are added to the solution. It would be difficult, if not impossible, to eliminate the shadow area for the two-robot configuration while simultaneously fulfilling the line-of-sight criteria. The addition of a third robot provides an optimal solution for this map. Addition of a fourth and fifth robot also result in optimal solutions, each having shadow areas of zero. The graphical results are provided in figure 5.15. PAGE 58 48 Figure 5.15d: Map 1, 5 Robots, Shadow Area = 0 Figure 5.15c: Map 1, 4 Robots, Shadow Area = 0 Figure 5.15b: Map 1, 3 Robots, Shadow Area = 0 Figure 5.15a: Map 1, 2 Robots, Shadow Area = 533 Figure 5.15: Results for Map 1 These results are intuitive and provide insight into the genetic algorithm technique that is being used to search through the space. Plots of the rates of convergence for each configuration are shown in figure 5.16. The only data displayed on the plot is that for the two-robot configuration. The three-, four-, and five-robot configurations converge to the PAGE 59 49 optimal solution (shadow area = 0) in less than one second; therefore the corresponding data is zero. The total runtime for the two-robot case has increased to approximately two minutes and this is due to the increase in the search space. 150200250300me (sec) 2 Robots 3 Robots 4 Robots 5 Robots 0100200300400500600700800050100TiCombined Shadow Area Figure 5.16: Map 1 convergence rates for 2-5 robots after 200 generations Map Two This map contains three obstacles that are located in the top half of the search space. Previous results have indicated that the number of obstacles and the obstacle locations affect how well the algorithm performs especially in the twoand three-robot cases. In these cases less area can be covered resulting in greater shadow areas and fewer options regarding final robot positions. PAGE 60 50 The results presented in figure 5.17 show that the addition of a third robot is detrimental to the resulting shadow area. Addition of a fourth and fifth robot drastically improves the final solution and an optimal solution is obtained for the five-robot case. Figure 5.17b: Map 2, 3 Robots, Shadow Area = 611 Figure 5.17a: Map 2, 2 Robots, Shadow Area = 198 Figure 5.17c: Map 2, 4 Robots, Shadow Area = 16 Figure 5.17d: Map 2, 5 Robots, Shadow Area = 0 Figure 5.17: Results for Map 2 The shadow area for the four-robot configuration is 16 pixels, but this is barely visible on an image of this scale. As stated earlier, the increase in the size of the search space PAGE 61 51 affects the time in which a solution is obtained. Figure 5.18 shows the corresponding rates of convergence for the four situations. The three-robot takes approximately six minutes to arrive at a solution and while the five-robot configuration takes approximately four minutes to converge to the optimal solution of zero shadow area. 400500600700 (sec) 2 Robots 3 Robots 4 Robots 5 Robots 0200400600800100012000100200300TimeCombined Shadow Area Figure 5.18: Map 2 rates of convergence for 2-5 robots after 200 generations Map Three This map incorporates four obstacles into the search space. The results shown in figure 5.19 indicate that the addition of a fourth robot increases the shadow area considerably. This may be attributed to the random nature of the genetic algorithm. Addition of a fifth robot to the solution further improves the final results. Only a minimal amount of area is hidden from the five robots views. This algorithm is PAGE 62 52 interesting because it tries to maximize the area covered and maintain line-of-sight among the robots. Figure 5.19b: Map 3, 3 Robots, Shadow Area = 70 Figure 5.19a: Map 3, 2 Robots, Shadow Area = 944 Figure 5.19c: Map 3, 4 Robots, Shadow Area = 306 Figure 5.19d: Map 3, 5 Robots, Shadow Area = 25 Figure 5.19: Results for Map 3 The processing time for the two-robot configuration is approximately four and a half minutes and steadily increases as more robots are added to the solution. The processing PAGE 63 53 time for the five-robot configuration is approximately 11 minutes. A plot of the rates of convergence for this map is shown in figure 5.20. 05000100200300 2 Robots 3 Robots 4 Robots 5 Robots 400500600700e (sec) 100015002000250030003500TimCombined Shadow Area Figure 5.20: Map 3 rates of convergence for 2-5 robots after 200 generations Map Four Four larger obstacles are incorporated into this search space. Although this map is somewhat cluttered and a higher-resolution image the algorithm performs as expected. Once again, the obstacles have been randomly placed throughout the space using a custom program written in the C programming language. The two-robot case resulted in the greatest shadow area followed sequentially by the other three cases. Both the fourand five-robot configurations result in the optimal solution of a shadow area equal to zero. For the fourand five-robot cases the final robot PAGE 64 54 positions are optimal for maximizing map coverage while maintaining line-of-sight communications. The results are shown in figure 5.21. Figure 5.21a: Map 4, 3 Robots, Shadow Area = 364 Figure 5.21a: Map 4, 2 Robots, Shadow Area = 4749 Figure 5.21c: Map 4, 4 Robots, Shadow Area = 0 Figure 5.21d: Map 4, 5 Robots, Shadow Area = 0 Figure 5.21: Results for Map 4 PAGE 65 55 From the plots shown in figure 5.22 it is interesting to note that the four-robot case converged to a zero solution in approximately four minutes, while the five-robot case converged to a zero solution in approximately two minutes. Addition of a fifth robot decreased the time in which the algorithm converged to zero. This is an intuitive result because addition of another robot serves to maximize the coverage area therefore expediting the search for the optimal solution. 8 300400500600e (sec) 2 Robots 3 Robots 4 Robots 5 Robots 010002000300040005000600070000009000100000100200TimCombined Shadow Area Figure 5.22: Map 4 rates of convergence for 2-5 robots after 200 generations Map Five This map is composed of six obstacles; four of which are clustered together and the remaining two are spread farther apart. The results gradually improve as another robot is added to the solution. Although the five-robot case does not obtain a shadow area of zero, a drastic improvement is made when compared with the two-robot case. PAGE 66 56 Again the two-robot case resulted in the greatest shadow area followed sequentially by the three other cases. Increasing the number of generations and the size of the population would greatly affect the final results for all four cases. In addition this would increase the overall processing time. The results are shown in figure 5.23. Figure 5.23b: Map 5, 3 Robots, Shadow Area = 2022 Figure 5.23a: Map 5, 2 Robots, Shadow Area = 6576 Figure 5.23c: Map 5, 4 Robots, Shadow Area = 1072 Figure 5.23d: Map 5, 5 Robots, Shadow Area = 184 Figure 5.23: Results for Map 5 PAGE 67 57 This is one of the more complicated search spaces therefore there is an increase in the total processing time. The two-robot case takes approximately six minutes to obtain a solution and this time gradually increases as more robots are considered in the solution. Plots of the convergence rates are shown in figure 5.24. 0100020000100200300 2 Robots 3 Robots 4 Robots 5 Robots 400500600700800me (sec) 300040005000600070008000900010000TiCombined Shadow Area Figure 5.24: Map 5 rates of convergence for 2-5 robots after 200 generations Map Six This final map consisted of six obstacles randomly placed throughout the search space. The obstacles in this map are spread throughout the space and again, two to five robots will be positioned throughout the map. Two robots result in a considerable amount of hidden area. Addition of a third robot provides desirable results as the hidden regions decrease dramatically. The shadow area continues to decrease with the addition PAGE 68 58 of a fourth robot, however, addition of the fifth robot results in an increase in the shadow area. Although this is a complex map, the algorithm succeeds at finding reasonable solutions for each situation. The results are displayed in figure 5.25. Figure 5.25b: Map 6, 3 Robots, Shadow Area = 1320 Figure 5.25a: Map 6, 2 Robots, Shadow Area = 8348 Figure 5.25c: Map 6, 4 Robots, Shadow Area = 962 Figure 5.25d: Map 6, 5 Robots, Shadow Area = 1197 Figure 5.25: Results for Map 6 PAGE 69 59 This algorithm not only serves to determine the optimal robot placement but also inadvertently provides some insight as to the number of robots necessary to cover the search space most efficiently. The plots of the rates of convergence are shown in figure 5.26 and note that the four-robot case provides smallest shadow area in approximately 580 seconds or 9.6 minutes. 02000400060000100200Combi 2 Robots 3 Robots 4 Robots 5 Robots 800010000120001400016000180002000030ned Shadow Area 0400500600700Time (sec) Figure 5.26: Map 6 rates of convergence for 2-5 robots after 200 generations All of the examples shown in the previous sections provide a reasonable estimate of the visible as well as hidden area from the robots perspectives. These results are affected by the number of individuals used in the population and the number of generations incorporated into the genetic algorithm. Better results may be obtained by allowing the algorithm to run for a longer period of time. The final results proved to accomplish the overall objective of this work. The next section will compare the results PAGE 70 60 from an exhaustive search technique to the genetic algorithm technique described throughout this chapter. Exhaustive Search Technique versus Genetic Algorithm Technique The focus of this section is to present the results from two different techniques and observe the differences in the final solutions and the overall processing times. The exhaustive search technique calculates the shadow area for every possible two-robot configuration and keeps track of the current best solution. For the two-robot case, this method is computationally intensive and takes hours to arrive at a final solution. Therefore, the results compared will only be for the two-robot case. Three 6464 resolution maps will be compared and the results will be displayed graphically as in previous sections in addition to similar plots of the convergence rates for each technique. All of the maps have been presented in previous sections. The data in the convergence plots contain the current best solution for both techniques. Comparison #1 The first map is the most simplistic of the three maps that will be compared. Both methods arrive at a similar solution for the shadow area with slightly different robot positions. The main difference that should be noted is the overall processing time required to arrive at the solution. For this particular example, the exhaustive search technique takes approximately four hours to complete while the genetic algorithm technique finds a solution in seven seconds. The exhaustive search would have found multiple solutions that have a shadow area of 14, but the first one found was reported as the best solution. The results from the two methods are shown in figure 5.27. Data plotted are the best of each run and are not the entire data set. PAGE 71 61 Figure 5.27a: Exhaustive Search Results Robot 1 Position: (49, 20) Shadow Area: 14 Robot 2 Position: (3, 40) Total Time: 4.27 hours Figure 5.27b: Genetic Algorithm Results Shadow Area: 26 Robot 1 Position: (0, 58) Robot 2 Position: (45, 35) Total Time: 7 seconds Exhaustive Search Technique1101001000100000100020003000400050006000Time (sec)Minimum Shadow Area Genetic Algorithm Technique11010010001000001234567Time (sec)Minimum Shadow Area Figure 5.27c: Exhaustive search convergence rate Figure 5.27d: Genetic algorithm convergence rate Figure 5.27: Results for Comparison #1 PAGE 72 62 Comparison #2 This map contains more obstacles than the previous example. The increase in the number of obstacles increased the processing time for the exhaustive search technique. The increase in the number of obstacles increases the number of calculations that must be performed throughout the search space. The results are shown in figure 5.28. The genetic algorithm ran for 100 generations and then selects the best solution from each generation. After the algorithm has cycled through all 100 generations the final solution is reported to be the best of the final generation. Figure 5.28: Results for Comparison #2 Figure 5.28a: Exhaustive Search Results Shadow Area: 3 Robot 1 Position: (62, 5) Robot 2 Position: (12, 63) Total Time: 17.4 hours Figure 5.28b: Genetic Algorithm Results Shadow Area: 85 Robot 1 Position: (55, 49) Robot 2 Position: (9, 28) Total Time: 7 seconds There is a definite difference in the solution for the shadow areas. The genetic algorithm does not obtain the optimal solution, however it obtains a solution in far less time. It should also be noted that the size of the map for the exhaustive search technique PAGE 73 63 was increased from 5050 to 6464; this results in 1,596 extra data points that must be checked which accounts for the drastic increase in the total processing time. Initial tests were performed with a 5050 resolution search space and the space was later increased to a resolution of 6464 to accommodate the genetic algorithm library specifications. Plots of the convergence rates are shown in figure 5.28c-d. 110100010002000300040005000Time (sec) 11010001234567Time (sec) Genetic Algorithm Technique100010000Minimum Shadow Area Exhaustive Search Technique100010000Minimum Shadow Area Figure 5.29a: Exhaustive search convergence rate Figure 5.29b: Genetic algorithm convergence rate Figure 5.29: Convergence Rates for Comparison #2 Comparison #3 The final map is shown in figure 5.30. There is an increase in the processing time for the exhaustive search technique due to the increase in the number of obstacles as well as the size of the search space. It should be noted that the robot positions obtained from both techniques maintain line-of-sight very narrowly. This problem can be mitigated if the boundaries of the obstacles were expanded. PAGE 74 64 Very similar results are obtained for each of the techniques. The main difference being the time in which a solution was calculated. Figure 5.30a: Exhaustive Search Results Shadow Area: 147 Robot 1 Position: (9, 22) Robot 2 Position: (59, 61) Total Time: 13.7 hours Figure 5.30b: Genetic Algorithm Results Shadow Area: 284 Robot 1 Position: (33, 62) Robot 2 Position: (34, 1) Total Time: 6 seconds Exhaustive Search Method1101001000100000200040006000800010000120001400016000Time (sec)Minimum Shadow Area Genetic Algorithm Method1101001000100000123456Time (sec)Minimum Shadow Area Figure 5.30c: Exhaustive search convergence rate Figure 5.30d: Genetic algorithm convergence rate Figure 5.30: Results for Comparison #3 PAGE 75 65 This section presented the results obtained for two vastly different techniques. The exhaustive search technique was a starting point for this research. Initial experiments were conducted with various maps using the exhaustive search technique for the two-robot case. Collecting data using this technique was extremely laborious and time consuming. Addition of even a third robot to the problem would increase the processing time exponentially. Other techniques such as the golden section method, steepest descent technique, and Monte Carlo programming, were investigated and the genetic algorithm optimization technique was finally chosen due to the ease of implementation with the current algorithm. The following table summarizes the specifications of the computers that were used and the specifications that the genetic algorithm required. 6464 Maps 256256 Maps Computer Specifications: Pentium 3, 1GHz Processor 256 MB RAM Pentium 4, 2GHz Processor 512 MB RAM Genetic Algorithm: Population 10 20 Generations 100 200 Mutation Rate 2% 2% Table 5.1: Summary of computer specifications and genetic algorithm specifications for both types of maps PAGE 76 CHAPTER 6 SUMMARY AND CONCLUSION This research demonstrates that simulation robot positioning is essential when planning for multiple robotic entities. This simulation provides insight into where the communications repeater robots should be positioned throughout the search space so that communication is maintained and coverage is maximized. This program is a very useful tool when coordinating the actions of a multi-agent system. The genetic algorithm technique provided a method for obtaining a solution for several types of maps and multiple robots in a timely fashion. The genetic algorithm technique was compared with the exhaustive search technique. The results indicated that the exhaustive search technique provided the optimal solution for a two-robot configuration however, the time required to obtain a solution was on the order of several hours. In contrast, the genetic algorithm technique provided a sub-optimal solution for a two-robot configuration and the time required to obtain a solution was on the order of seconds. Although the genetic algorithm provides a solution in a timely manner, the global optimality of the solution is sacrificed. The research presented is strictly a two-dimensional evaluation but can be extended to a three-dimensional problem. The three-dimensional situation will account for elevation of the terrain in addition to obstacle locations. The current research could be extended to account for the x, y, and z components of the map and thus create a three-dimensional grid. The line-of-sight algorithm would have to be revised so that it 66 PAGE 77 67 accounts for how to determine if a path is obstructed between two grid points when dealing with three-dimensional contours. The method currently used may not be sufficient for the three-dimensional problem. In addition, this research could be extended to incorporate ground and aerial vehicles. The system would function as follows: 1. An aerial vehicle would navigate to a desired location or waypoint. 2. Once at the waypoint, a series of photographs would be taken with an onboard camera. 3. These photographs would be discretized, similar to the way the maps were as presented in this research. The landmarks, obstacles, and boundaries would be extracted from the images to create a map. 4. This map would be used and the algorithm would determine the positions for the ground robots and the corresponding combined shadow area. This is an example of a hybrid collaborative control system. Two specific types of robots are being controlled to achieve an overall task of maximizing the coverage of a search space while maintaining communications. This is a very simplified approach to this problem and there is a great deal of work involved before actual implementation of this type of system. Some problems are: automation of a small aerial vehicle that is able to navigate to waypoints, image processing that will extract obstacles from the photographs taken by the aerial vehicle, and having enough ground vehicles to accomplish this task. This research has provided some initial results for robot coordination and collaborative control. The results reinforce the validity of the method as well as the technique used for optimization of the solution. The speed at which a solution is obtained is also an attractive feature of this algorithm. The genetic algorithm technique for optimization PAGE 78 68 provided a solution for this type of global optimization problem. The final algorithm was easily applicable to larger search spaces consisting of different maps and a variable number of robots. This simulation is a starting point for future research and implementation on an actual system. This research has provided some initial results for robot coordination and collaborative control. The results reinforce the validity of the method as well as the technique used for optimization of the solution. The speed at which a solution is obtained is also an attractive feature of this algorithm. The genetic algorithm technique for optimization provided a solution for this type of global optimization problem. The final algorithm was easily applicable to larger search spaces consisting of different maps and a variable number of robots. This simulation is a starting point for future research and implementation of an actual system. PAGE 79 APPENDIX A SOURCE CODE FOR FINAL ALGORITHM This appendix contains the code written to implement a graphical user interface as well as all functions necessary to carry out all calculations. The implementation of the genetic algorithm library (GAlib) is also included. The appendix begins with the header files and then the function prototypes used throughout the body of the code. ////////////////////////////////////////////////////////////////////////////// // This program was adapted from Matthew Wall's example 1 using his // genetic algorithm library, GAlib. // // DESCRIPTION: The following program has modified ex1.c to extend to my // particular application. I am using the Simple Genetic // Algorithm and a 2D binary string genome. // In particular, I have modified the Objective function // so that it performs shadow area calculations for a given // multi-robot configuration and a specified number of robots. // The program outputs the final results to the terminal and // also creates a data file that logs GA data periodically. // (GAdata.txt) // A dialog window has been implemented which displays the // data to the user. // // DATE: Oct. 21, 2002 // PROGRAMMER: Erica Zawodny /////////////////////////////////////////////////////////////////////////////// /* robotDialog.cpp : Defines the entry point for the application.*/ #include "stdafx.h" 69 PAGE 80 70 #include #include "resource.h" #include #include #include #include // we're going to use the simple GA #include // and the 2D binary string genome //Erica's Stuff #define ROW 64 #define COLUMN 64 #define DONT_INTERSECT 0 #define DO_INTERSECT 1 #define COLLINEAR 2 #define RANGE 50 #define MAX_RAND 32767.0 //maximum random number /////////////////////////////////////////////////// // This macro is used to determine if 2 numbers // // have the same sign. // /////////////////////////////////////////////////// #define SAME_SIGNS(a, b) ((((long) (a) (long) (b)) >= 0) ? 1 : 0) ////////////////////////// // Function Prototypes // ////////////////////////// void drawObstacles(void) ; int shadows(int num, int robot[][2]) ; int LOS(int mat1[][COLUMN],int xs, int ys, int xe, int ye) ; int lines_intersect(unsigned int x1, unsigned int y1, unsigned int x2, unsigned int y2, unsigned int x3, unsigned int y3, unsigned int x4, unsigned int y4) ; void randomRobot(int robots, int robot_positions[][2]) ; int multiRobotLOS(int number,int robot_loc[][2],unsigned int line_segments,unsigned int *x3,unsigned int *y3,unsigned int *x4,unsigned int *y4) ; PAGE 81 71 void Statistics(GAGenome& g) ; float Objective(GAGenome &) ; // This is the declaration of our obj function. // The definition comes later in the file. int WINAPI WinMain(HINSTANCE hInstance, HINSTANCE hPrevInstance, LPSTR lpCmdLine, int nCmdShow) ; BOOL CALLBACK DlgProc(HWND hwnd, UINT Message, WPARAM wParam, LPARAM lParam) ; void DrawGrid(HDC hdc, HWND hwnd) ; void DrawMap(HDC hdc, HWND hwnd) ; void DrawRobots(int best_robots[][2], HDC hdc, HWND hwnd) ; void DrawShadows(HDC hdc, HWND hwnd) ; ////////////////////////// // Global Variables ////////////////////////// int obstacles_matrix[ROW][COLUMN] = {0}; //A matrix containing the obstacle locations int shadow_matrix[ROW][COLUMN] = {0}; int num_robots ; //User-specified number of robots int best_robots[20][2] ; //a global containing the best robots the GA found int best_shadow = 0 ; //a global var. containing the final combined shadow area int i,m,n ; int Solution_Found = 0 ; //A flag that is set when the GA has found a solution // FILE *fp1, *fp2 ; //File pointers for accessing map file and segment file char map_file[80] = "map1.txt"; //Default map char segment_file[80] = "segments1.txt" ; //Default segment file PAGE 82 72 BOOL CALLBACK DlgProc(HWND hwnd, UINT Message, WPARAM wParam, LPARAM lParam) { //Variables for drawing in the dialog PAINTSTRUCT ps ; HDC hdc ; static int iSelection = IDM_MAP1 ; HMENU hMenu ; switch(Message) { hMenu = GetMenu (hwnd) ; case WM_INITDIALOG: // This is where we set up the dialog box, and initialise any default values SetDlgItemInt(hwnd, IDC_NUMBER, 2, FALSE); break; case WM_PAINT: hdc = BeginPaint(hwnd, &ps) ; DrawGrid(hdc, hwnd) ; DrawMap(hdc, hwnd) ; if(Solution_Found) { DrawRobots(best_robots, hdc, hwnd) ; DrawShadows(hdc, hwnd) ; } EndPaint(hwnd, &ps) ; break ; case WM_COMMAND: switch(LOWORD(wParam)) { case IDC_SOLVE: { // When somebody clicks the Solve button, first we get the number PAGE 83 73 // they entered //Local Variables for timer time_t start, end ; double diff ; char temp[80] ; //I will place all code to run the GA here // Declare variables for the GA parameters and set them to some default values. int width ; //the number of bits int height ; //the number of individuals generated int popsize ; int ngen ; float pmut ; float pcross ; num_robots = GetDlgItemInt(hwnd, IDC_NUMBER, NULL, FALSE) ; width = 12 ; //the number of bits height = num_robots ; //the number of individuals generated popsize = 20; ngen = 200; pmut = 0.002; pcross = 0.9; //->Here I will enter my GA Stuff! //ERICA'S GA STUFF STARTS HERE drawObstacles() ; //Start the timer time (&start) ; // Now create the GA and run it. First we create a genome of the type that // we want to use in the GA. The ga doesn't operate on this genome in the // optimization it just uses it to clone a population of genomes. PAGE 84 74 GA2DBinaryStringGenome genome(width, height, Objective); // Now that we have the genome, we create the genetic algorithm and set // its parameters number of generations, mutation probability, and crossover // probability. And finally we tell it to evolve itself. GASimpleGA ga(genome); ga.populationSize(popsize); ga.nGenerations(ngen); ga.pMutation(pmut); ga.pCrossover(pcross); ga.scoreFilename("GAdata.txt"); // name of file for scores ga.scoreFrequency(1); // keep the scores of every 1 generation ga.flushFrequency(50); // specify how often to write the score to disk ga.selectScores(GAStatistics::AllScores); ga.evolve(); time (&end) ; //Stop timer diff = difftime(end, start) ; //Times functions //sprintf(temp,"Total Processing Time: %f ",diff) ; //MessageBox(hwnd, temp, "Processing Time", MB_OK) ; //Display the Processing Time to the dialog window SetDlgItemInt(hwnd, IDC_TIME, diff, FALSE) ; //Call statistics function Statistics((GAGenome&)ga.statistics().bestIndividual()) ; //Set the Solution_Found flag Solution_Found = 1 ; //Display the combined shadow area to the dialog window SetDlgItemInt(hwnd, IDC_SHADOW, best_shadow, FALSE) ; PAGE 85 75 //Clear the list box SendDlgItemMessage(hwnd, IDC_LIST, LB_RESETCONTENT, 0, 0); //Display the best robots to the dialog window (list box) for(m=0; m=0 ; n--) { robot[m][0] += genome.gene((genome.width()/2)-1 n, m) pow(2,n) ; robot[m][1] += genome.gene((genome.width()-1) n, m) pow(2,n) ; } } //Call the shadow area function score = ROW*COLUMN shadows(num_robots, robot) ; return score ; } void Statistics(GAGenome& g) { GA2DBinaryStringGenome & genome = (GA2DBinaryStringGenome &)g; float score=0.0; int count=0; int m, n ; FILE *fp ; PAGE 89 79 fp = fopen("debug.out","w") ; //Zero the robot 2D array for(m=0; m<20 ; m++) { for(n=0; n<2; n++) { best_robots[m][n] = 0 ; } } fprintf(fp, "%d \n", genome.height()) ; //Convert the binary string to integers for(m=0 ; m=0 ; n--) { best_robots[m][0] += genome.gene((genome.width()/2)-1 n, m) pow(2,n) ; best_robots[m][1] += genome.gene((genome.width()-1) n, m) pow(2,n) ; } fprintf(fp, "%d %d\n", best_robots[m][0], best_robots[m][1]) ; } //Call the shadow area function best_shadow = shadows(num_robots, best_robots) ; fprintf(fp, "%d \n", best_shadow) ; fclose(fp) ; } /////////////////////////////////////////////////////////////////////////////// //FUNCTION NAME: drawObstacles //DESCRIPTION: This function opens a file that contains obstacle location // information. This info. is placed into a matrix // called 'obstacles_matrix'. /////////////////////////////////////////////////////////////////////////////// void drawObstacles(void) { int i = ROW; PAGE 90 80 int j = COLUMN; FILE *fp; int m, n; //Open the file to be read fp=fopen(map_file, "r"); /*******WARNING: map_file is a global var.**********/ //Scans the file and colors in the points until it reaches the end of the file while (fscanf(fp, "%i%i", &m, &n) > 0) { if(m 0) { segments+=1 ; } segments -= 1 ; /* //Open the file containing the # of robots and robot positions fp3 = fopen("robotPositions.txt", "r") ; fscanf(fp3, "%i", &num) ; //This is the number of robots for(n=0; n h) t=h; else t=w; for (i=0; i < ROW; i++) { for (j=0; j < COLUMN; j++) { Ellipse(hdc,t*i+10,t*j+10,t*(i+1)+10,t*(j+1)+10); } } } /////////////////////////////////////////////////////////////////////////////// //FUNCTION NAME: DrawMap //DESCRIPTION: This function opens a file that contains obstacle location // information. It then re-draws the obstacle and colors the // circle green and displays it to the window. /////////////////////////////////////////////////////////////////////////////// void DrawMap(HDC hdc, HWND hwnd) { int i = ROW; int j = COLUMN; FILE *fp; int m, n; int w, h; //Window width and height counters int t; //Based on the shape of the window, t is used to ensure the ellipses are acutally circles. HPEN hpen, hpenOld ; HBRUSH hbrush, hbrushOld ; RECT dimensions ; //Variable to a structure containing the window dimensions //Get the Current Window Size GetClientRect(hwnd, &dimensions) ; PAGE 100 90 //Create a Brush hbrush = CreateSolidBrush(RGB(0,255,0)); //A Green Brush //Select the brush SelectObject(hdc, hbrush) ; //Re-Draw the Obstacle Points in window w = (dimensions.right-100) / COLUMN; h = dimensions.bottom / ROW; if (w > h) t=h; else t=w; //Open the file to be read fp=fopen(map_file, "r"); /*******WARNING: map_file is a global var.**********/ //Scans the file and colors in the points until it reaches the end of the file while (fscanf(fp, "%i%i", &m, &n) > 0) { if(m h) t=h; else t=w; for(m=0; m h) t=h; else t=w; for(m=0; m #include #include #include 93 PAGE 104 94 #include #define RANGE 50 #define MAX_RAND 32767.0 //maximum random number #define SIZE 5 //maximum size (radius) of an obstacle /*Function Protoypes*/ void randomMap() ; /*Global Variables*/ int main(int argc, char* argv[]) { //cout << "Please enter the desired number of obstacles: ; //cin >> num_obstacles ; randomMap() ; printf("The obstacle information was written to: map.txt\n") ; printf("The line segment information was written to: segments.txt\n") ; return 0 ; } /* FUNCTION NAME: randomMap DATE: Oct. 14, 2002 DESCRIPTION: This function will take the value entered by the user and generate that many random obstacles. The positions will be stored to a file called 'map.txt' This function will also save the line segments that make up the boundary of each obstacle to a file named 'segments.txt'. */ void randomMap() { int xcenter, ycenter ; //Obstacle's center point int i,j,k ; int radius ; //Radius of the obstacle int num_obstacles ; //User specified number of obstacles PAGE 105 95 FILE *fp1 ; FILE *fp2 ; FILE *fp3 ; /*Open the files to be written to or read*/ fp1 = fopen("map.txt", "w") ; fp2 = fopen("mapdata.txt", "r") ; fp3 = fopen("segments.txt", "w") ; fscanf(fp2, "%d", &num_obstacles) ; for(i=0; i