Variables Bounding Based Retiming Algorithm

Retiming is a technique for optimizing sequential circuits.In this paper,we discuss this problem and propose an improved retiming algorithm based on varialbes bounding.Through the computation of the lower and upper bounds on variables,the algorithm can significantly reduce the number of constratints and speed up the execution of retiming.Furthermore,the elements of matrixes D and W are computed in a demand-driven way,which can reduce the capacity of memory,It is shown through the experimental results on ISCAS89 benchmarks that our algorithm is very effective for large-scale seuqential circuits.     

RHiNET-2/SW: a high-throughput, compact network-switch using 8.8-gbit/s optical interconnection

We have developed a high-throughput, compact network switch (the RHiNET-2/SW) for a distributed parallel computing system. Eight pairs of 800-Mbit/s×12-channel optical interconnection modules and a CMOS ASIC switch are integrated on a compact circuit board. To realize high-throughput (64 Gbit/s) and low-latency network, the SW-LSI has a customized high-speed LVDS I/O interface, and a high-speed internal SRAM memory in a 784-pin BGA one-chip package. We have also developed device implementation technologies to overcome the electrical problems (loss and crosstalk) caused by such high integration. The RHiNET-2/SW system enables high-performance parallel processing in a distributed computing environment. Shinji Nishimura: He is a researcher in the Department of Network System at the Central Research Laboratory, Hitachi Ltd., at Tokyo. He obtained his bachelors degree in Electronics Engineering from the University of Tokyo in 1989, and his M.E. from the University of Tokyo in 1991. He joined a member of the Optical Interconnection Hitachi Laboratory from 1992. His research interests are in hardware technology for the optical interconnection technologies in the computer and communication systems. Katsuyoshi Harasawa: He is a Senior Enginner of Hitachi Communication Systems Inc. He obtained his bachelors degree in Electrical Engineering from Tokyo Denki University. He is a chief of development of the devices and systems for the optical telecommunication. He was engaged in Development of Optical Reciever and Transmitter module. He joined RWCP project from 1997. His research interests are in hardward technology for optical interconnection in distributed parallel computing system (RHiNET). Nobuhiro Matsudaira: He is a engineer in the Hitachi Communication Systems, Inc. He obtained his bachelors degree in Mercantile Marine Engineering from the Kobe University of Mercantile Marine in 1986. He was engaged in Development of Optical Reciever and Transmitter module at 2.4 Gbit/s to 10Gbit/s. He joined RWCP project from 1998. His reserch interests are in hardware technology for the optical interconnection technology in the computer and communication systems. Shigeto Akutsu: He is a staff in Hitachi Communication Systems Inc. He obtained his bachelors degree in Electronics from Kanagawa University, Japan in 1998. His research interests are hardware technology for the optical interconnection technology in the computer and communication systems. Tomohiro Kudoh, Ph.D.: He received Ph.D. degree from Keio University, Japan in 1992. He has been chief of the parallel and distributed architecture laboratory, Real World Computing Partnership since 1997. His research interests include the area of parallel processing and network for high performance computing. Hiroaki Nishi: He received B.E., M.E. from Keio University, Japan, in 1994, 1996, respectively. He joined Parallel & Distributed Architecture Laboratory, Real World Computing Partnership in 1999. He is currently working on his Ph.D. His research interests include area of interconnection networks. Hideharu Amano, Ph.D.: He received Ph.D. degree from Keio University, Japan in 1986. He is now an Associate Professor in the Department of Information and Computer Science, Keio University. His research interests include the area of parallel processing and reconfigurable computing.     

A grid-oriented genetic algorithm framework for bioinformatics

In this paper, we propose a framework for enabling for researchers of genetic algorithms (GAs) to easily develop GAs running on the Grid, named “Grid-Oriented Genetic algorithms (GOGAs)”, and actually “Gridify” a GA for estimating genetic networks, which is being developed by our group, in order to examine the usability of the proposed GOGA framework. We also evaluate the scalability of the “Gridified” GA by applying it to a five-gene genetic network estimation problem on a grid testbed constructed in our laboratory. Hiroaki Imade: He received his B.S. degree in the department of engineering from The University of Tokushima, Tokushima, Japan, in 2001. He received the M.S. degree in information systems from the Graduate School of Engineering, The University of Tokushima in 2003. He is now in Doctoral Course of Graduate School of Engineering, The University of Tokushima. His research interests include evolutionary computation. He currently researches a framework to easily develop the GOGA models which efficiently work on the grid. Ryohei Morishita: He received his B.S. degree in the department of engineering from The University of Tokushima, Tokushima, Japan, in 2002. He is now in Master Course of Graduate School of Engineering, The University of Tokushima, Tokushima. His research interest is evolutionary computation. He currently researches GA for estimating genetic networks. Isao Ono, Ph.D.: He received his B.S. degree from the Department of Control Engineering, Tokyo Institute of Technology, Tokyo, Japan, in 1994. He received Ph.D. of Engineering at Tokyo Institute of Technology, Yokohama, in 1997. He worked as a Research Fellow from 1997 to 1998 at Tokyo Institute of Technology, and at University of Tokushima, Tokushima, Japan, in 1998. He worked as a Lecturer from 1998 to 2001 at University of Tokushima. He is now Associate Professor at University of Tokushima. His research interests include evolutionary computation, scheduling, function optimization, optical design and bioinformatics. He is a member of JSAI, SCI, IPSJ and OSJ. Norihiko Ono, Ph.D.: He received his B.S. M.S. and Ph.D. of Engineering in 1979, 1981 and 1986, respectively, from Tokyo Institute of Technology. From 1986 to 1989, he was Research Associate at Faculty of Engineering, Hiroshima University. From 1989 to 1997, he was an associate professor at Faculty of Engineering, University of Tokushima. He was promoted to Professor in the Department of Information Science and Intelligent Systems in 1997. His current research interests include learning in multi-agent systems, autonomous agents, reinforcement learning and evolutionary algorithms. Masahiro Okamoto, Ph.D.: He is currently Professor of Graduate School of Systems Life Sciences, Kyushu University, Japan. He received his Ph.D. degree in Biochemistry from Kyushu University in 1981. His major research field is nonlinear numerical optimization and systems biology. His current research interests cover system identification of nonlinear complex systems by using evolutional computer algorithm of optimization, development of integrated simulator for analyzing nonlinear dynamics and design of fault-tolerant routing network by mimicking metabolic control system. He has more than 90 peer reviewed publications.     

