ASPHD_CSC Archives

PhD Student


Options: Use Forum View

Use Monospaced Font
Show Text Part by Default
Show All Mail Headers

Message: [<< First] [< Prev] [Next >] [Last >>]
Topic: [<< First] [< Prev] [Next >] [Last >>]
Author: [<< First] [< Prev] [Next >] [Last >>]

Print Reply
Tammie Dudley <[log in to unmask]>
Reply To:
PhD Student <[log in to unmask]>
Thu, 6 Oct 2011 11:44:03 -0400
text/plain (18 lines)
Departmental Colloquium
2:30 pm, 10/07/2011, Friday, Department Conference Room

Dr. Piotr 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 life-time energy (battery power), this motivates our objective: minimize the maximum distance traveled by a robot.
In graph-theoretic 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.