Narrow Results

This paper deals with the development of 2-D space maps during navigation in unknown environments, by synthesizing the shapes of consecutive free spaces. Each shape extracted from each current-free navigation space is represented by attributed graphs. Thus, the synthesis of the shapes is based on the synthesis of graphs for the generation of new graph forms that represent the new shape traveled by an autonomous robot. Illustrative examples from a space with obstacles are presented.

In massively parallel systems, the performance gains are often significantly diminished by the inherent communication overhead. This overhead is caused by the required message passing resulting from the task allocation scheme. In this paper, techniques to reduce this communication overhead by both scheduling the communication and determining the routing that the messages should take within a tightly-coupled processor network are presented. Using the recently developed Collision Graph model, static scheduling algorithms are derived which work at compile-time to determine the ordering and routing of the individual message transmissions. Since a priori knowledge about the network traffic required by static scheduling may not be available or accurate, this work also considers dynamic scheduling. A novel hybrid technique is presented which operates in a dynamic environment yet uses known information obtained by analyzing the communication patterns. Experiments performed show significant improvement over baseline techniques.