Vol. 3, No. 1 Spring 1992 CENTRE FOR INTEGRATED COMPUTER SYSTEMS RESEARCH • C -I • C • S • R THE UNIVERSITY OF BRITISH COLUMBIA FOCUS THE NEW RECRUITS CICSR welcomes seven talented new researchers with very diverse interests ■ The research interests of the new crop of CICSR faculty members profiled in this issue defy categorization. They range from walking robots to automated fish processing, with geometric problems, electromagnetic theory, computer logic, medical imaging and VLSI chip design in between. Some of the researchers are interested in applied research, while others focus on theory. One thing you can generalize about, however, is the skill and aptitude of the researchers themselves. They are young, ... continued on page 2 The seven newest CICSR members, from left, back row: Jack Snoeyink, Matthew Palmer, Hussein Alnuweiri; front row: Dinesh Pai, Ray Gosine and Craig Boutilier. 1 IN THIS ISSUE Palmer improving medical imaging page 2 Shapes of all kinds page 3 Computer logic theory page 4 Machines that move page 5 Industrial automation: a practical perspective page 6 Parallel computing and electromagnetic theory page 7 NEW RECRUITS ... continued from cover talented and enthusiastic new members of the UBC faculty. These seven people have come to UBC in the past year from various parts of the world, as far afield as India, England and Saudi Arabia. They have training at the world's finest academic institutions, including Cambridge, Stanford and M.I.T. Many of the new faculty members are already working on collaborative projects with other CICSR members; others plan to do so in the near future. In general, they commend the goals of CICSR and are looking forward to meeting and working with more CICSR members. We decided to get the ball rolling by introducing CICSR Focus readers to all of the new faculty members and their work in this Improving medical imaging Director's Statement Over the last five years, membership in CICSR has doubled from 30 to 60. Most of this increase is due to the intensive faculty recruiting efforts of the three constituent UBC departments: Computer Science, Electrical Engineering, and Mechanical Engineering. This recruiting has been remarkably successful. These recruits are young (under 35 in most cases), talented, and come from diverse backgrounds. Four have recently been recommended for fellowships with the Advanced Systems Institute of B.C. We thought it would be. interesting to profile some of the newest of our new recruits, and in this issue of the newsletter, we will focus on seven who have been hired over the past year — three in Computer Science, three in Electrical Engineering and one in Mechanical Engineering. ■ ■ Improving the quality and precision of medical imaging is the main research interest of Matthew Palmer, a new member of the Department of Electrical Engineering. UBC is an excellent place to pursue his research — he is working with UBC hospital researchers and has also used the positron emission tomograph (PET) facilities at TRIUMF. Palmer's work is multidisciplinary, involving basic physics, image processing and engineering. Palmer is now working in conjunction with UBC hospital staff to use magnetic resonance imaging (MRI) to study multiple sclerosis. "The project has raised questions on how we handle and process images using the computer," said Palmer. One question he would like to answer is: What sort of image-based measurements can you achieve and what effects them? Precise measurements are not crucial for diagnosis of patients, which is usually done visually, but are important for medical researchers. Palmer says that using MRI, a very safe form of medical imaging, researchers can do as many scans as they want and look for changes in the brain almost hourly. However, to get meaningful results from this data, they need precise measurements of location of lesions, areas of coverage, distribution within the brain and changes over time. Palmer is working on various aspects of this problem, from image-based measurements to hardware development to hold the patient's head in the right place. Palmer is also at work on a very different research project: the study of focus waves. These waves, discovered in the past ten years, provide novel solutions to 150- year-old wave equations. Some of these solutions have the ability to propagate over very large distances without losing their focus. Although the research is at a very early stage, Palmer thinks it may be possible to incorporate these waves into better probes for medical scanning. "They produce a different type of beam that could be useful in ultrasound imaging and possibly in ultrasound tomography," said Palmer. Palmer and a colleague have simulated focus waves on the computer, but haven't yet figured out a practical way to physically generate these waves. Generation of focus waves would take a tremendous amount of equipment, and because they're so new, nobody knows how to control them or generate them properly, said Palmer. He plans to continue refining computer generation of focus waves, breaking them into physically realizable elements. It is possible, in theory, to generate waves that propagate forever without losing their focus, but this would require an infinitely large transmitter. However, if Palmer's scaled-down focus waves look promising in simulation, he plans to build a device to generate them. "It could be a new kind of ultrasound probe, but that's getting far ahead of where we are now," said Palmer. ■ Matthew Palmer Palmer is now working in conjunction with UBC hospital staff to use magnetic resonance imaging (MRI) to study multiple sclerosis. The project has raised questions about how we handle and process images using computers. Jack Snoeyink "Lots of two-dimensional objects are easy to understand — you can separate any problem into two problems. Three-D is much more difficult. But we live in three dimensions, so I'd like to try and understand it." Shapes of all kinds interest Snoeyink ■ Jack Snoeyink's main research interest is in using the computer to solve geometry problems, or problems best stated geometrically. He is studying the design and analysis of algorithms of geometric computation and its application to problems arising in solid modelling, CAD/ CAM, computer graphics, data structuring and robotics, as well as to discrete geometry and topology. To simplify, Snoeyink is interested in shapes of all kinds. He is a visual thinker, and doesn't describe anything without drawing a picture of it. He loves geometric puzzles — complicated structures you can take apart and put together again if you have the skill and patience — the more complicated the better. Snoeyink is interested in three-dimensional objects, and most of his research projects involve 3-D. "Lots of two-dimensional objects are easy to understand — you can separate any problem into two problems. Three-D is much more difficult. But we live in three dimensions, so I'd like to try and understand it. I'm a theoretician," said Snoeyink. One of the projects Snoeyink is currently working on is the development of efficient algorithms to overcome cartographers' line simplification problem. When map-makers receive digitized data from actual photographs, there is far too much data to display clearly, so many of the coordinates have to be discarded. Cartographers currently throw away point arbitrarily and then look for best-fit curves. This arbitrary process is slower and less accurate than it could be. Snoeyink's approach to the problem is quite different. He enlarges the points so that simpler lines can be drawn through them, with much fewer segments. "I don't pay the cost of finding the absolute best, but I can guarantee the resulting shape beforehand," said Snoeyink. "It's better than arbitrarily throwing away points." Snoeyink is also working on the analysis and decomposition of non-convex objects, which are among the most difficult three- dimensional objects to analyze. For CAD systems to incorporate such objects, and to analyze their structural properties, these objects must be broken up into convex pieces. Snoeyink is working on an algorithms to cut polyhedrons into the fewest number of convex pieces possible and analyze the resulting shapes. He spent summer at the Ricoh Software Research Centre in Tokyo working on this problem. CAD programs make complex objects by combining many simpler objects. A lot of work needs to be done on boundary representation, which is different than the representation of the collection of 3-D objects. Snoeyink has developed an algorithm to represent any arbitrary polygon as a formula using unions and intersection where the basic shapes (primitives) are unions defined by the edges. The work will make CAD conversions from boundary representations more efficient and faster. "There are a lot of brute-force ways of doing the same thing, but they are much more complicated than necessary." Snoeyink majored in both computer science and mathematics as an undergraduate and his work now combines the two disciplines. "Doing geometry problems using computers gives you a whole new set of questions to ask about the mathematics. You can see the applications of mathematics as pictures on the screen. When you put the two together, you get a chance to say new things." ■ Boutilier takes a new look at computer logic theory In the course of our lives, we pick up vast stores of knowledge about the world around us, and much of it, we take for granted. In Craig Boutilier's research, he can take nothing for granted. Boutilier, a new member of the Department of Computer Science, is interested in supplying computers with logical representations of the knowledge they need to behave intelligently. It's a vast and complex problem which draws on his expertise in both logic and computer science. "The computer has no background knowledge, no evolution and no experience," said Boutilier. "On the other hand, we carry with us so much context and presupposition about the way the world works. For example, we know that objects stay where they are. You'd never think of telling your computer that when it leaves the room, the desk and the chair will stay there." It's impossible to impart all the knowledge people have into a computer, so the AI community is currently addressing just how much information a computer needs to behave intelligently. This information can't be presented in a black-and-white fashion if a machine is to emulate human intelligence. People regularly make assumptions, jump to conclusions, forget unimportant information and change their minds about what they believe. People are Craig Boutilier It's impossible to impart all the knowledge people have into a computer, so the AI community is currently addressing just how much information a computer needs to behave intelligently. This information can't be presented in a black-and- white fashion if a machine is to emulate human intelligence. People regularly make assumptions, jump to conclusions, forget unimportant information and change their minds about what they believe. comfortable with fuzzy concepts like "if and "maybe". Boutilier's main research interest is in laying the foundation for artificial intelligence by working on ways that computers can, in some ways, think more like people. He is developing logics to represent knowledge in a mathematical form, while keeping it as close to the English language as possible. That way, computers can assimilate the information, and people can understand and use his method of representing knowledge. Early attempts to develop artificial intelligence were quite different from today's approach. Researchers "taught" computers to make fully-logical connections: to keep track of their beliefs, as well as the reason for them; when the reason changed, the belief changed. This makes perfect sense, but is far too much to keep track of, even for today's computers. "We have to teach a computer to forget," said Boutilier. People naturally forget information that isn't useful, but a computer has no way of separating the wheat from the chaff. One could easily program it to discard the information it hasn't used for the longest. However, some of that information may be crucial on the rare occasions it is called upon. Boutilier is interested in applying his research to deductive databases that allow for a certain level of uncertainty. "Smart" databases exist today, but the type of information they can impart is limited. Boutilier would like to see databases with the ability to respond to queries that begin with, 'What if... ?' "Default reasoning can be applied. Artificial intelligence could extract the information and draw conclusions for you," said Boutilier. At first glance, many of the problems Boutilier is wrestling with appear straightforward. But he is finding that when he delves into them, their complexity approaches the human mind's. Boutilier's work forces him to think about how we think and then find ways to represent that logically — keeping in mind that not everything we do is perfectly logical. ■ Dinesh Pai Pai researches machines that move ■ Dinesh Pai, a recent addition to the Department of Computer Science, is concerned with how machines move. His research combines his knowledge of robotics and computing. Pai is working on how to program a robot with a large number of degrees of freedom. "In industry, they typically use robots with six degrees of freedom, the minimum amount required to operate in three dimensions." However, that is pretty limiting when you consider that the human arm has about 25 degrees of freedom. Currently researchers don't fully understand how to program for a large number of degrees of freedom. Pai's approach is to make programming easier by specifying constraints rather than the trajectory of the robot limbs. Pai used his approach in his postdoctoral work and successfully programmed a computer-simulated walking machine. The LISP program not only demonstrates stable walking from a full stop, but also illustrates the problems that result when you program steps that are too large (the biped get stuck in a wide straddle position) or too small (the machine falls forward). Pai has a strong interest on locomotion. He has a wide assortment of locomotive machines in his office. Most of them are little toys that move in ingenious ways when wound up: spiders that crawl, frogs that hop, small pairs of feet that walk by themselves. Many of these toys illustrate simple concepts of locomotion that can In the long run Pai's work and approaches like it will make life easier for the working robot. Ironically, the same approach also makes things easier for people working on assembly lines... There are many assembly jobs that are tedious and hazardous, or for which robots are faster and more precise, and these jobs will increase. be applied in his research. Pai is now considering building a legged walking machine to study locomotion, which could ultimately be used to traverse rough terrain. He notes that the Japanese have already built working robots that can travel along the sides of ships and clean off barnacles, reducing drag and hence, fuel consumption. Pai is also interested in the singularities of robot arms. (Singularities are the extremes of motion possible — a fully-extended arm would be one singularity.) In extreme configurations, arms lose degrees of freedom. Pai's work involves looking at the structure of singular points to make general statements about them. One application of this work is to help determine the best task locations for an industrial robot arm. "The question of where you put the assembly with respect to the robot arm is clarified," said Pai. Another project Pai is working on that will make automated assembly easier is the study of "motion diodes." These are simply items that snap together and stay put, like the cover for a cassette tape. Pai has developed an algorithm that will predict when motion will terminate (when the case is snapped shut, for example) and if it will stay that way. "We used computational geometry and were able to develop a very fast algorithm, taking friction into account," said Pai. "It will be useful for industry. It's easy for a robot to assemble equipment if everything snaps on." However, he adds that it will be some time before this work is incorporated into standard industrial design practices. In the long run, however, Pai's work and approaches like it will make life easier for the working robot. Ironically, the same approach also makes things easier for people working on assembly lines. When IBM decided to automate production of its Proprinter, the printer was completely redesigned for robot assembly. Once this was done, IBM found that while robots could do the job, people could do it much faster. However, there are many assembly jobs that are tedious and hazardous, or for which robots are faster and more precise, and these jobs will increase, especially when many of the problems Pai is working on are solved. Gosine maintains practical perspective on industrial automation projects ■ Industrial automation is the main research interest of new Mechanical Engineering Department member Ray Gosine. While to some "industrial automation" conjures up images of workers displaced from their jobs by robots, in fact, much of the work Gosine is involved in improves already-automated processes, or automates jobs that industry cannot find people with the skill or desire to do. Gosine holds the NSERC junior chair in industrial automation, which was set up to research problems in industrial automation, especially as they relate to the fish processing industry. Gosine and colleague Clarence de Silva (who holds the senior NSERC chair) have first turned their attention to some specific automation problems in fish processing. One project involves minimizing waste in salmon processing through more precise cutting. This process is already automated, but the equipment is old and employs little advanced technology. About five per cent of the salmon is wasted, yet if yields increased by just one per cent, the Canadian fish processing industry would make an additional $5 million. (For more information on this project, see CICSR Focus, Fall 1991.) Another interest of Gosine's is in motion planning for robots, especially important when they are put to work in cluttered environments. "Most approaches are offline, and everything is pre-calculated," said Gosine. What he feels is needed is a system that can rapidly generate a collision-free path of its own using a model of its environment. Another project Gosine is interested in is the improvement of fish spray-marking. A method is needed to feed the fish through a machine and spray them in a specific place on their bodies, no matter what type of fish is processed. Then, when marked fish are caught later in their lives, equipment that can recognize the pattern, even if it's worn or distorted, would be very useful. This identification would require knowledge-based vision, another of Gosine's interests. Machine vision is also necessary for "A lot of engineering work could be applied to the problems experienced by disabled people. In some areas of engineering you can do a lot technically and not accomplish much practically. Working directly with disabled people forces you to keep a practical perspective." automated herring roe grading, a project Gosine hopes to start this summer. Roe grading takes a great deal of skill, but B.C. Packers is finding it increasingly difficult to find people willing and able to do the job. Grading is very important because herring roe buyers are very particular about the quality of the product they receive. Grading is also very subjective, so an automated system would require the use of fuzzy logic and an expert knowledge base to do the job well. Gosine hopes to work with the Computer Science Department on this problem. Gosine is also interested in the development of better robotic devices for handling objects. "I want to look at multiple-degree-of-freedom joints that could conform to the shape of an object — joints that could be more gentle by determining which object is present and what is the optimal grasp. This work would not only apply in industrial automation, but in robots to help the disabled. Gosine is exploring ways to ease the use of telemanipulators for the disabled. This project, linked with the Neil Squire Foundation and Simon Fraser University, is now progressing on a small scale, but Gosine hopes to expand the program by summer and involve Shaughnessy Hospital as well. In collaboration with mechanical engineering professor Doug Romilly, Gosine is building an exoskeleton for Ray Gosine people with flail arms. People with this disability can't move their arms, though the limbs have sensation. The goal of the project is provide these people with the ability to move their arms and perform a number of natural movements we take for granted. The first step is the study of the way people with fully-functioning arms move to complete basic tasks like eating and washing. While working on his Ph.D. and postdoctoral work at Cambridge, Gosine focused on research in robots for the disabled. "It's nice to find there are similar interests here," he said. "A lot of engineering work could be applied to the problems experienced by disabled people. In some areas of engineering you can do a lot technically and not accomplish much practically. Working directly with disabled people forces you to keep a practical perspective." ■ Parallel computing winning the race ■ Hussein Alnuweiri, a new assistant professor of electrical engineering, is interested in parallel processing and implementing highly-concurrent computer systems in VLSI (Very Large Scale Integration) technology. His research application areas include signal processing, image analysis, computer vision and algorithmic graph theory. VLSI has advanced considerably in the past decade, Alnuweiri reflects. By the year 2000, it will be possible to pack about 100 million transistors onto a single chip. It will be possible to build a parallel processing system on one chip. However, the future aside, VLSI is currently a rather restricted medium compared with previous technologies. Both the number of layers in which wires can be routed and the number of input/ output terminals are limited and, with decreasing feature (transistor) size, sending signals along long wires poses many difficulties. While Alnuweiri's research considers several interacting trade-offs in application-specific VLSI designs, his major Hussein Alnuweiri goal is to resolve several communications problems associated with embedding parallel and distributed systems in VLSI. He is currently involved in developing a number of chip designs which can perform permutation routing efficiently on a VLSI chip. These designs can be used to perform data routing between processing stages. According to Alnuweiri, the main problem in designing VLSI networks for parallel computing is in routing the data between processing units. "That's usually where the bottlenecks occur," he said. "The networks I'm working on overcome many of these difficulties." Alnuweiri's design separates ... continued on page 8 Electromagnetic theory revisited by Howard Gregory Howard ■ Electromagnetic theory, synthesis and analysis are the main research interests of new electrical engineering professor Gregory Howard. According to Howard, the main problem with analysis of electromagnetic circuits is the large number of unknowns present. This makes it difficult to get meaningful results. "You need post-processing to make final results meaningful for a designer," said Howard. His Ph.D. work involved developing a set of tools to reduce the computation time for problems where unknowns numbered in the thousands. He developed a multi-level technique which allows the computer to come up with an approximate solution while reducing computation by an order of magnitude. Howard is looking at new techniques to analyze electromagnetic circuits. Current circuit theory entails the use of block component modelling, which accounts for each individual block fairly accurately, but doesn't account for the interaction of that block with its environment. To incorporate all of the interactions between complex electromagnetic systems is a feat too large for even powerful modern computers. Howard worked on a new approach for both his Masters and Ph.D. theses, and is continuing with this research. His method of circuit analysis allows for the inclusion of the electromagnetic coupling. His approach emphasizes integral equation methods and their use in a new integrated form of circuit theory. Howard points out another drawback to traditional methods of electromagnetic ... continued on page 8 Passing notes Vinod Modi wins Brouwer Award Parallel computing ... continued from page 7 Electromagnetic theory ... continued from page 7 Mechanical Engineering professor Vinod Modi is the first Canadian in history to receive the Dirk Brouwer Award, the most prestigious offered by the American Astronautical Society. Modi's research in aerospace engineering focuses on the dynamics and control of large space structures, including the next generation of communications satellites, space shuttle-based experiments, the proposed space station Freedom and mobile remote manipulator systems. ■ Ribbon-cutting ceremony held ■ A ribbon-cutting ceremony was held in December to officially celebrate construction of the new CICSR building. The $18 million building will bring together the departments of Electrical and Mechanical Engineering, as well as Computer Science. All three departments have grown considerably in recent years. The building will also be the new home of CICSR, and will enable the Centre to better facilitate interdisciplinary work among its members. UBC president David Strangway, B.C. Tel chairman Gordon MacFarlane, CICSR director James Varah and Tourism and Culture minister Darlene Marzari were among those present at the ceremony. ■ networks into chip areas that do processing, and chip areas that do the routing. Alnuweiri started his research in his Saudi Arabia. He also spent five years in the U.S. at the University of Southern California where he earned his Ph.D. in computer engineering. A prototype chip is now being produced based on his design which can perform permutations on 256 inputs simultaneously. Alnuweiri is also working on designing algorithms for reconfigurable networks of processors. These are networks which can change their topology dynamically throughout a computation. Their application would be in areas where very fast solutions are required, such as image processing and robot vision. But the work is still in the research phase and has a way to go before it can be applied. The applied nature of the discipline is what attracted Alnuweiri to electrical engineering. His earlier interest was physics, but he says, "I like design problems and to see a product out of what I study." His chosen field is one of the fastest- growing engineering fields. "There are a lot of emerging technologies and all require a substantial amount of research," said Alnuweiri. He feels, like many others, that parallel computers are the way of the future. In fact, several parallel computers have emerged in the last few years, with others soon to follow from most of the companies that now produce mainframes or "traditional" supercomputers. "Traditional supercomputers and mainframes are losing the battle. Massively parallel computers will dominate the future of supercomputing." However, there is still a lot of work to be done before these computers of the future become widely used. Alnuweiri is doing a part of that work. ■ circuit analysis, which his approach could help overcome: "Present techniques are limited by the fact that they use linear operation techniques. A new method is needed to analyze non-linear materials." Another strong interest which Howard is pursuing could save electromagnetic researchers a lot of redundant work in the future. "When doing research in numerical electromagnetics, new researchers start almost from scratch because the way the code was previously written, it is not re-usable," said Howard. He would like to see this change through wider use of new software tools and object-oriented languages so code can be extended for new applications without researchers having to re-invent the whole underlying structure. This approach would also make implementation of new methods and techniques, such as the one Howard is working on, easier to implement within existing work. "It would make it easier for researchers to collaborate if code writers used the same design methodology," said Howard. Howard is interested in collaborating with the Computer Science Department to solve another fundamental difficulty in electromagnetic circuit research. When dealing with electromagnetics, the amount of information that needs to be processed is so large, a very friendly user interface is required for people to process that information. Howard hopes to collaborate on the development of an interface which will allow his analysis tools to be used by industry in a reasonable, rather than an expert, fashion. Electromagnetic circuits are used in satellite communications, radar, modulation circuits in fibreoptic technology, and many other areas. ■ CICSR: The UBC Centre for Integrated Computer Systems Research (CICSR) is an interdepartmental research organization made up of computer- related research faculty members in the Departments of Computer Science, Electrical Engineering and Mechanical Engineering. Currently there are more than 60 CICSR researchers which direct over 100 graduate students and collaborate with dozens of industrial firms in areas such as robotics, artificial intelligence, communications, VLSI design and industrial automation. CISCR FOCUS, is published twice a year. CREDITS: EDITOR: Leslie Ellis DESIGN: Rob Bishop Office: 2053 - 2324 Main Mall, Vancouver, B.C. V6T 1Z4 Tel: (604) 822-6894, fax: (604) 822-9013 Contact: Gale Ross THE UNIVERSITY OF BRITISH COLUMBIA