Forward ray tracing and remote object location in two dimensions.

A Remote Object Location (ROL) system comprises a number of sensors probing for some targets in an environment via certain transmission media. Two problems arise in establishing a ROL system: the layout problem, in which the number and the locations of sensors are to be determined; and the object-location problem, in which target locations are sought based on data gathered by the sensors. These two problems have simple solutions where the line-of-sight can be established between the target and the sensor, but where line-of-sight is not available and signals reflect, these two problems become much more complicated. We study the two problems in a given reflective, polygonal environment, using distance sensors. Distance is obtained from the time-of-flight, the time needed for signal to travel the shortest path between the target and the sensor. Hence with distance sensors, both problems are closely related to finding the shortest path with reflections. By devising a new data structure, the Shortest Reflection Diagram (SRD), we present developments for both ROL problems. The SRD is a partition of the environment into regions where the shortest paths from all points in a region bounce off the same sequence of walls to reach the sensor. A sensor layout is unique if it can precisely locate an object appearing anywhere in the environment. By merging multiple SRDs, we show that two points can be ambiguous to a set of sensors in two ways: they can be locally ambiguous if they are from the same region in the merged SRD, or globally ambiguous otherwise. Local ambiguity is detectable by the existence of symmetry lines, and global ambiguity by surface intersections in the distance space, thus leading to two algorithms for testing a sensor layout for uniqueness. A heuristic incorporating these two algorithms has been developed to identify a unique layout. By extending the definition of bisectors to reflective environments, a more structured method for finding unique layouts is also presented. The SRD also facilitates an accurate and efficient solution to the object-location problem by eliminating the need to recompute the signal paths every time. This contrasts with the total enumeration which would otherwise be necessary. An algorithm is presented which returns all feasible object locations using a precomputed SRD. The expected gain in accuracy is verified with an implementation.Ph.D.Applied SciencesComputer scienceIndustrial engineeringSystems scienceUniversity of Michigan, Horace H. Rackham School of Graduate Studieshttp://deepblue.lib.umich.edu/bitstream/2027.42/132271/2/9959884.pd