Colloquium Series Fall 1999

Advances in computing hardware, software, and network technology have enabled a new class of interactive applications involving 3D animated characters to become increasingly feasible. Many such applications require algorithms that allow both autonomous and user-controlled animated human figures to move naturally and realistically in response to task-level commands. In this talk, I will present a research framework aimed at facilitating the high-level control of animated characters in real-time virtual environments. The framework design is inspired by research in motion planning, control, and sensing for autonomous mobile robots. In particular, the problem of synthesizing motions for animated characters is approached from the standpoint of modeling and controlling a "virtual robot".

Two important classes of task-level motion control are investigated in detail: goal-directed navigation, and the grasping and manipulation of virtual objects. First, I will present a technique for quickly synthesizing from navigation goals the collision-free motions for animated human figures in dynamic virtual environments. The method combines a fast 2D path planner, a path-following controller, and cyclic motion capture data to generate the underlying animation. The rendering hardware is used to simulate the visual perception of a character, providing a feedback loop to the overall navigation strategy. Second, I will describe a method for automatically generating collision-free human arm motions to complete high-level object grasping and manipulation tasks. Given a target position and orientation in the workspace, a goal configuration for the arm is computed using an inverse kinematics algorithm that attempts to select a collision-free, natural posture. If successful, a randomized path planner is invoked to search the configuration space (C-space) of the arm, modeled as a 7-DOF kinematic chain, for a collision-free path connecting the arm initial configuration to the goal configuration. Several video clips of interactive animation sessions using implementations of the above techniques will be shown.

For a web site related to this work please go here.

BACK

We give a new primality testing algorithm by reducing primality testing for number n to testing if a specific univariate identity over Z_n holds.

We also give new randomized algorithms for testing if a multivariate polynomial, over a finite field or over rationals, is identically zero. The first of these algorithms also works over Z_n for any n. The running time of the algorithms is polynomial in the size of arithmetic circuit representing the input polynomial and the error parameter. These algorithms use fewer random bits and work for a larger class of polynomials than all the previously known methods, e.g., the Schwartz-Zippel test, Chen-Kao and Lewin-Vadhan tests.

Our algorithms first transform the input polynomial to a univariate polynomial and then use Chinese remaindering over univariate polynomials to efficiently test if it is zero.

BACK

Software development "just ain't what it used to be". Prof. Baker and Dr. Barrero are currently working on a software development project with the following features/requirements: client-server system architecture, at least 1,000 concurrent client users, web-based (using the http protocol to move serialized Java objects) and "connected/ unconnected" client execution required. The project is using Java as the implementation language, IBM's VisualAge(tm) as the IDE, and Rational's RationalRose(tm) High-level Design Tool, including the code generation capabilities of RationalRose.

We will present an overview of the architecture of this system and an introduction to the development methodology being employed. It is hoped the architecture and methodology will, in themselves, be of interest. However, the main purpose of the talk is to identify the "fundamental concepts" that underlie the architectural features and project methodology. with the expressed intention of influencing the design of software development curricula.

BACK

Starting with an overview of several viruses, including their properties, origins, and flaws, this talk presents precursors of viruses and worms and changes in the computing milieu that have materially contributed to the phenomenon. It then gives definitions of the intruders, reviews the Internet attack, and comments on detection and prevention.

BACK

A vertex subset S of a graph G is said to be an independent dominating set if elements of S are mutually nonadjacent in G, and each vertex not in S is adjacent to at least one element of S. Obtaining a smallest independent dominating set (s.i.d.s.) is a classical combinatorial problem with applications in areas such as game theory, coding theory, channel assignment and resource placement. The problem is NP-hard, and remains so even if the graph is known to be bipartite. The present talk discusses vertex partitions of products of certain cycles into s.i.d.s.'s. The products considered are: (i) Cartesian, (ii) Kronecker and (iii) strong. The methodology consists of labeling the vertices in such a way that distinct vertices labeled alike are at a distance of at least three. Optimality is achieved by noting that the number of labels used is equal to D + 1, where D is the degree of the (regular) graph.

BACK