Calculating accumulations

Theaccumulation strategy consists of generalizing a function over an algebraic data structure by inclusion of an extra parameter, anaccumulating parameter, for reusing and propagating intermediate results. However, there remain two major difficulties in this accumulation strategy. One is to determinewhere andwhen to generalize the original function. The other, surprisingly not yet receiving its worthy consideration, is how to manipulate accumulations. To overcome these difficulties, we propose to formulate accumulations ashigher order catamorphisms, and provide several general transformation rules for calculating accumulations (i.e., finding and manipulating accumulations) bycalculation-based (rather than a search-based) program transformation methods. Some examples are given for illustration. Zhenjiang Hu, Dr.Eng.: He is an Assistant Professor in Information Engineering at the University of Tokyo. He received his BS and MS in Computer Science from Shanghai Jiao Tong University in 1988 and 1990 respectively, and his Dr. Eng. degree in Information Engineering from the University of Tokyo in 1996. His current research concerns programming languages, functional programming, program transformation, and parallel processing. Hideya Iwasaki, Dr.Eng.: He is an Associate Professor in Information Engineering at the University of Tokyo. He received the M.E. degree in 1985, the Dr. Eng. degree in 1988 from the University of Tokyo. His research interests are list processing languages, functional languages, parallel processing, and constructive algorithmics. Masato Takeichi, Dr.Eng.: He is Professor in Mathematical Engineering and Information Engineering at the University of Tokyo since 1993. After graduation from the University of Tokyo, he joined the faculty at the University of Electro-Communications in Tokyo before he went back to work at the University of Tokyo in 1987. His research concerns the design and implementation of functional programming languages, and calculational program transformation systems.     

Relational semantics for locally nondeterministic programs

Introducing nondeterministic operators in a conventional deterministic language gives rise to various semantic difficulties. One of the problems is that there has been no semantic domain that is wholly satisfactory for denoting nondeterministic programs. In this paper, we propose an approach based on relational algebra. We divide the semantics of a nondeterministic program into two parts. The first part concerns the angelic aspect of programs and the second part concerns the demonic aspect of programs. Because each semantic function used in these parts is monotonic with respect to an ordering on relations, the existence of the fixed points of recursively defined nondeterministic programs is ensured. Liangwei Xu: His research interests are computational model, program transformation and derivation methodology. He received the B. E. degree from Shanghai Jiao Tong University in 1982 and the M.E. degree from University of Tokyo in 1992. He currently joins Mathematical Systems Institute Inc. Masato Takeichi, Dr. Eng.: He is a Professor of Department of Mathematical Engineering. Graduate School of Engineering, University of Tokyo. His research interests are functional programming, language implementation and constructive algorithmics. Hideya Iwasaki, Dr. Eng.: He is an Associate Professor of Faculty of Technology, Tokyo University of Agriculture and Technology. He received the M.E. degree in 1985, the Dr. Eng. degree in 1988 from University of Tokyo. His research interests are list processing languages, functional languages, parallel processing, and constructive algorithmics.     

Open Mobile Alliance (OMA) security layer: Architecture, implementation and performance evaluation of the integrity unit

Security has become a very critical issue in the provision of mobile services. The Open Mobile Alliance (OMA) has specified a powerful security layer, the WTLS. In this paper, a VLSI architecture for the implementation of the WTLS integrity unit is proposed. The proposed architecture is reconfigurable in the sense that operates in three different modes: as Keyed-Hash Authentication Code (HMAC), as SHA-1 and MD5 hash functions, according to WTLS specifications. This multi-mode operation is achieved due to the reconfigurable applied design technique in the proposed architecture, which keeps the allocated area resources at a minimized level. The proposed architecture achieves high speed performance, due to the pipeline designed architecture. Especially, SHA-1 operation achieved throughput is equal to 1,7 Gbps, while MD5 operation mode bit rate is equal to 2,1 Gbps. The proposed architecture has been integrated by using VHDL and has been synthesized placed and routed in an FPGA device. Comparisons with related hash functions implementations have been done in terms of throughput, operating frequency, allocated area and Area-Delay product. The achieved performance of the SHA-1 operation mode is better at about 14–42 times compared with the other conventional works. In addition, MD5 performance is superior to the other works at about 6–18 times, in all of the cases. The proposed Integrity Unit is a very trustful and powerful solution for the WTLS layer. In addition, it can be integrated in security systems which are used for the implementation networks for wireless protocols, with special needs of integrity in data transmission. Nicolas Sklavos, Ph.D.: He is a Ph.D. Researcher with the Electrical and Computer Engineering Department, University of Patras, Greece. His interests include computer security, new encryption algorithms design, wireless communications and reconfigurable computing. He received an award for his Ph.D. thesis on “VLSI Designs of Wireless Communications Security Systems” from IFIP VLSI SOC 2003. He is a referee of International Journals and Conferences. He is a member of the IEEE, the Technical Chamber of Greece and the Greek Electrical Engineering Society. He has authored or co-authored up to 50 scientific articles in the areas of his research. Paris Kitsos, Ph.D.: He is currently pursuing his Ph.D. in the Department of Electrical and computer Engineering, University of Patras, Greece. He received the B.S. in Physics from the University of Patras in 1999. His research interests include VLSI design, hardware implementations of cryptography algorithms, security protocols for wireless communication systems and Galois field arithmetic implementations. He has published many technical papers in the areas of his research. Epaminondas Alexopoulos: He is a student of the Department of Electrical and Computer Engineering, University of Patras, Greece. His research includes hardware implementations, mobile computing and security. He has published papers in the areas of his research. Odysseas Koufopavlou, Ph.D.: He received the Diploma of Electrical Engineering in 1983 and the Ph.D. degree in Electrical Engineering in 1990, both from University of Patras, Greece. From 1990 to 1994 he was at the IBM Thomas J. Watson Research Center, Yorktown Heights, NY, USA. He is currently an Associate Professor at the Department of Electrical and Computer Engineering, University of Patras. His research interests include VLSI, low power design, VLSI crypto systems and high performance communication subsystems architecture and implementation. He has published more than 100 technical papers and received patents and inventions in these areas.     

