Mobile Edition
Print
Get the Mag
Weekly Updates1. Introduction
An Autonomous Guided Vehicle (AGV) must continuously determine its position within a manufacturing facility in order to find a path to a desired destination. While Global Positioning Systems (GPS) have provided a reliable and cost-effective solution for location outdoors, no equivalent solution exists for interior environments. One of the most common Local Positioning Systems (LPS) for indoors is the so-called beacon or landmark navigation. The approach is similar to GPS in that the position of the AGV is determined by a process known as three-dimensional multilateration. With this technique, the position of the vehicles is computed as the intersection point of several spheres that have their centers at the beacons' positions and radii equal to the distance between beacons and the mobile element. The reliability and robustness of these positioning systems depend on the correct location of the beacons. An ineffective beacon configuration results in some areas that are either not covered at all or where the position cannot be calculated (e.g., when the beacons within the sensor range are in line with the vehicle).
Complete coverage and absence of singularities in an area does not guarantee accuracy in the position estimation. Geometric dilution of precision or DOP is a measure of position accuracy (Yarlagadda. 2000). The DOP acts as an amplification factor that translates errors in the range estimation to errors in the position estimation. Hence, even starting from fairly accurate range measurements, the position estimation may contain large errors if the DOP at the measurement point is high. This may be caused, for example, by the configuration geometry of the beacons in sight.
The problem of finding a beacon configuration that meets a desired level of accuracy and reliability is relatively simple in small regular areas (e.g., a square). In practice, however, the areas to be covered may be irregular (e.g., those with several rooms with different shapes, passage ways and corridors), forcing the use of a large number of beacons that must be located in such a way that the resulting design is not only usable but also cost-effective and flexible. Fundamentally, this engineering design problem is multi-objective in nature. Specifically, we seek a beacon configuration that is optimal or near to optimal with respect to three objectives.
1. Minimize the number of beacons. While the cost of the beacons is relatively low compared to other costs in a manufacturing facility, minimizing the number of beacons results in time savings and translates into higher system flexibility, scalability and capacity to cover large areas (Sinriech and Shoval, 2000). Flexibility is important because short product life cycles force manufacturing facilities (particularly those in the high-tech and electronic industries) to change process configurations that result in new vehicle paths.
2. Maximize the coverage of the workspace. The covered workspace is defined as the area where the required number of beacons is available and their configuration results in an acceptably low DOP. The uncovered area consists of singular points with high (even infinite when the beacons are positioned in a straight line) DOP values, and points where the beacons in Line Of Sight (LOS) are not sufficient for trilateration. In the current context, we require three beacons because we use spherical positioning. However, it is possible for other applications to require more beacons. In practice, less than 100% coverage might be acceptable, if the number of beacons needed to reach difficult points (e.g., corners) is unreasonably large.
3. Maximize the percentage of the area that is covered with admissible DOP values. Lower DOP values mean that the estimations of the positioning system are more accurate. Admissible DOP values depend on the manufacturing context and therefore the setting of a threshold is an a priori design decision. Maximizing the covered area that falls below the chosen threshold becomes an objective of the optimization process.
As described in Roa et al. (2005), a number of studies have been reported in the literature concerning the problem of optimally locating beacons, for instance the work by Oh and No (1994) in a nuclear reactor facility and the articles by Kang et al. (1996) and Kang et al. (1998) that address optimal placement of sensors for vibration control of laminated beams and plates, respectively. The work that is closest to our current development is the article by Sinriech and Shoval (2000). They developed a non-linear mixed-integer programming model to minimize the number of beacons subject to covering a set of critical points in a work area. The model calculates Euclidean distances between the selected beacons and the critical points and forces at least three beacons to be within a specified range to each of the critical points in the entire area. The three-beacon requirement is the same that we impose to be able to calculate the position of a vehicle using triangulation. The given range (specified by a minimum and maximum distance to a critical point) is related to the physical limitation of the laser navigation system used in the specific environment being studied. Sinriech and Shoval (2000) do not solve the proposed model due to its complexity. Instead, they relaxed the model by removing all non-linearities and solved the resulting set covering problem in order to find a lower bound in the number of beacons. The set covering formulation assumes that beacons can only be placed in the intersections of a grid that is overlaid on the work area. There is a constraint for each critical point that forces the point to be covered by at least three beacons. The constraint coefficients are zero or one to indicate whether or not a beacon placed in a particular grid intersection covers a critical point. A greedy heuristic is then used to find a feasible solution to the problem. The heuristic considers, in descending order, the locations in the grid that will cover the most number of critical points. As beacons are added to these locations, the convexity constraints (which are relaxed in the set covering problem) are checked. The convexity constraints ensure that each critical point is located within the convex hull of the set of beacons serving the critical point.
Although the work of Sinriech and Shoval (2000) addresses certain aspects of the problem that are of interest to us (e.g., the minimization of the number of beacons), their procedure focuses on finding a beacon configuration that covers critical points (such as pick up delivery points for material handling vehicles) as opposed to one that covers an entire area. To the best of our knowledge, the only existing procedure for the optimization problem that we propose to tackle is the Genetic Algorithm (GA) described by Roa et al. (2005). This basic GA follows the traditional literature (see e.g., Holland (1975)) and starts with a population of solutions consisting of beacons deployed at random positions. Solutions were represented as sets of two-dimensional coordinates indicating the location of each beacon. Experiments showed that a large computational effort was required to obtain designs of a reasonable quality. It was also observed that occasionally the GA was unable to escape inferior local minima even when allowed to run for an extended amount of time. Our current goal is to overcome these deficiencies with a different heuristic approach and compare our results to the GA implementation.
2. Problem description
In interior spaces, such as industrial bays or office spaces, where a navigation system for robots or autonomous vehicles is being considered, it is necessary to first determine the characteristics of the work area that are relevant to the optimization process. These characteristic include the navigation area, beacon area and possible obstacles (as described below). Since beacon capabilities are considered known, the problem consists in finding the placement of a minimum number of beacons that maximizes coverage of the navigation area while guaranteeing reliability and achieving a desired level of accuracy in the position estimations (i.e., a low DOP).
We define three types of areas within the indoor facility: (i) navigation area ([A.sub.v]); (ii) beacon area ([A.sub.b]); and (iii) obstacles ([A.sub.o]). Figure 1 shows a schematic representation of these areas.
[FIGURE 1 OMITTED]
The navigation area is shown in light gray and represents the space on the floor where the vehicle moves and localization services must be provided. The grid represents the area on the ceiling of the facility where beacons could be located (i.e., the beacon area). Finally, the black and dark gray areas are obstacles that the vehicle must avoid. Some obstacles, such as walls, reach the ceiling of the facility and interrupt the signals used for positioning, acting as discontinuities in the beacon area. Other obstacles, however, do not reach the ceiling and therefore only affect the navigation area. In general, the navigation area does not have to be the same as the beacon area.
This problem is general in the sense that it can be applied to multilateration processes regardless of the technology used to estimate the range between the beacons and the mobile device (e.g., RF, UF, IR, UWB or laser) (High-tower and Borriello, 2001). Different technologies can be considered within this framework by a precise characterization of the transducers used for emission and reception (in terms of patterns of emission, maximum range, etc.). In the current setting, we consider a sub-centimeter exact ultrasonic positioning system where broadband transducers and Golay codes are used to codify the emitted signals, allowing increased noise immunity, capability of simultaneous measurements and increased precision (Prieto et al., 2007). In this system, ranges to the mobile vehicle are estimated by measuring the time-of-flight (TOF) of RF-synchronized ultrasonic signals traveling from emitters to receivers. This is a common scheme used in the Robotics community for navigation of AGVs (Hazas and Ward, 2003; Yi, 2003).
FEED