Grasping a curved object free in the plane may be done through rolling a pair of fingers on the object's boundary. Each finger is equipped with a tactile sensor able to record instantaneous point contacts with the object. Contact kinematics reveal a relationship between the amount of finger rotations and the total curvatures of the boundary segments of the fingers and the object respectively traversed by the two contact points during the same period of rolling. Such relationship makes it possible to localize both fingers relative to the object from a few pairs of simultaneously taken finger contacts at different time instants. A least-squares formulation of this localization problem can then be solved by the Gauss-Newton algorithm. Simulation results are presented.

After localization, a simple open-loop strategy is used to control the continual rolling of the fingers until they simultaneously reach two locations on the object's boundary where a grasp is finally performed.

BACK

What do graduate students do with all that time they spend not sleeping? They work on their research, of course! This will be an opportunity to glimpse the enormous breadth and depth of research being conducted in our department and by our affliated faculty. Over 15 different areas of research will be presented throughout the first and second floors of Atanasoff Hall, ranging from AI and Robotics to Programming Languages and Computational Complexity. A few of the topics are:

• Software Safety
• Parallelization Agent, parAgent, for Automatic Transformation and Parallelization of Legacy Codes
• Java Modeling Language
• Instance Complexity and Average Case Complexity
• Adding Multiple Dispatch to Java
• Distributed System Software and Security
• Branch-Decoupled Architectures
• Building software for parallel computers
• Software environment for application developers
• Intrusion detection using mobile agent technology

Graduate students and faculty will be available to answer your questions and describe their work. Refreshments will be available in the conference room during the entire 3:40-5:00 session. This should be a fun, informal, and informative time. Undergraduates are especially welcome! Don't miss it!

BACK

Many temporal extensions of the relational data model have been proposed for the SQL standard, but no similar attempts have been made to extend the standard for object-oriented databases, defined by ODMG. In particular the impact of granularity in temporal data on a temporal object-oriented data model has not been investigated adequately. A drawback of the existing proposals is the lack of a formal basis - which we believe is essential to manage the inherent complexity of the object-oriented data model. In this talk we present an object-oriented data model supporting multiple temporal granularities compliant to the ODMG standard data model. We formally define the set of legal values for our type system. Finally, we address issues related to inheritance, type refinement and substitutability.

BACK

Recent constructions for Venn diagrams for arbitrary numbers of sets have shown how they map the Gray code and have led to new forms which similarly map the binary code. They also depict the "revolving-door algorithm". Further developments have revealed classes of symmetrical diagrams for prime numbers of sets, leading to the conjecture that such diagrams always exist. The complete enumeration for 7 sets will be given.

BACK

In this talk, I will address the problem of manipulating an object in the plane using a succession of contacts with simple robotic devices that may have discrete or continuous degrees of freedom. The problem of planning the overall object trajectory is reduced to constructing a sequence of atomic robot motions between equilibrium states of the system. The proposed approach is based on constructing the of each equilibrium, i.e., the maximal subset of the object's configuration space such that any motion starting within this subset is guaranteed to end up in the equilibrium configuration. In particular, we do not assume that contact is maintained during the execution of the manipulation task; nor do we attempt to predict the object motion between equilibria. I will discuss applications of this approach to three problems:

I will also present preliminary experiments with actual robotic devices, including three Nomadic Super Scout II mobile robots and prototypes of the reconfigurable gripper and of the proposed Pachinko machine developed at the University of Illinois.

BACK

Risk and Safety analyses are two examples of tasks that can involve arithmetic on variables whose values can be uncertain. When two variables are described by distribution functions, and are known to be independent, their sum, product, difference, etc. may be found by discretizing the distributions into intervals and associated probabilities, and reducing the problem to one of calculations on intervals. The result is bounds on the distribution function of the result, with finer discretizations yielding better bounds.

The problem is trickier when the independence assumption is relaxed and no assumption is permitted about the dependency or lack thereof of the variables upon each other. An answer is still possible, but is in the form of a bounded space within which the distribution function of the result must fall for any given dependency relationship between the two input variables. Two methods for this are known. I will review the one developed by my students and I, review how it can be done, and provide copies of a relevant paper to those interested in the full details of the method. Various curves and bounds produced by a software package will provide a visual illustration of the problem.