A quantum algorithm using NMR computers to break secret-key cryptosystems

In this paper, we discuss quantum algorithms that, for a given plaintextm _o and a given ciphertextc _o, will find a secret key,k _o, satisfyingc _o=E(k _o,m _o), where an encryption algorithm,E, is publicly available. We propose a new algorithm suitable for an NMR (Nuclear Magnetic Resonance) computer based on the technique used to solve the counting problem. The complexity of, our algorithm decreases as the measurement accuracy of the NMR computer increases. We discuss the possibility that the proposed algorithm is superior to Grover’s algorithm based on initial experimental results. Kazuo Ohta, Dr.S.: He is Professor of Faculty of Electro-Communications at the University of Electro-Communications, Japan. He received B.S., M.S., and Dr. S. degrees from Waseda University, Japan, in 1977, 1979, and 1990, respectively. He was researcher of NTT (Nippon Telegraph and Telephone Corporation) from 1979 to 2001, and was visiting scientist of Laboratory for Computer Science e of MIT (Massachusetts Institute of Technology) in 1991–1992 and visiting Professor of Applied Mathematics of MIT in 2000. He is presently engaged in research on Information Security, and theoretical computer science. Dr. Ohta is a member of IEEE, the International Association for Cryptologic Research, the Institute of Electronics, Information and Communication Engineers and the Information Processing Society of Japan. Tetsuro Nishino,: He received the B.S., M.S. and, D.Sc. degrees in mathematics from Waseda University, in 1982, 1984, and 1991 respectively. From 1984 to 1987, he joined Tokyo Research Laboratory, IBM Japan. From 1987 to 1992, he was a Research Associate of Tokyo Denki University, and from 1992 to 1994, he was an Associate Professor of Japan Advanced Institute of Science and Technology, Hokuriku. He is presently an Associate Professor in the Department of Communications and Systems Engineering, the University of Electro-Communications. His main interests are circuit complexity theory, computational learning theory and quantum complexity theory. Seiya Okubo,: He received the B.Eng. and M.Eng. degrees from the University of Electro-Communications in 2000 and 2002, respectively. He is a student in Graduate School of Electro-Communications, the University of Electro-Communications. His research interests include quantum complexity theory and cryptography. Noboru Kunihiro, Ph.D.: He is Assistant Professor of the University of Electro-Communications. He received his B. E., M. E. and Ph. D. in mathematical engineering and information physics from the University of Tokyo in 1994, 1996 and 2001, respectively. He had been engaged in the research on cryptography and information security at NTT Communication Science Laboratories from 1996 to 2002. Since 2002, he has been working for Department of Information and Communication Engineering of the University of Elector-Communications. His research interests include cryptography, information security and quantum computations. He was awarded the SCIS’97 paper prize.     

Feasibility Study on an Excavation-Type Demining Robot

In this study, we propose a design of an excavation-type demining robot that rids a farm of mines efficiently and safely. In the dangerous area, the robot automatically takes in soil in which mines are laid. The entire soil surface, including mines, is crushed, separated and discharged. Therefore, the demining ratio is high; also, the soil becomes clean and cultivated. The robot has a large bucket on its front. The robot moves forward, maintaining the height of the bucket from the ground by the vertical motion of the bucket and the forward motion of the body. The possibility of that motion is confirmed through simulations and experiments. The crush process and the proper depth of the excavation are also discussed.Yoshikazu Mori has a Ph.D. degree in information science from Tohoku University (Japan). he is a research associate in the Department of Precision Engineering, Tokyo Metropolitan University. His research focuses on a welfare robot, and won the 2004 Presentation Award from The Japan Society of Mechanical Engineers, Robotics and Mechatronics Division. He is also interested in an autonomous agent that lives with the human.Kazuhiro Takayama has a Masters Degree from the Department of precision Engineering at Tokyo Metropolitan University. He is an acoustic engineer of Honda R&D Co., Ltd., Tochigi R&D Center.Takeshi Adachi has a Bachelors Degree from the Department of Precision Engineering at Tokyo Metropolitan University. Currently he is studying a bipedal robot with jack legs for carrying a heavy load.Shintaro Omote has a Bachelors Degree from the Department of Precision Engineering at Tokyo Metropolitan University. He is currently studying a partner robot and trying to let it recognize human mental characters.Tatsuya Nakamura received the B.E. degree in aeronautics, the M.S. degree in physics and D. E. degree in robotics in 1965, 1967 and 1983, respectively, from Nagoya University. He joined the Mechanical Engineering Laboratory, AIST, MITI in 1967. He was engaged in advanced robotics project there. In 1992, he became a professor at Mie University. Since 1997, he has been a Professor in the Department of Precision Engineering, Tokyo Metropolitan University. His research topics include micromanipulation using magnetic technologies and intelligent welfare robots.     

An Efficient Support Vector Machine Learning Method with Second-Order Cone Programming for Large-Scale Problems

