This paper considers a motion planning method for humanoid robots. First, we review a modular state net which is a state net representing behavior of a part of the humanoid robots. Each whole body motion of the humanoid robots is represented by a combination of modular state nets for those parts. In order to obtain a feasible path of the whole body, a timed Petri net is used as an abstracted model of a set of all modular state nets. Next, we show an algorithm for constructing nonlinear dynamics which describes a periodic motion. Finally, we extend the state net in order to represent primitive periodic motions and their transition relation so that we can generate a sequence of primitive periodic motions satisfying a specified task.

This paper addresses the scheduling problem of a class of automated manufacturing systems with multiple resource requests. In the automated manufacturing system model, a set of jobs is to be processed and each job requires a sequence of operations. Each operation may need more than one resource type and multiple identical units with the same resource type. Upon the completion of an operation, resources needed in the next operation of the same job cannot be released and the remaining resources cannot be released until the start of the next operation. The scheduling problem is formulated by Timed Petri nets model under which the scheduling goal consists in sequencing the transition firing sequence in order to avoid the deadlock situation and to minimize the makespan. In the proposed genetic algorithm with deadlock-free constraint, Petri net transition sequence is coded and a deadlock detection method based on D-siphon technology is proposed to reschedule the sequence of transitions. The enabled transitions should be fired as early as possible and thus the quality of solutions can be improved. In the fitness computation procedure, a penalty item for the infeasible solution is involved to prevent the search process from converging to the infeasible solution. The method proposed in this paper can get a feasible scheduling strategy as well as enable the system to achieve good performance. Numerical results presented in the paper show the efficiency of the proposed algorithm.

To fulfill the computing demands in visual media processing, we have been investigating a parallel processing system to improve the processing speed of the visual media related to applications from the point of view of a memory system within a single instruction multiple data (SIMD) computer. In this paper, we have introduced MAMS-PP4, which is similar to a pipelined SIMD architecture type and consists of pq processing elements (PEs) as well as a multi-access memory system (MAMS). MAMS supports simultaneous access to pq data elements within a horizontal (1 pq), a vertical (pq 1) or a block (p q) subarray with a constant interval in an arbitrary position in an M N array of data elements, where the number of memory modules, m, is a prime number greater than pq. MAMS reduces the memory access time for an SIMD computer and also improves the cost and complexity that involved in controlling the large volume of data demanded in visual media applications. PE is designed to be a two-state machine in order to utilize MAMS efficiently. MAMS-PP4 was fabricated into ASIC using TOSHIBA TC240C series library and a test board was used to measure the performance of ASIC. The test board consists of devices such as an MPC860 embedded-PCI board, two ASICs and a FPGA for the control units. Experiment was done on various computer systems in order to compare the performance of MAMS-PP4 using morphological operations as the application. MAMS-PP4 shows a respectful and consistent processing speed.

This paper provides a list-scheduling method for program nets executed with two processors. The program nets dealt with in this paper are acyclic and SWITCH-less, and the priority list proposed in this paper consists of both dynamic and static lists. First, we point out the weakness of a previously proposed priority list and propose a new priority list. Then we give properties of the new priority list and further prove this new priority list can generate optimal schedules for the program nets whose AND-nodes possess at most single input edge. Finally, we compare the new priority list with the previous one to show the new priority list can generate shorter schedules than the previous for the nets whose AND-nodes may have two input edges.

This paper proposes methods of computing maximum throughput for Petri nets that model workflows including resources, called WF-nets with resources. We first propose the formal definitions of WF-nets with resources and their subclasses: marked graph/state machine WF-nets with conflict-free resources (CF-Res-MG/SMWF-nets). We also show several properties of CF-Res-MG/SMWF-nets. Next we give the methods of computing maximum throughput for CF-Res-MG/SMWF-nets under condition that all tokens have to be processed in the order of First-In First-Out (FIFO). Concretely, for CF-Res-MGWF-nets, on the basis of Ramamoorthy's method of computing cycle time, we give an algorithm of computing maximum throughput under the FIFO condition. For CF-Res-SMWF-nets, there is not any method of computing maximum throughput under the FIFO condition. So we are the first to give an algorithm of computing maximum throughput for CF-Res-SMWF-nets under the FIFO condition. Finally we show an example of computing maximum throughput by using our method.

In this paper, we propose a formal method for detection of three automation surprises in human-machine interaction; a mode confusion, a refusal state, and a blocking state. The mode confusion arises when a machine is in a different mode from that anticipated by the user, and is the most famous automation surprise. The refusal state is a situation that the machine does not respond to a command the user executes. The blocking state is a situation where an internal event occurs, leading to change of an interface the user does not know. In order to detect these phenomena, we propose a composite model in which a machine and a user model evolve concurrently. We show that the detection of these phenomena in human-machine interaction can be reduced to a reachability problem in the composite model.

