Departmental Colloquium
2:30 pm, 10/07/2011, Friday, Department Conference Room
Dr. Piotr Berman
http://www.cse.psu.edu/people/berman
Associate Professor
Department of Computer Science and Engineering
Penn State University
"Planning Robotic Motion"
Our problem is motivated by sensor networks in which a large number of sensors is randomly or arbitrarily placed, and we want to achieve some important network property by changing their positions. The assumption is that each individual sensor has only limited lifetime energy (battery power), this motivates our objective: minimize the maximum distance traveled by a robot.
In graphtheoretic formulation, we have an undirected graph, and in one step each robot can traverse to an adjacent node; we minimize the number of steps. The first goal we investigate is that robot cover a path between a given pair of nodes, we show that no approximation within factor better than 2 is possible while our algorithm has approximation ratio 7. Other goals are: to connect all robot positions and to connect a set of given nodes.
About the Speaker:
Piotr Berman joined Penn State in September 1982. His earlier education took place in Poland, where he received his master's degree from the Department of Mathematics and Computer Science, Uniwersytet Warszawski (University of Warsaw). He pursued further graduate research at Instytut Matematyczny PAN (Mathematics Institute of the Polish Academy of Sciences) prior to coming to the United States to study for his doctorate at MIT. Currently, Dr. Berman is working on theoretical issues of distributed systems and approximation algorithms. In general, he is interested in the theory of algorithms and its applications in other areas of computer science, such as distributed databases and biological computing.
===============================