BACK

Specification of software for safety critical, embedded computer systems has been widely addressed in literature. To achieve the high level of confidence in a specification's correctness necessary in many applications, manual inspections, formal verification, and simulation must be used in concert. Researchers have successfully addressed issues in inspection and verification; however, results in the areas of execution and simulation of specifications have not made as large an impact as desired.

In this talk we present an approach to specification-based prototyping which addresses this issue. The approach combines the advantages of rigorous formal specifications and rapid systems prototyping. It lets us refine a formal executable model of the system requirements to a detailed model of the software requirements. Throughout this refinement process, the specification is used as a prototype of the proposed software. Thus, we guarantee that the formal specification of the system is always consistent with the observed behavior of the prototype. The approach is supported with the Nimbus environment, a framework that allows the formal specification to execute while interacting with software models of its embedding environment or even the physical environment itself (hardware-in-the-loop simulation).

BACK

In a heterogeneous distributed environment where multiple applications compete and share a limited amount of system resources, applications tend to suffer from variations in resource availability. It is desired that they adapt their behavior to the resource variations of the system above a minimum Quality of Service (QoS) guarantee. On one hand, current adaptation mechanisms built within an application have the disadvantage of lacking global information to preserve fairness among all sharing applications. On the other hand, the adaptive resource management built within operating system ignores the data semantics of the application. Hence, we believe that a proper adaptive behavior of QoS can be achieved in a middleware framework, having data semantics of the application as well as understanding of underlying resource management dynamics.

In this talk, we present a control-theoretical middleware framework to enhance QoS adaptations by dynamic control and reconfiguration to the internal functionalities of a distributed multimedia application. We will present analytical and experimental validations. We have developed the Task Control Model and implemented it within an experimental client-server visual tracking system to evaluate our middleware framework. To maintain tracking precision in a specified range, the middleware framework controls the tracking application according to the current system dynamics.

BACK

Visit Prof. Baker's homepage here.

Alejandro Barrero is a Senior Consultant with ABC Virtual Communications, Inc. in Des Moines, Iowa. He has over 20 years experience as a manager and technical developer in a variety of industry positions. His professional experience has focused on distributed applications with object-oriented designs. Barrero holds the Ph.D. Degree in Electrical Engineering from the University of Tennessee. 

BACK

Ernst L. Leiss, our ACM Distinguished Speaker, received degrees in computer science and in mathematics from the University of Waterloo and the Technical University of Vienna. He joined the Department of Computer Science at the University of Houston in 1979; in 1985 he became the director of the Research Computation Laboratory. He (co)authored about 120 technical papers; he wrote Principles of Data Security (1982, Plenum) and Software Under Siege: Viruses and Worms (1990, Elsevier). He contributed articles on data-security and on computer viruses to the Encyclopedia of Physical Science and Technology (1987 and 1990, Academic Press). Since 1983, he has been (co)PI on research funded at over $2.5 million. His research interests range from vector/parallel computing to data security, geophysical data processing, databases, and theory of formal languages. He is a member of ACM and EATCS, a Senior Member of IEEE, and an Active Member of SEG. 

Visit Prof. Leiss's homepage here.

BACK

Pranava K. Jha is from India, working currently in Malaysia at Multimedia University, Melaka. He earned his Ph.D. in computer science from Iowa State University in 1990 under the tutelage of Dr. Giora Slutzki. His publications are in the areas of hypercubes, median graphs and products of graphs. Dr. Jha is a member of Upsilon Pi Epsilon. 

Visit Prof. Jha's homepage here.

BACK

Yan-Bin Jia is an assistant professor in the Department of Computer Science at Iowa State University. He received a Ph.D. in robotics from School of Computer Science at Carnegie Mellon University in 1997. Before joining ISU, he taught at CMU and was on the faculty at University of Minnesota. His research interests include robotics, artificial intelligence, geometric computing and modeling, optimizations, nonlinear control, and kinematics and dynamics of manipulation. 

Visit Prof. Jia's homepage here.

BACK