In this paper we propose a new fast learning algorithm for the support vector machine (SVM). The proposed method is based on the technique of second-order cone programming. We reformulate the SVM's quadratic programming problem into the second-order cone programming problem. The proposed method needs to decompose the kernel matrix of SVM's optimization problem, and the decomposed matrix is used in the new optimization problem. Since the kernel matrix is positive semidefinite, the dimension of the decomposed matrix can be reduced by decomposition (factorization) methods. The performance of the proposed method depends on the dimension of the decomposed matrix. Experimental results show that the proposed method is much faster than the quadratic programming solver LOQO if the dimension of the decomposed matrix is small enough compared to that of the kernel matrix. The proposed method is also faster than the method proposed in (S. Fine and K. Scheinberg, 2001) for both low-rank and full-rank kernel matrices. The working set selection is an important issue in the SVM decomposition (chunking) method. We also modify Hsu and Lin's working set selection approach to deal with large working set. The proposed approach leads to faster convergence. Rameswar Debnath is a Ph.D candidate at the University of Electro-Communications, Tokyo, Japan and also a lecturer of the Computer Science & Engineering Discipline at Khulna University, Bangladesh. He received the bachelor's degree in computer science and engineering from Khulna University in 1997 and masters of engineering degree in communication and systems from the University of Electro-Communications in 2002. His research interests include support vector machines, artificial neural networks, pattern recognition, and image processing. Masakazu Muramatsu is an associate professor of the Department of Computer Science at the University of Electro-Communications, Japan. He received a bachelor's degree from the University of Tokyo in 1989, master's degree in engineering from University of Tokyo in 1991, and Ph.D from the Graduate University for Advanced Studies in 1994. He was an assistant professor of the Department of Mechanical Engineering at Sophia University from 1994 to 2000, when he moved to the current university. His research interests include mathematical programming, second-order cone programming and its application to machine learning. Haruhisa Takahashi was born in Shizuoka Prefecture Japan, on March 31, 1952. He graduated from the University of Electro-Communications. He received the Dr Eng. degree from Osaka University. He was a faculty member of the Department of Computer Science and Engineering at Toyohashi University of Technology from 1980 to 1986. Since 1986, he has been with the University of Electro-Communications where he is currently professor of the Department of Information and Communication Engineering. He was previously engaged in the fields of nonlinear network theory, queueing theory and performance evaluation of communication systems. His current research includes learning machines, artificial neural networks, and cognitive science.     

An efficient underwater coverage method for multi-AUV with sea current disturbances

This paper presents an online coverage method for the exploration of unknown oceanic terrains using multiple autonomous underwater vehicles (AUVs). Working from the concept of planar algorithm developed by Hert, this study attempts to develop an improved method. Instead of theoretical research, it focuses on the practical aspects of exploration by considering the equations of motion for AUVs that are actually used in oceanic exploration as well as on the characteristics of complex oceanic topography and other realistic variables, such as sea current. These elements are used to calculate cross track error (CTE) and path width for AUV movement. The validity of the improved algorithm for terrain coverage is first verified mathematically and then by a simulation of the real underwater environment that analyzes the path length and time taken for the coverage as well as the missed areas, which is the key element of efficiency. In order to apply the improved method to the multi-AUV operation, each AUV was assigned a covering or a scanning role by means of a dynamic role-changing mechanism. The results showed that the multi-AUV operation has an advantage over a single-AUV operation in many ways. The method proposed in this study will be useful not only for commercial applications but also for mine counter-measures (MCMs) and rapid environmental assessments (REAs) as part of naval military operations as well. We also believe that it will be ideal for use in variable oceanic environment, particularly in shallow water terrains. For the purposes of this study, we assume that the communication between AUVs is problem-free. Recommended by Editorial Board member Sooyong Lee under the direction of Editor Jae-Bok Song. This work was supported in part by MOCIE Industrial Technology Development Program, the ASRI, and BK21 Information Technology at Seoul National University. Yeun-Soo Jung received the Ph.D. degree in Electrical Engineering from Seoul National University in 2008. His research interests include autonomous underwater vehicles and multi-agent control. Kong-Woo Lee received the M.S. degree in Electrical Engineering from Seoul National University in 2007. His research interests include multi-agent control, autonomous mobile robot navigation and SLAM. Seong-Yong Lee received the M.S. degree in Electrical Engineering from Seoul National University in 2007. His research interests include intelligent robots, embedded systems, operating systems, and multi-agent control. Myoung Hwan Choi received the Ph.D. degree in Control and Instrumentation Engineering from Seoul National University in 1992. His research interests include ultrasonic Imaging, biomedical signal processing and biomedical imaging. Beom-Hee Lee received the Ph.D. degree in Computer, Information & Control Engineering from University of Michigan in 1985. His research interests include multi-agent system coordination, control, and application.     

Oscillation amplitude-controlled resonant accelerometer design using a reference tracking automatic gain control

In this paper, it is presented a novel approach for the self-sustained resonant accelerometer design, which takes advantages of an automatic gain control in achieving stabilized oscillation dynamics. Through the proposed system modeling and loop transformation, the feedback controller is designed to maintain uniform oscillation amplitude under dynamic input accelerations. The fabrication process for the mechanical structure is illustrated in brief. Computer simulation and experimental results show the feasibility of the proposed accelerometer design, which is applicable to a control grade inertial sense system. Recommended by Editorial Board member Dong Hwan Kim under the direction of Editor Hyun Seok Yang. This work was supported by the BK21 Project ST·IT Fusion Engineering program in Konkuk University, 2008. This work was supported by the Korea Foundation for International Cooperation of Science & Technology(KICOS) through a grant provided by the Korean Ministry of Education, Science & Technology(MEST) in 2008 (No. K20601000001). Authors also thank to Dr. B.-L. Lee for the help in structure manufacturing. Sangkyung Sung is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the M.S and Ph.D. degrees in Electrical Engineering from Seoul National University in 1998 and 2003, respectively. His research interests include inertial sensors, avionic system hardware, navigation filter, and intelligent vehicle systems. Chang-Joo Kim is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the Ph.D. degree in Aeronautical Engineering from Seoul National University in 1991. His research interests include nonlinear optimal control, helicopter flight mechanics, and helicopter system design. Young Jae Lee is a Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the Ph.D. degree in Aerospace Engineering from the University of Texas at Austin in 1990. His research interests include integrity monitoring of GNSS signal, GBAS, RTK, attitude determination, orbit determination, and GNSS related engineering problems. Jungkeun Park is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University. Dr. Park received the Ph.D. in Electrical Engineering and Computer Science from the Seoul National University in 2004. His current research interests include embedded real-time systems design, real-time operating systems, distributed embedded real-time systems and multimedia systems. Joon Goo Park is an Assistant Professor of the Department of Electronic Engineering at Gyung Book National University, Korea. He received the Ph.D. degree in School of Electrical Engineering from Seoul National University in 2001. His research interests include mobile navigation and adaptive control.     