We introduce an inheritance concept into a specification method of a concurrent system in order to reuse and refine existing specifications. Reusability by inheritance is emphasized in this paper. We take multiple inheritance to enable to reuse several specifications at a time. An upper specification can be skillfully reused by dividing inherited parts and non-inherited ones if the specification contains unnecessary parts for a lower specification. As an application, we specify the FIPA contract net interaction protocol (IP) with the function of an agent authentication. This is accomplished by using multiple inheritance. We also specify the FIPA iterated contract net IP by reusing the FIPA contract net IP. We have been developing a validation support tool for specifications described with the proposed method.

A batch process is a typical concurrent system in which multiple interacting tasks are carried out in parallel on several batches at the same time. A major difficulty in designing a batch control system is the lack of modeling techniques. This paper aims at developing a method of constructing batch control system models in a hierarchical manner and operating batch processes using the constructed models. For this purpose, it first defines process and plant specifications described by partial languages, next presents a procedure for constructing hierarchical Petri net based models, and states the verification of models based on reachability analysis. It also discusses the detection of faults and conflicts in batch processes based on place-invariant analysis.

LOTOS parallel operator, which is a binary operator, is used to combine processes in order to express their concurrency. Unlike other LOTOS operators, various possibilities exist when combining processes by the parallel operator. If two processes are selected randomly for combining, the size of the composite intermediate process after combining may be large. In this paper, we propose an algorithm for selecting two processes out of three or more processes so that the size of the intermediate process is the smallest when combined by the parallel operator. Smaller size of an intermediate process means it takes less memory space which is very important in designing verification tools for systems or communication protocols specified in LOTOS.

In this paper, we propose an optimal power control algorithm with fast convergence rate for CDMA cellular systems. The new power control algorithm is based on linear quadratic control theory (LQR). Using the state feedback control designed to minimize an objective function, each mobile performs a successful transmission with optimal power. Simulation results show a fast convergence rate to target SIR with less power consumption, and an augmented channel capacity through decreased outage probability.

We study analysis of hybrid systems under incomplete knowledge. The class of hybrid systems to be considered is assumed to have the form of a rectangular hybrid automaton such that each constant in invariants and guards is given as a parameter. We develop a method based on symbolic computation that computes an approximation of the discrete behavior of the automaton. We also show an implementation on a constraint logic programming language.

Through many researches on modeling and analyzing biological pathways, Petri net has recognized as a promising method for representing biological pathways. Recently, Matsuno et al. (2003) introduced hybrid functional Petri net (HFPN) for giving more intuitive and natural biological pathway modeling method than existing Petri nets. They also developed Genomic Object Net (GON) which employs the HFPN as a basic architecture. Many kinds of biological pathways have been modeled with the HFPN and simulated by the GON. This paper gives a new HFPN model of "cell cycle of fission yeast" with giving six basic HFPN components of typical biological reactions, and demonstrating the method how biological pathways can be modeled with these HFPN components. Simulation results by GON suggest a new hypothesis which will help biologist for performing further experiments.

The control problem of hybrid systems have received considerable attention. However, because of the existence of constraints and the combinatorial nature of continuous time and discrete event dynamics, the understanding of hybrid systems is rather limited at present. Only optimal control approaches were proposed based on heuristic rules. Few theoretical properties of system can be predicted until now. In this paper, we consider the tracking control problem of hybrid plants represented by MLD model to follow a family of reference signals produced by an external generator. Some new results are presented. The internal model principle of continuous system is extended to hybrid systems so as to solve the problem.

This paper provides a computational method to construct a Lyapunov function to prove a stability of hybrid automata that can have nonlinear vector fields. Algebraic inequalities and equations are formulated, which are solved via LMI optimization. Numerical examples are presented to illustrate the proposed method.

We develop an algorithm for a controller design method for Max-Plus Linear (MPL) systems with selective parameters. Since the conventional algorithm we proposed requires high computational load when the prediction horizon is large, two methods for reducing the calculation time are proposed. One is based upon the branch-and-bound method, and the other is to reuse the optimal solution. The effectiveness of these two methods is confirmed through numerical simulation.

This paper proposes a simple method for estimation and compensation of signal direction, to deal with relative change of sound source location caused by the movements of a microphone array and a sound source. This method introduces a delay filter that has shifted and sampled sinc functions. This paper presents a concept for the joint optimization of arrival time differences and of the coordinate system of a mobile microphone array. We use the LMS algorithm to derive this method by maintaining a certain relationship between the directions of the microphone array and the sound source directions. This method directly estimates the relative directions of the microphone array to the sound source directions by minimizing the relative differences of arrival time among the observed signals, not by estimating the time difference of arrival (TDOA) between two observed signals. This method also compensates the time delay of the observed signals simultaneously, and it has a feature to maintain that the output signals are in phase. Simulation results support effectiveness of the method.

In this paper, we present a new numerical method for the complex approximation of FIR digital filters. Our objective is to design FIR filters with equiripple magnitude and phase errors. The proposed method solves the least squares (LS) problem iteratively. At each iteration, the desired response is updated so as to have an equiripple error. The proposed methods do not require any time-consuming optimization procedure such as the quasi-Newton methods and converge to equiripple solutions quickly. We show some examples to illustrate the advantages of our proposed methods.

