Gerardo AYALA San Martin Yoneo YANO
Effective collaboration in ComputerSupported Collaborative Learning (CSCL) environments is nowadays an important research topic. It deals with two main problems: the configuration of an appropriate learning group and the intelligent task distribution in the practice of domain knowledge. In order to have effective collaboration in a CSCL environment, we have proposed a set of software agents that assist the learners to select their learning tasks, according to their capabilities and the possibilities of collaboration between them. In this paper the cooperation among software agents is presented as the key point for effective collaboration in CSCL environments. In this kind of environments the learner must have enough collaboration and learning possibilities, being motivated with the experience of social knowledge construction. We have been working on the problem of effective collaboration in CSCL environments, based on the cooperation between software agents developed for GRACILE, our Japanese Grammar CSCL environment. Before, we have proposed intelligent agents that assist the learners. Our next step has been the design of the cooperation between agents in order to create possibilities of effective collaboration in a virtual community of practice. In order to evaluate the performance of our agents we made several simulations. The results obtained from these simulations of diverse types of learning groups provided us with guidelines for the configuration of groups in CSCL environments, where effective collaboration is possible.
The purpose of our study is to develop an intelligent adaptive instruction system that manages intelligently the learner's estimated knowledge structure and optimizes the selection of problems according to his/her knowledge structures. The system adopts the dynamic problems of high school physics as a material of study, and is intended to operate on a UNIX Work Station. For these purposes, the system is composed of three parts, 1) interface part, 2) problem solving expert part, and 3) optimization expert system part for problem selection. The main feature of our system is that both knowledge structures of learner and teacher are represented by structural graph, and the problem selection process is controlled by the relationship between the learner's knowledge structure and the teacher's knowledge structure. In our system the relationship between these two knowledge structures is handled in the optimization expert system part for problem selection. In this paper the theory of the optimization expert system part for problem selection is described, and the effectiveness of this part is clarified through a simulation experiment of the originally defined matching coefficient.
A sequence of nonnegative integers s=(S1, s2, , sn) is a score sequence of an r-tournament if, for some positive integer r, ther is a directed graph with vertices v1, v2, , vn such that deg+(vj)=sj and deg-(vj)=r(n-1) -sj for each j=1, 2, , n. The score sequence problem of an r-tournament is: Given some positive integer r and a sequence of nonnegative integers, determine whether it is a score sequence of an r-tournament or not. In this paper, we consider several variations of the score sequence problem of an r-tournament, and give efficient algorithms.
Toshinori YAMASAKI Tetsuo HATTORI
We developed the computer calligraphy, that is, a computer formation of brush-written Kanji characters using calligraphic knowledge. The style of brush handwriting depends mainly on the way of using a writing brush. Brush writing skills include the direction of brush at the beginning, curvature and turning the brush, the brush-up at the termination point in a stroke. We make up the calligraphic knowledge base according to the above mentioned brush writing skills. For simulating real brush movement, we represent the brush contact form that is the brush shape on the writing plane as a brush-touch. The system can control the size and direction of this brush-touch during the brush simulation. The system simulates the real brush writing to move the brush-touch along the skeleton letter shape in the standard database. We get the brush written Kanji from the locus of the brush-touch movement. We can extend this system to the new on line training system for brush writing using the simulation of brushtouch movement modified by the pressure, speed and rotation of the writing brush, and the skeleton letters written by a learner from the tablet. This system is also useful for students learning how to write Japanese letters beautifully with brush.
Kaoru KUROSAWA Yutaka KATAYAMA Wakaha OGATA
This paper presents a reshufflable and laziness tolerant mental card game protocol. First, our protocol can reshuffle any subset of cards. For example, some opened cards and some face down cards can be shuffled together. Next, we consider two types of honest players, currently active and currently nonactive. A player is currently nonactive if he dropped out the game or he declared "pass" and has not declared "rejoin" yet. In the proposed protocol, if more than half of the players are currently active, they can play the game. In this case, the privacy of the currently nonactive players are kept secret.
Yoshitaka FUJIWARA Shin-ichiro OKADA Hiroyuki TAKADOI Toshiharu MATSUNISHI Hiroshi OHKAMA
In a conventional client-server system using the satellite communications, the responsibility of the system to the client user is considerably degraded by the long transmission time between the satellite and the ground terminal as well as the relatively low data transmission rate in comparison with the ground transmission line as the Ethernet. In this paper, a new client-server control, VEEC, is proposed to solve the problem. As a result of the experimental performance studies, it is clarified that the responsibility in the client is remarkably improved when the pre-fetching mechanism of VEEC works efficiently.
The edge of a thin SOI (silicon on insulator) film was used to form a very narrow Si-MOS inversion layer. The ultra-thin SOI film was formed by local oxidation of SIMOX wafer. The thickness of the SOI film is less than 15 nm, i.e., the channel width is narrower than 15 nm. At low tempera-tures, clear and large conductance oscillations were seen in this edge channel MOSFET. These oscillations are explained by Coulomb blockade effects in the narrow channel with several effective potential barriers, since the SOI film is so thin that the channel current is seriously affected by small potential fluctuations in the channel. These results suggest that the channel current in edge quantum wire MOSFET can be cut off even with a small controlled potential change. Furthermore, we fabricated a double-gate edge channel Si-MOSFET. In this device, the channel current can be controlled in two ways. One way is to control the electron number inside the isolated electrodes. The other way is to control the threshold voltage of MOSFET. This device enables us to control the phase of Coulomb oscillation.
Zhixiong WU Toshifumi KANAMARU
For very low bit-rate video coding such as under 64 kbps, it is unreasonable to encode and transmit all the information. Thus, it is very important to choose the "important" information and encode it efficiently. In this paper, we first propose an image separation-composition method to solve this problem. At the encoder, an image is separated into a low-frequency part and two (horizontal and vertical) edge parts, which are considered as "important" information for human visualization. The low-frequency part is encoded by using block DCT and linear quantization. And the edges are selected by their values and encoded by using Chain coding to remain the most of the important parts for human visualization. At the decoder, the image is reconstructed by first generating the high-frequency parts from the horizontal and vertical edge parts, respectively, and then applying the inverse wavelet transform to the low frequency part and high frequency parts. This composition algorithm has less computational complexity than the conventional analytic/synthetic algorithms because it is not based on iterating approach. Moreover, to reduce the temporal redundancy efficiently, we propose a hierarchical motion detection and a motion interpolation /extrapolation algorithm. We detect motion vectors and motion regions between two reconstructed images and then predict the motion vectors of the current image from the previous detected motion vectors and motion regions by using the interpolation/extrapolation both at the encoder and at the decoder. Therefore, it is unnecessary to transmit the motion vectors and motion regions. This algorithm reduces not only the temporal redundancy but also bit-rates for coding side information . Furthermore, because the motion detection is completely syntax independent, any type of motion detection can be used. We show some simulation results of the proposed video coding algorithm with the coding bit-rate down to 24 kbps and 10 kbps.
Correspondence problem in road image sequence is discussed and a method to establish road correspondence from its perspective image sequence is suggested. The proposed method is mainly based on the features of turn angles of road edge points, while the turn angle for each edge point at one time can be computed from the frame based on the determination of matching points whin that frame. The turn angles will change from frame to frame according to the panning rotation of the camera and, each stationary edge point, the difference of turn angles between two frames equals the panning angle of the camera. Thus we develop an algorithm to estimate the value of panning angle of the camera by which correspondence in road image sequence can be established.
Surapan AIRPHAIBOON Shozo KONDO
A method for the recognition of handprinted Thai characters input using an image scanner is presented. We use methods of edge detection and boundary contour tracing algorithms to extract loop structures from input characters. The number of loops and their locations are detected and used as information for rough classification. For fine classification, local feature analysis of Thai characters is presented to discriminate an output character from a group of similar characters. In this paper, four parts of the recognition system are presented: Preprocessing, single-character segmentation, loop structure extraction and character identification. Preprocessing consists of pattern binarization, noise reduction and slant normalization based on geometrical transformation for the forward (backward) slanted word. The method of single-character segmentation is applied during the recognition phase. Each character from an input word including the character line level information is subjected to the processes of edge detection, contour tracing and thinning to detect loop structures and to extract topological properties of strokes. The decision trees are constructed based on the obtained information about loops, end points of strokes and some local characteristics of Thai characters. The proposed system is implemented on a personal computer, and a high recognition rate is obtained for 1000 samples of handprinted Thai words from 20 subjects.
Yasushi KANAZAWA Kenichi KANATANI
Introducing a mathematical model of image noise, we formalize the problem of fitting a line to point data as statistical estimation. It is shown that the reliability of the fitted line can be evaluated quantitatively in the form of the covariance matrix of the parameters. We present a numerical scheme called renormalization for computing an optimal fit and at the same time evaluating its reliability. We also present a scheme for visualizing the reliability of the fit by means of the primary deviation pair and derive an analytical expression for the reliability of a line fitted to an edge segment by using an asymptotic approximation. Our method is illustrated by showing simulations and real-image examples.
Toshinori YAMADA Koji YAMAMOTO Shuichi UENO
Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph G from H by adding a minimum number Δ(t, H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate Δ(t, H) for the hypercube and torus, which are well-known as important interconnection networks for multiprocessor systems. If we denote the hypercube and the square torus on N vertices by QN and DN respectively, we show, among others, that Δ(t, QN) = O(tN log(log N/t + log 2e)) for any t and N (t 2), and Δ(1, DN) = N/2 for N even.
Gil-Haeng LEE Heung-Kyu LEE Jung-Wan CHO
In an adaptive load balancing, the location policy to determine a destination node for transferring tasks can be classified into three categories: dynamic selection, random selection, and state polling. The dynamic selection immediately determines a destination node by exploiting the state information broadcasted from other nodes. It not only requires the overheads of collecting the state information, but may cause an unpredictable behavior unless the state information is accurate. Also, it may not guarantee even load distribution. The random selection determines a destination node at random. The state polling determines a destination node by polling other nodes. It may cause some problems such as useless polling, unachievable load balancing, and system instability. A new Sender-initiated Adaptive LOad balancing scheme (SALO) is presented to remedy the above problems. It determines a destination node by exploiting the predictable state knowledge and by polling the destination node. It can determine a good destination with minimal useless polling and guarantee even load distribution. Also, it has an efficient mechanism and good data structure to collect the state information simply. An analytic model is developed to compare with other well known schemes. The validity of the model is checked with an event-driven simulation. With the model and the simulation result, it is shown that SALO yields a significant improvement over other schemes, especially at high system loads.
Md. Shoaib BHUIYAN Hiroshi MATSUO Akira IWATA Hideo FUJIMOTO Makoto SATOH
Existing edge detection methods provide unsatisfactory results when contrast changes largely within an image due to non-uniform illumination. Koch et al. developed an energy function based upon the Hopfield neural network, whose coefficients were fixed by trial and error, and remain constant for the entire image, irrespective of the differences in intensity level. This paper presents an improved edge detection method for non-uniformly illuminated images. We propose that the energy function coefficients for an image with inconsistent illumination should not remain fixed, rather should vary as a second-order function of the intensity differences between pixels, and actually use a schedule of changing coefficients. The results, compared with those of existing methods, suggest a better strategy for edge detection depending upon both the dynamic range of the original image pixel values as well as their contrast.
This paper proposes a robust method for detecting step and ramp edges. In this method, an edge is defined not as a point where there is a large change in intensity, but as a region boundary based on the separability of image features which can be calculated by linear discriminant analysis. Based on this definition of an edge, its intensity can be obtained from the separability, which depends only on the shape of an edge. This characteristic enables easy selection of the optimum threshold value for the extraction of an edge, and this method can be applied to color and texture edge extraction. Experimental results have demonstrated that this proposed method is robust to noise and dulled edges, and, in addition, allows easy selection of the optimum threshold value.
A new high-performance fault-tolerant ATM switching network is proposed. This network contains the baseline network and has many redundant switching elements to enhance the fault tolerance and throughput of the conventional multistage interconnection networks. The presented routing algorithm is very simple and can support a very huge number of paths between each input-output pair. The paths can be used to route cells when internal cell contentions occur in switching elements. The redundant switching elements at the last stage offer two access points to the output ports to resolve the output conflict. Performance analysis and simulation results show that this network has better maximum throughput even for faulty conditions. Among various networks, it has the largest number of redundant paths, and the greatest unit node contribution and unit edge contribution.
The background concepts and methodologies of the knowledge-based program understander ALPUS is discussed. ALPUS understands user's buggy Pascal programs using four kinds of programming knowledge: the knowledge on algorithms, programming techniques, the Pascal language, and logical bugs. The knowledge on algorithms, the key knowledge, is represented in a form of hierarchical data structure called Hierarchical Procedure Graph (HPG). In HPG each node represents a chunk of operations called process," which is consisted of sub-processes. The other knowledge is maintained as independent knowledge bases and linked to associated processes of the HPG. The knowledge about bugs acquired by cognitive experiment is grouped into three categories: bugs on algorithms, programming techniques, and the Pascal language, and connected to associated elements of programming knowledge respectively. ALPUS tries to understand user's buggy programs, detects logical bugs, infers user's intentions, and gives advices for fixing bugs. Program understanding is achieved by three steps: normalization, variable identification, and process and technique identification. Normalization results in improving flexibility of understanding. Variable, process and technique identifications are achieved by knowledge-based pattern matching. Intentions are inferred by means of information attached to buggy patterns. The result of comprehension is reported to a user (i.e., student). Experimental results using Quicksort programs written by students show that the HPG formalism is quite powerful in understanding algorithm-oriented programs. The ALPUS's way of program comprehension is useful in the situation of programming education in an intermediate class of an engineering school. The ALPUS system is a subsystem of the intelligent programming environment INTELLITUTOR for learning programming, which was implemented in the frame-based knowledge engineering environment ZERO on a UNIX workstation.
Yoshizumi KOBAYASHI Tadashi OHTA Nobuyoshi TERASHIMA
This paper proposes a requirement description and elicitation approach for communication services. Requirements are described in natural language, refined with a knowledge base, and converted to a formal language for program generation. A model for communication services is made as a set of three items: terminal state, terminal action and the response of the communication system to the action. This set, in turn, corresponds to natural language syntax that expresses two conditions (terminal state and action) and their result. These conditions and result are expressed as a sequence of simple sentences that describe the relationship between a terminal and a communication system. Thus, by defining such a description style to reflect the features of communication services, it should be possible to achieve both a high level of description and mechanical processing capabilities at the same time. However, requirement descriptions usually include omission and inconsistency. This problem cannot be solved by merely introducing natural language for the descriptions. Knowledge about the target domain of requirements is needed to resolve it. This paper reports on a knowledge base that stores constraints existing between conditions and results in communication services. This knowledge base is shown to be effective in supplementing omissions and resolving inconsistency. This paper also presents a technique for converting the elicited requirements in natural language to descriptions in a formal language that can be used to generate a program.
Masanobu WATANABE Toru YAMANOUCHI Masahiko IWAMOTO Satoru FUJITA
This paper describes, from a system architectural viewpoint, how knowledge-based technologies have been utilized in developing EXLOG (an LSI circuit synthesis system) and SOFTEX (a software synthesis system) inside the authors' projects. Although the system architectures for EXLOG and SOFTEX started from the same production systems, consisting of transformation rules in the middle of the 1980's, both branched off in different directions in the 1990's. Based on experiences with EXLOG and SOFTEX, the differences between LSI and software design models are discussed, and the future directions are indicated for the knowledge-based design system architectures.
Intelligent Tutoring Systems (ITS) represents a wide class of computer based tutoring systems, designed with an extensive use of the technology of modern Artificial Intelligence. Successful applications of various expert systems and other knowledge based systems of AI gave rise to a new wave of interests to ITS. Yet, many authors conclude that practically valuable achievements of ITS are rather modest despite the relatively long history of attempts to use knowledge based systems for tutoring. It is advocated in this paper that some basic obstacles for designing really successful ITS are due to the lack of well understood and sound models of the education process. The paper proposes to overcome these problems by borrowing the required models from AI and adjacent fields. In particular, the concept of Learning Levels from AI might be very useful both for giving a valuable retrospective analysis of computer based tutoring and for suggestion of some perspective directions in the field of ITS.