Public opinion channel for communities in the information age

In this paper, we propose as a new challenge a public opinion channel which can provide a novel communication medium for sharing and exchanging opinions in a community. Rather than simply developing a means of investigating public opinion, we aim at an active medium that can facilitate mutual understanding, discussion, and public opinion formation. First, we elaborate the idea of public opinion channels and identify key issues. Second, we describe our first step towards the goal using the talking virtualized egos metaphor. Finally, we discuss a research agenda towards the goal. Toyoaki Nishida, Dr.Eng.: He is a professor of Department of Information and Communication Engineering, School of Engineering, The University of Tokyo. He received the B.E., the M.E., and the Doctor of Engineering degrees from Kyoto University in 1977, 1979, and 1984 respectively. His research centers on artificial intelligence in general. His current research focuses on community computing and support systems, including knowledge sharing, knowledge media, and agent technology. He has been leading the Breakthrough 21 Nishida Project, sponsored by Ministry of Posts and Telecommunications, Japan, aiming at understanding and assisting networked communities. Since 1997, he is a trustee for JSAI (Japanese Society for Artificial Intelligence), and serves as the program chair of 1999 JSAI Annual Convention. He is an area editor (intelligent systems) of New Generation Computing and an editor of Autonomous Agents and Multiagent Systems. Nobuhiko Fujihara, Ph.D.: He is a fellow of Breakthrough 21 Nishida project, Communications Research Laboratory sponsored by Ministry of Posts and Telecommunications, Japan. He received the B.E., the M.E., and the Ph.D. in Human Sciences degrees from Osaka University in 1992, 1994, and 1998 respectively. He has a cognitive psychological background. His current research focuses on: (1) cognitive psychological analysis of human behavior in a networked community, (2) investigation of information comprehension process, (3) assessment and proposition of communication tools in networking society. Shintaro Azechi: He is a fellow of Breakthrough 21 Nishida project, Communications Research Laboratory sponsored by Ministry of Posts and Telecommunications, Japan. He received the B.E. and the M.E. of Human Sciences degrees from Osaka University in 1994 and 1996 respectively. He is a Doctoral Candidate of Graduate School of Human Sciences, Osaka University. His current researches focus on (1) human behavior in networking community (2) social infomation process in human mind (3) development of acessment technique for communication tools in networkingsociety. His approach is from social psychological view. Kaoru Sumi, Dr.Eng.: She is a Researcher of Breakthrough 21 Nishida Project. She received her Bachelor of Science at School of Physics, Science University of Tokyo. She received her Master of Systems Management at Graduate School of Systems Management, The university of Tsukuba. She received her Doctor of engineering at Graduate School of Engineering, The University of Tokyo. Her research interests include knowledge-based systems, creativity supporting systems, and their applications for facilitating human collaboration. She is a member of the Information Processing Society of Japan (IPSJ), the Japanese Society for Artificial Intelligence (JSAI). Hiroyuki Yano, Dr.Eng.: He is a senior research official of Kansai Advanced Research Center, Communications Research Laboratory, Ministry of Posts and Telecommunications. He received the B.E., the M.E., and the Doctor of Engineering degrees from Tohoku University in 1986, 1988, and 1993 respectively. His interests of research include cognitive mechanism of human communications. His current research focuses on discourse structure, human interface, and dialogue systems for human natural dialogues. He is a member of the Japanese Society for Artificial Intelligence, the Association for Natural Language Processing, and the Japanese Cognitive Science Society. Takashi Hirata: He is a doctor course student in Graduate School of Information Scienc at Nara Institute of Science and Technology (NAIST). He received a master of engineering from NAIST in 1998. His research interest is knowledge media and knowledge sharing. He is a member of Information Processing Society of Japan (IPSJ), Japan Association for Artificial Intelligence (JSAI) and The Institute of Systems, Control and Information Engineers (ISCIE).     

A New Approach to Humanitarian Demining

Landmines can deprive whole areas of valuable resources, and continue to kill and cause injuries years after the end of armed conflicts. Armored vehicles are used for mine clearance, but with limited reliability. The final inspection of minefields is still performed by human deminers exposed to potentially fatal accidents. The aim of this research is to introduce automation as a way to improve the final level of humanitarian demining. This paper addresses mobility and manipulation, while sensing, communication and visualization shall be discussed in detail in a subsequent paper. After analyzing the merits and limitations of previous works, a new approach to tele-operated demining is considered, using off-road buggies equipped with combustion engines, and taking into account actual field requirements. Control of the automated buggies on rough terrain is also discussed, as well as the development of a new weight-balanced manipulator for landmine clearance operations.Paulo Debenest received the B. Eng. degree in mechanical engineering (major in automation and systems) from Polytechnic School of the University of São Paulo (EPUSP), Brazil, in 1998, and the M. Eng. degree in mechanical and aerospace engineering from Tokyo Institute of Technology (Tokyo Tech), Japan, in 2002. He is currently working toward the Ph.D. degree in mechanical science engineering at Tokyo Tech and member of IEEE. His current research activities include development of demining robots and mechanical design of machines for field applications.Edwardo F. Fukushima is an assistant professor in the Department of Mechanical and Aerospace Engineering at Tokyo Institute of Technology (Tokyo Tech). He received the B. Eng. degree in electric engineering (major in electronics and telecommunications) from Federal Center of Technological Education of Paraná (CEFET-PR), Brazil, in 1989, and M. Eng. degree in mechanical science engineering from Tokyo Tech in 1993. In 1994 he became a research associate in the same institute. During Sept.–Dec. 2001 he has been a Visiting Researcher at Stanford University, and during Aug.–Sept. 2004 Visiting Scientist at University of Zurich. He is also member of RSJ. His current research activities include development of demining robots, design of controllers for intelligent robots, and development of new brushless motors and drives.Yuki Tojo is a masters course student in the Department of Mechanical and Aerospace Engineering at Tokyo Institute of Technology (Tokyo Tech). He received the B. Eng. degree in mechanical and aerospace engineering from Tokyo Tech in 2003. His research interests include design and control of weight-compensated manipulator on mobile platform. He is also member of RSJ.Shigeo Hirose was born in Tokyo in 1947. He received his B.Eng. Degree with First Class Honors in Mechanical Engineering from Yokohama National University in 1971, and his M. Eng. and Ph.D. Eng. Degrees in Control Engineering from Tokyo Institute of Technology in 1973 and 1976, respectively. From 1976 to 1979 he was a Research Associate, and from 1979 to 1992 an Associate Professor. Since 1992 he has been a Professor in the Department of Mechanical and Aerospace Engineering at the Tokyo Institute of Technology. Since 2002, he has been Honorary Professor in Shengyang Institute of Technology, the Chinese Academy of Sciences. Fellow of JSME and IEEE. He is engaged in creative design of robotic systems. Prof. Hirose has been awarded more than twenty prizes.     

Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing

The single linkage method is a fundamental agglomerative hierarchical clustering algorithm. This algorithm regards each point as a single cluster initially. In the agglomeration step, it connects a pair of clusters such that the distance between the nearest members is the shortest. This step is repeated until only one cluster remains. The single linkage method can efficiently detect clusters in arbitrary shapes. However, a drawback of this method is a large time complexity of O(n ²), where n represents the number of data points. This time complexity makes this method infeasible for large data. This paper proposes a fast approximation algorithm for the single linkage method. Our algorithm reduces the time complexity to O(nB) by rapidly finding the near clusters to be connected by Locality-Sensitive Hashing, a fast algorithm for the approximate nearest neighbor search. Here, B represents the maximum number of points going into a single hash entry and it practically diminishes to a small constant as compared to n for sufficiently large hash tables. Experimentally, we show that (1) the proposed algorithm obtains clustering results similar to those obtained by the single linkage method and (2) it runs faster for large data than the single linkage method. Hisashi Koga received the M.S. and Ph.D. degree in information science in 1995 and 2002, respectively, from the University of Tokyo. From 1995 to 2003, he worked as a researcher at Fujitsu Laboratories Ltd. Since 2003, he has been a faculty member at the University of Electro-Communications, Tokyo (Japan). Currently, he is an associate professor at the Graduate School of Information Systems, University of Electro-Communications. His research interest includes various kinds of algorithms such as clustering algorithms, on-line algorithms, and algorithms in network communications. Tetsuo Ishibashi received the M.E. degree in information systems design from the Graduate School of Information Systems at the University of Electro-Communications in 2004. Presently, he is a system engineer at Fujitsu Broad Solution & Consulting Inc. Toshinori Watanabe received the B.E. degree in aeronautical engineering in 1971 and the D.E. degree in 1985, both from the University of Tokyo. In 1971, he worked at Hitachi as a researcher in the field of information systems design. His experience includes demand forecasting, inventory and production management, VLSI design automation, knowledge-based nonlinear optimizer, and a case-based evolutionary learning system nicknamed TAMPOPO. He also engaged in FGCS (Fifth Generation Computer System) project of Japan and developed a new hierarchical message-passing parallel cooperative VLSI layout problem solver that ran on PIM (Parallel Inference Machine) in 1991. Since 1992, he has been a professor at the Graduate School of Information Systems, University of Electro-Communications, Tokyo, Japan. His areas of interest include media analysis, learning intelligence, and the semantics of information systems. He is a member of the IEEE.     

Trends of internet auctions and agent-mediated Web commerce

Electronic Commerce (EC) is a promising field for applying agent and Artificial Intelligence technologies. In this article, we give an overview of the trends of Internet auctions and agent-mediated Web commerce. We describe the theoretical backgrounds of auction protocols and introduce several Internet auction sites. Furthermore, we describe various activities aimed toward utilizing agent technologies in EC and the trends in standardization efforts on agent technologies. Makoto Yokoo, Ph.D.: He received the B.E. and M.E. degrees in electrical engineering, in 1984 and 1986, respectively, from the University of Tokyo, Japan, and the Ph.D. degree in information and communication engineering in 1995 from the University of Tokyo, Japan. He is currently a distinguished technical member in NTT Communication Science Laboratories, Kyoto, Japan. He was a visiting research scientist at the Department of Electrical Engineering and Computer Science, the University of Michigan, Ann Arbor, from 1990 to 1991. His current research interests include multi-agent systems, search, and constraint satisfaction. Satoru Fujita, D.Eng.: He received his B.E. and M.E. degrees in electronic engineering from the University of Tokyo in 1984 and 1986, respectively. He also received his D.Eng. from the University of Tokyo in 1989 for his research on context comprehension in natural language understanding. He joined NEC Corporation in 1989, and is now a principal researcher of Internet Systems Research Laboratories of NEC. He is engaged in research on mobile agents, distributed systems and Web services.     

Music composition by interaction between human and computer