A low-power high-frequency sinusoidal quadrature oscillator is presented through a new RC technique using only CMOS current mirrors. The technique is relatively simple based on (1) internal capacitances of CMOS current mirrors and (2) a resistor of a CMOS current mirror for a negative resistance. Neither external capacitances nor inductances are required. As a particular example, a 2.4 GHz-0.4 mW, 0.325-f_T, CMOS sinusoidal quadrature oscillator has been demonstrated. The power consumption is very low at approximately 0.4 mW. Total harmonic distortions (THD) are less than 0.3%. The oscillation frequency is current-tunable over a range of 540 MHz or 22%. The amplitude matching and the quadrature phase matching are better than 0.035 dB and 0.15, respectively. A figure of merit called a normalized carrier-to-noise ratio (CNR_norm) is 158.79 dBc/Hz at the 2 MHz offset from 2.46 GHz. Comparisons to other approaches are also presented.

For large circuits, vector compaction techniques could provide a faster solution for power estimation with reasonable accuracy. Because traditional sampling approach will incur useless transitions between every sampled pattern pairs after they are concatenated into a single sequence for simulation, we proposed a vector compaction method with grouping and single-sequence consecutive sampling technique to solve this problem. However, it is very possible that we cannot find a perfect consecutive sequence without any undesired transitions. In such cases, the compaction ratio of the sequence length may not be improved too much. In this paper, we propose an efficient approach to relax the limitation a little bit such that multiple consecutive sequences are allowed. We also propose an algorithm to reduce the number of sequences instead of setting the number as one to find better solutions for vector compaction problem. As demonstrated in the experimental results, the average compaction ratio and speedup can be significantly improved by using this new approach.

The optimum tier architectures for ASICs are investigated by using a methodology for predicting packing efficiency of a logic block (the ratio of total cell area to the block area including space regions between cells). In the methodology based on Rent's rule, (1) the empirical parameters required for the prediction are derived from the results of our ASIC products. (2) The concept of logic distance, which is expressed in units of the number of cells rather than the absolute net length, is introduced. (3) Not only performance constraints but also reliability constraints are incorporated. These allow us to make a quantitative comparison of the packing efficiency between various cell and tier structures. It is found that, for mega-cell blocks, all minimum-pitch layer architecture with buffer insertion is expected to give more than 20% reduction in block areas compared to the minimum-pitch + bi-pitch architecture, while satisfying the performance and reliability constraints.

We will propose a key-agreement-type three-party password-authenticated key exchange protocol. The proposed protocol is quite efficient and, among the same type of protocols, is the first to be formally proven to be secure. A three-party formal model for security proof is proposed based on [25] and [26]. We construct a simulator in this model to show that our proposed protocol is secure under reasonable and well-defined cryptographic primitives.

We propose a novel hierarchical transmission method of DCT coefficients using multi-code DS/SS modulation. For low resolution image transmission over noisy channel, an error resilient and graceful degradation technique is necessary. Here, the DCT coefficients are divided into each stratum (a branch of multi-code DS/SS) and transmitted simultaneously through a noisy channel. By assigning an appropriate transmission energy that corresponds to their source energy variances, energy assignment, it is possible to maintain picture quality effectively even in a noisy channel. Analysis of this method was performed using an image data model, 2-D Gauss-Markov random field, which showed that picture quality is maintained even in the noisy channel condition.

Electronic Toll Collection (ETC), an application of Dedicated Short Range Wireless Communication (DSRC), had suffered from wrong operations due to multipath problems. To solve this problem, we proposed to apply a simple configured path determination scheme for the ETC system. The system consists of a vector network analyzer, low-noise amplifier, and X-Y positioner and achieves an automatic measurement of the spatial transfer function with emphasis on accurate measurement and reproducibility. For the reliable identification of the propagating paths, 3-D Unitary ESPRIT and SAGE algorithms were employed. Having developed the system, field experiments at the toll gate of the highway was carried out. In the measurements, we could determine many propagation paths so that the dominant propagation phenomena at the toll gate was identified. They included a ground-canopy twice reflected wave, which was a potential path that caused wrong operation. Consequently, their reflection coefficients and polarization characteristics were investigated. From the results, applicability of the path determination system for short range on-site measurement was confirmed.

In the formerly proposed theory for sub-linear (linear in a changed addition rule) systems, we developed a sub-linear mathematical theory and demonstrated its capability in several sub-linear systems. In this paper, we assert that we can further construct hybrid systems useful in engineering by combining sub-linear systems with linear systems, and as an example, we show the construction of a divergence-free electrodynamics. Since the energy of photon fields in engineering is tending upward, it would be desirable for us to get rid of the divergence difficulties encountered in the conventional high energy electrodynamics. The most important result is the recognition that Nature herself has a hybrid system composed of sub-linear photon fields and linear electron fields. Mathematically, our electrodynamics is formulated by only one point correction (the insertion of tanh into the electromagnetic energy density) in the conventional electrodynamics of photons and electrons (including positrons).

In this study, we analyze the memory-based architecture of the FFT processor using the radix-4, and propose a novel mechanism that improves the throughput while simultaneously decreasing the area using single-port memories with several banks.