The Graduate Advisory Committee, or GAC, was formed in the the spring semester of 1999 to serve as an advisory committee to the department chairperson. The committee's role has since evolved. We seek to provide a common focal point for computer science graduate student concerns. By directing graduate student concerns through a single committee we are able to focus our efforts and achieve greater impact than each student might be able to achieve individually.

Finally, the committee works to welcome new graduate students by sponsoring a mentoring program for incoming students, hosting a welcome session at the beginning of each semester, and participating in the ComS 591 orientation class.  

Visit the GAC homepage here.

BACK

Isabella Merlo received a MS Degree in Computer Science (with honors) at the University of Genova in 1996. Since November 1996, she is enrolled in a Ph D program, under the supervision of Prof. Elisa Bertino, in the Department of Computer and Information Sciences of the University of Genova as a member of the Databases and Information Systems Group. Her current research interests include object-oriented, active and temporal databases, data models for management of semi-structured data. She was one of the organizers of the ECOOP'99 (European Conference on Object-Oriented Programming ) Workshop on Object-Oriented Databases. 

BACK

Dr Anthony Edwards is Reader in Biometry at the University of Cambridge. He studied genetics under R.A.Fisher and held postdoctoral posts at the University of Pavia, Italy, and Stanford University. After three years as Senior Lecturer in Statistics at the University of Aberdeen, Scotland, he returned to Cambridge as a Fellow of Gonville and Caius College and subsequently Reader in the University. Dr Edwards is known for his work with Professor L.L.Cavalli-Sforza in writing the first computer programs for the estimation of evolutionary trees in the 1960s. He is the author of the books Likelihood (1972; currently Johns Hopkins University Press, 1992), Foundations of Mathematical Genetics (Cambridge University Press, 1977 & 2000) and Pascal's Arithmetical Triangle (Oxford University Press New York, 1987). He is at present collaborating with Professor Herbert A. David of Iowa State University on a book Annotated Readings in the History of Statistics. His interest in Venn diagrams stems from designing a stained-glass window for the college hall in memory of John Venn, who was President of Gonville and Caius College. 

Visit Prof. Edwards' homepage here.

Jean Ponce received his These d'Etat from the University of Paris, Orsay in 1988. He is currently a professor in the Department of Computer Science at the University of Illinois at Urbana-Champaign and a full-time Beckman Institute faculty member in the Artificial Intelligence Group. His fields of professional interest are computer vision and robotics. 

Visit Prof. Ponce's homepage here.

BACK

Daniel Berleant recently joined the Dept. of Electrical and Computer Engineering at Iowa State University as an Associate Professor. He received his PhD from University of Texas at Austin in 1991. In addition to the topic of this colloquium he also works in the areas of software engineering and Web Based systems. 

BACK

Dr. Heimdahl earned a M.S. in Computer Science and Engineering from the Royal Institute of Technology in Stockholm, Sweden and a Ph.D. in Information and Computer Science from the University of California at Irvine. He is the McKnight Land-grant Assistant Professor of Computer Science and Engineering at the University of Minnesota. He was a member of RTCA Special Committee 147 and was one of the project leads for the development of the formal requirements specification for TCAS II (Traffic alert and Collision Avoidance System II).

Dr. Heimdahl's research interests are in software engineering, formal specification languages, and automated analysis of specifications. In particular, he is interested in software development for safety critical control systems. He is currently pursuing his interest in static analysis of state-based models and is investigating how dynamic methods, for example, simulation and testing, can be used to validate requirements specifications for embedded systems. In addition to his academic career, Dr. Heimdahl consults for industry and has taught courses in software development for safety critical systems, object-oriented development, and C++ programming. He also serves as an expert witness in cases related to the use of software in safety. Dr. Heimdahl is a recipient of the NSF Career award. 

Visit Prof. Heimdahl's homepage here.

BACK

Visit Prof. Nahrstedt's homepage here.

BACK

Thank you for visiting this page. Please send your suggestions and comments to one of us in the Computer Science colloquium committee.

• Soma Chaudhuri . chaudhur@cs.iastate.edu
• Curtis Clifton. cclifton@cs.iastate.edu

(Top)

---