This paper aims at constructing a music composition system that composes music by the interaction between human and a computer. Even users without special musical knowledge can compose 16-bar musical works with one melody part and some backing parts using this system. The interactive Genetic Algorithm is introduced to music composition so that users’ feeling toward music is reflected in the composed music. One chromosome corresponds to 4-bar musical work information. Users participate in music composition by evaluating composed works after GA operators such as crossover, mutation, virus infection are applied to chromosomes based on the evaluation results. From the experimental results, it is found that the users’ evaluation values become high over the progress of generations. That is, the system can compose 16-bar musical works reflecting users’ feeling. Muneyuki Unehara: He received his M.S. in Engineering in 2002 from Institute of Science and Engineering, University of Tsukuba. Currently, he is a Ph.D. candidate of Graduate School of Systems and Information Engineering, University of Tsukuba. His research interests include the construction of intelligent systems by considering soft computing techniques and human interface. Takehisa Onisawa, Ph.D.: He received Dr.Eng. in Systems Science in 1986 from Tokyo Institute of Technology. Currently, he is a Professor in the Graduate School of Systems and Information Engineering, University of Tsukuba. His research interests include applications of soft computing techniques to human centered systems thinking. He is a member of IEEE and IFSA.     

Biologically inspired control of quadruped walking robot

In this paper, we present a control method for a quadruped walking robot inspired from the locomotion of quadrupeds. A simple and useful framework for controlling a quadruped walking robot is presented, which is obtained by observing the stimulus-reaction mechanism, the gravity load receptor and the manner of generating repetitive motions from quadrupeds. In addition, we propose a new rhythmic pattern generator that can relieve the large computational burden on solving the kinematics. The proposed method is tested via a dynamic simulation and validated by implementation in a quadruped walking robot, called AiDIN-I (Artificial Digitigrade for Natural Environment I). Recommended by Editorial Board member Sangdeok Park under the direction of Editor Jae-Bok Song. This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2005-D00031). Ig Mo Koo received the B.S. degree in Mechanical Engineering from Myongji University, Yongin, Korea, in 2003, the M.S. degree in Mechanical Engineering from the Sungkyunkwan University, Suwon, Korea, in 2005, where he is currently working toward a Ph.D. degree in Mechanical Engineering from Sungkyunkwan University. His research interests include artificial muscle actuators, haptics, tactile display, biomimetics and quadruped walking robots systems. Tae Hun Kang received the B.S., M.S., and Ph.D. degrees in Mechanical Engineering from Sungkyunkwan University, Korea, in 2000, 2002, and 2006, respectively. His current research interests focus on biomimetics and quadruped walking robot. Gia Loc Vo received the B.S degree in Mechanical Engineering form Ha Noi University of Technology in Vietnam 2003, the M.S. degree Mechanical Engineering form Sungkyunkwan University, Suwon, Korea, in 2006, where he is currently working toward a Ph.D. degree in Mechanical Engineering from Sungkyunkwan University. His research interests include legged locomotion, walking and climbing robot. Tran Duc Trong received the B.S degree in Mechatronics from HoChiMinh City University of Technology in Vietnam in 2005, where he is currently working toward a M.S. degree in Mechanical Engineering from Sungkyunkwan University. His research interests include biological inspired control and adaptive control of quadruped walking robot. Young Kuk Song received the B.S. degree in Mechanical Engineering from Sungkyunkwan University, Suwon, Korea, in 2006, where he is currently working toward a M.S. degree in Mechanical Engineering from Sungkyunkwan University. His research interests include biomimetics, hydraulic robotics system and quadruped walking robot. Hyouk Ryeol Choi received the B.S. degree from Seoul National University, Seoul, Korea, in 1984, the M.S. degree from the Korea Advanced Technology of Science and Technology (KAIST), Daejeon, Korea, in 1986, and the Ph.D. degree from the Pohang University of Science and Technology (POSTECH), Pohang, Korea, in 1994. Since 1995, he has been with Sungkyunkwan University, Suwon, Korea, where he is currently a Professor in the School of Mechanical Engineering. He was an Associate Engineer with LG Electronics Central Research Laboratory, Seoul, Korea, from 1986 to 1989. From 1993 to 1995, he was with Kyoto University, Kyoto, Japan, as a grantee of scholarship funds from the Japanese Educational Administry. He visited the Advanced Institute of Industrial Science Technology (AIST), Tsukuba, Japan, as a JSPS Fellow from 1999 to 2000. He is now an Associate Editor in IEEE Transactions on Robotics, Journal of Intelligent Service Robotics, International Journal of Control, Automation and Systems (IJCAS). His interests includes dexterous mechanisms, field application of robots, and artificial muscle actua tors.     

A novel control loop design and its application to the force balance of vibratory rate sensor

This paper investigates a new loop design approach of force balance control for the vibratory rate sensor application. The proposed force balance control design takes advantages of the modified automatic gain control configuration in controlling the system’s oscillating dynamics at the sense mode. The adapted automatic gain control scheme and force balance strategy, which maintains a constant oscillation magnitude in the sense mode, have several advantages. First it is possible to analyze a complicated nonlinear feedback system using a linear control theory, which resulted in straightforward prediction of closed loop performance. Moreover the control system to achieve the design goals can be implemented using a relatively simple feedback configuration. An application to the vibratory rate sensor using the proposed automatic gain control configuration witnessed that the force balance control can be validated in a practical design process. Experiments using an actual micromachined rate sensor verified the feasibility of the proposed control scheme with demonstration of enhanced performance. Recommended by Editorial Board member Dong Hwan Kim under the direction of Editor Hyun Seok Yang. This work was supported by the BK21 Project, ST-IT Fusion Engineering program in Konkuk University, 2008. This work was supported by the KICOS through a grant provided by the Korean Ministry of Education, Science & Technology in 2008 (No. K20601000001). Sangkyung Sung is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the M.S. and Ph.D. degrees in Electrical Engineering from Seoul National University in 1998 and 2003, respectively. His research interests include inertial sensors, avionic system hardware, integrated navigation, and intelligent vehicle technologies. Sukchang Yun is a Ph.D. course student of the Department of Aerospace Information Engineering at Konkuk University, Korea. He received the M.S. degree in Aerospace Engineering from Konkuk University in 2009. His research interests include MEMS mechatronics and control, INS/GPS integration, and instrumentation. Woon-Tahk Sung is an Senior Engineer of the Communication Reserarch Center, Samsung Electronics Co. Ltd. He received the Ph.D. degree in School of Electrical Engineering from Seoul National University in 2007. His research interests include analog and digital control algorithm, MEMS piezo actuator, circuit design for microsystems using VCM. Chang Joo Kim is an Assistant Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the Ph.D. degree in Aeronautical Engineering from Seoul National University in 1991. His research interests include nonlinear optimal control, helicopter flight mechanics, and helicopter system design. Young Jae Lee is a Professor of the Department of Aerospace Engineering at Konkuk University, Korea. He received the Ph.D. degree in Aerospace Engineering from the University of Texas at Austin in 1990. His research interests include integrity monitoring of GNSS signal, GBAS, RTK, attitude determination, orbit determination, and GNSS related engineering problems.     

A New Challenge for Applying Time Series Metrics Data to Software Quality Estimation

In typical software development, a software reliability growth model (SRGM) is applied in each testing activity to determine the time to finish the testing. However, there are some cases in which the SRGM does not work correctly. That is, the SRGM sometimes mistakes quality for poor quality products. In order to tackle this problem, we focussed on the trend of time series data of software defects among successive testing phases and tried to estimate software quality using the trend. First, we investigate the characteristics of the time series data on the detected faults by observing the change of the number of detected faults. Using the rank correlation coefficient, the data are classified into four kinds of trends. Next, with the intention of estimating software quality, we investigate the relationship between the trends of the time series data and software quality. Here, software quality is defined by the number of faults detected during six months after shipment. Finally, we find a relationship between the trends and metrics data collected in the software design phase. Using logistic regression, we statistically show that two review metrics in the design and coding phase can determine the trend. Sousuke Amasakireceived the B.E. degree in Information and Computer Sciences from Okayama Prefectural University, Japan, in 2000 and the M.E. degree in Information and Computer Sciences from Graduate School of Information Science and Technology, Osaka University, Japan, in 2003. He has been in Ph.D. course of Graduate School of Information Science and Technology at Osaka University. His interests include the software process and the software quality assurance technique. He is a student member of IEEE and ACM. Takashi Yoshitomireceived the B.E. degree in Information and Computer Sciences from Osaka University, Japan, in 2002. He has been working for Hitachi Software Engineering Co., Ltd. Osamu Mizunoreceived the B.E., M.E., and Ph.D. degrees in Information and Computer Sciences from Osaka University, Japan, in 1996, 1998, and 2001, respectively. He is an Assistant Professor of the Graduate School of Information Science and Technology at Osaka University. His research interests include the improvement technique of the software process and the software risk management technique. He is a member of IEEE. Yasunari Takagireceived the B.E. degree in Information and Computer Science, from Nagoya Institute of Technology, Japan, in 1985. He has been working for OMRON Corporation. He has been also in Ph.D. course of Graduate School of Information Science and Technology at Osaka University since 2002. Tohru Kikunoreceived the B.E., M.Sc., and Ph.D. degrees in Electrical Engineering from Osaka University, Japan, in 1970, 1972, and 1975, respectively. He joined Hiroshima University from 1975 to 1987. Since 1990, he has been a Professor of the Department of Information and Computer Sciences at Osaka University. His research interests include the analysis and design of fault-tolerant systems, the quantitative evaluation of software development processes, and the design of procedures for testing communication protocols. He is a member of IEEE and ACM.     

Lyapunov-based feedback design and experimental verification of IC engine speed control

In this paper, the speed control problem of internal combustion engines is investigated based on mean-value engine models. The dynamics of internal combustion engines is a complicated nonlinear system, and usually, it is difficult to know the exact values of the physical parameters. First, a Lyapunov-based design method is shown without requiring the full information of the physical parameters. Then, to improve transient performance, the design method is extended to several cases under different operation conditions. Numerical simulation results are presented for comparing the proposed design methods. Finally, experiments are conducted on an engine test bench and the results demonstrate the validity of the proposed design methods. Recommended by Editorial Board member Myotaeg Lim under the direction of Editor Hyun Seok Yang. The authors are grateful to Kai Zheng for his assistance of the model identification experiments. Jiangyan Zhang received the B.E. and M.E. degrees in Electrical Engineering, Yanshan University, China, in 2005 and 2008, respectively. Now, she is a Ph.D. candidate with the Department of Engineering and Applied Sciences, Sophia University, Tokyo, Japan. Her current research interests include nonlinear system control theory and applications to powertrain system control. Tielong Shen received the Ph.D. degree in Mechanical Engineering from Sophia University, Tokyo, Japan, March, 1992. From April 1992, he has been a faculty member of the Chair of Control Engineering in Department of Mechanical Engineering, Sophia University, where he currently serves as professor of the Department of Engineering and Applied Science. His research interests include control theory and application in mechanical systems, power systems, and automotive powertrain. Currently, he is an Associate Editor for the IEEE Control System Society Conference Editorial Board, and is serving as Associate Editor of Journal of Control Theory and Applications, and the Regional Editor Asia-Pacific for International Journal of Modeling, Identification and Control etc. Junichi Kako received the B.E. degree from Nagoya Institute of Technology, Nagoya, Japan. He joined Toyota Motor Corporation, Tokyo, Japan in 1989. He worked on various aspects of automotive powertrain control. From 1989 to 1994, he took part in the team for the development of Laboratory Automation (LA) system, Engineering Office Automation (EOD) system, and embedded system of powertrain control. During 1995–2001, he focused on the engine control systems in Powertrain Management Engineering Division. In 2002, he was with Future Project Division in which he was responsible for the R&D of model-based engine control system. Currently, he is developing engine control systems in the Powertrain Management Engineering Division, Toyota Motor Corporation. Shozo Yoshida received the M.S. degree in Engineering from Kyoto University, Kyoto, Japan. He joined Toyota Motor Corporation, Tokyo, Japan in 2000. From 2000 to 2004, he was with Future Project Division and worked on physical combustion modeling for Model-based Control Development. Since 2005, he has been with the Powertrain Management Engineering Division Toyota Motor Corporation, and is a member of the R&D of Model-based Engine Calibration.