Reinforcement learning (RL) has made significant progress in various domains, but scaling it to long-horizon tasks with complex decision-making remains challenging. Skill learning attempts to address this by abstracting actions into higher-level behaviors. However, current approaches often fail to recognize semantically similar behaviors as the same skill and use fixed skill lengths, limiting flexibility and generalization. To address this, we propose Dynamic Contrastive Skill Learning (DCSL), a novel framework that redefines skill representation and learning. DCSL introduces three key ideas: state-transition based skill definition, skill similarity function learning, and dynamic skill length adjustment. By focusing on state transitions and leveraging contrastive learning, DCSL effectively captures the semantic context of behaviors and adapts skill lengths to match the appropriate temporal extent of behaviors. Our approach enables more flexible and adaptive skill extraction, particularly in complex or noisy datasets, and demonstrates competitive performance compared to existing methods in task completion and efficiency.

Large language models (LLMs) have shown significant potential in guiding embodied agents to execute language instructions across a range of tasks, including robotic manipulation and navigation. However, existing methods are primarily designed for static environments and do not leverage the agent's own experiences to refine its initial plans. Given that real-world environments are inherently stochastic, initial plans based solely on LLMs' general knowledge may fail to achieve their objectives, unlike in static scenarios. To address this limitation, this study introduces the Experience-and-Emotion Map (E2Map), which integrates not only LLM knowledge but also the agent's real-world experiences, drawing inspiration from human emotional responses. The proposed methodology enables one-shot behavior adjustments by updating the E2Map based on the agent's experiences. Our evaluation in stochastic navigation environments, including both simulations and real-world scenarios, demonstrates that the proposed method significantly enhances performance in stochastic environments compared to existing LLM-based approaches. The code and supplementary materials are available at https://e2map.github.io/.

The presence of Non-Line-of-Sight (NLoS) blind spots resulting from roadside parking in urban environments poses a significant challenge to road safety, particularly due to the sudden emergence of pedestrians. mmWave technology leverages diffraction and reflection to observe NLoS regions, and recent studies have demonstrated its potential for detecting obscured objects. However, existing approaches predominantly rely on predefined spatial information or assume simple wall reflections, thereby limiting their generalizability and practical applicability. A particular challenge arises in scenarios where pedestrians suddenly appear from between parked vehicles, as these parked vehicles act as temporary spatial obstructions. Furthermore, since parked vehicles are dynamic and may relocate over time, spatial information obtained from satellite maps or other predefined sources may not accurately reflect real-time road conditions, leading to erroneous sensor interpretations. To address this limitation, we propose an NLoS pedestrian localization framework that integrates monocular camera image with 2D radar point cloud (PCD) data. The proposed method initially detects parked vehicles through image segmentation, estimates depth to infer approximate spatial characteristics, and subsequently refines this information using 2D radar PCD to achieve precise spatial inference. Experimental evaluations conducted in real-world urban road environments demonstrate that the proposed approach enhances early pedestrian detection and contributes to improved road safety. Supplementary materials are available at https://hiyeun.github.io/NLoS/.

Robots operating in human-centric or hazardous environments must proactively anticipate and mitigate dangers beyond basic obstacle detection. Traditional navigation systems often depend on static maps, which struggle to account for dynamic risks, such as a person emerging from a suddenly opening door. As a result, these systems tend to be reactive rather than anticipatory when handling dynamic hazards. Recent advancements in pre-trained large language models and vision-language models (VLMs) create new opportunities for proactive hazard avoidance. In this work, we propose a zero-shot language-as-cost mapping framework that leverages VLMs to interpret visual scenes, assess potential dynamic risks, and assign risk-aware navigation costs preemptively, enabling robots to anticipate hazards before they materialize. By integrating this language-based cost map with a geometric obstacle map, the robot not only identifies existing obstacles but also anticipates and proactively plans around potential hazards arising from environmental dynamics. Experiments in simulated and diverse dynamic environments demonstrate that the proposed method significantly improves navigation success rates and reduces hazard encounters, compared to reactive baseline planners. Code and supplementary materials are available at https://github.com/Taekmino/LaC.

Autonomous vehicles are increasingly utilized in diverse industries, relying heavily on perception systems to interpret their surroundings for decision-making and control. While Line-of-Sight perception technologies have advanced significantly, Non-Line-of-Sight (NLoS) perception remains a critical challenge. Current systems struggle to detect objects in NLoS scenarios, such as pedestrians or vehicles suddenly appearing from behind obstacles, leading to accidents, particularly at narrow T-junctions in urban environments. To address this, mmWave radar has emerged as a promising sensor for NLoS perception due to its ability to capture reflections and estimate the location of dynamic objects in occluded areas. However, previous researches are limited to controlled settings or single objects, with challenges like multipath reflections requiring precise spatial analysis for real-world use. In this paper, we propose a localization method for multi-dynamic NLoS pedestrians using ray tracing on 2D radar point clouds obtained from mm Wave radar in outdoor environments. The approach involves inferring spatial information from static points, performing ray tracing for dynamic points, and applying noise filtering and clustering to estimate pedestrian locations. Validation on a custom-built test bed demonstrates the effectiveness of the method, establishing a foundation for advanced NLoS perception technologies in real-world driving.

Sound can be utilized to gather information about vehicles approaching a Non-Line-of-Sight (NLoS) region that remains hidden from Line-of-Sight (LoS) sensors due to its reflective and diffractive characteristics, like a radar. However, due to the inability to determine the location of NLoS vehicles in previous studies, it has not been possible to construct a sound-based active emergency braking system. This paper introduces a novel approach for localization of vehicles approaching in NLoS regions through sound. Specifically, a new particle filter method incorporating Acoustic-Spatial Pseudo-Likelihood (ASPLE) has been proposed to track objects using both acoustic and spatial information from the ego vehicle. Also, the Acoustic Recognition based Invisible-target Localization (ARIL) dataset, which is the firstly providing the location of the NLoS vehicle as ground truth using Bird’s Eye View camera, is proposed. The proposed method is validated using two datasets: the ARIL dataset and the Occluded Vehicle Acoustic Detection Dataset (OVAD) dataset. The proposed method exhibited remarkable performance in localizing NLoS targets in both datasets, predicting the location of the vehicle in the NLoS region. Lastly, the analysis of how the reflection of sound affects to the proposed method, highlighting variations based on the spatial situations, and demonstrate the empirical convergence of the method is described. Our code and dataset is available athttps://github.com/mingujeon/NLoSVehicleLocalization.

In this study, we address the off-road traversability estimation problem, that predicts areas where a robot can navigate in off-road environments. An off-road environment is an unstructured environment comprising a combination of traversable and non-traversable spaces, which presents a challenge for estimating traversability. This study highlights three primary factors that affect a robot’s traversability in an off-road environment: surface slope, semantic information, and robot platform. We present two strategies for estimating traversability, using a guide filter network (GFN) and footprint supervision module (FSM). The first strategy involves building a novel GFN using a newly designed guide filter layer. The GFN interprets the surface and semantic information from the input data and integrates them to extract features optimized for traversability estimation. The second strategy involves developing an FSM, which is a self-supervision module that utilizes the path traversed by the robot in pre-driving, also known as a footprint. This enables the prediction of traversability that reflects the characteristics of the robot platform. Based on these two strategies, the proposed method overcomes the limitations of existing methods, which require laborious human supervision and lack scalability. Extensive experiments in diverse conditions, including automobiles and unmanned ground vehicles, herbfields, woodlands, and farmlands, demonstrate that the proposed method is compatible for various robot platforms and adaptable to a range of terrains. Code is available at https://github.com/yurimjeon1892/FtFoot.

Hierarchical reinforcement learning (HRL) incorporates temporal abstraction into reinforcement learning (RL) by explicitly taking advantage of hierarchical structures. Modern HRL typically designs a hierarchical agent composed of a high-level policy and low-level policies. The high-level policy selects which low-level policy to activate at a lower frequency and the activated low-level policy selects an action at each time step. Recent HRL algorithms have achieved performance gains over standard RL algorithms in synthetic navigation tasks. However, these HRL algorithms still cannot be applied to real-world navigation tasks. One of the main challenges is that real-world navigation tasks require an agent to perform safe and interactive behaviors in dynamic environments. In this paper, we propose imagination-augmented HRL (IAHRL) that efficiently integrates imagination into HRL to enable an agent to learn safe and interactive behaviors in real-world navigation tasks. Imagination is to predict the consequences of actions without interactions with actual environments. The key idea behind IAHRL is that the low-level policies imagine safe and structured behaviors, and then the high-level policy infers interactions with surrounding objects by interpreting the imagined behaviors. We also introduce a new attention mechanism that allows the high-level policy to be permutation-invariant to the order of surrounding objects and to prioritize our agent over them. To evaluate IAHRL, we introduce five complex urban driving tasks, which are among the most challenging real-world navigation tasks. The experimental results indicate that IAHRL enables an agent to perform safe and interactive behaviors, achieving higher success rates and lower average episode steps than baselines.

Learning shared structures across changing environments enables an agent to efficiently retain obtained knowledge and transfer it between environments. A skill is a promising concept to represent shared structures. Several recent works proposed unsupervised skill discovery algorithms that can discover useful skills without a reward function. However, they focused on discovering skills in stationary environments or assumed that a skill being trained is fixed within an episode, which is insufficient to learn and represent shared structures. In this paper, we introduce a new unsupervised skill discovery algorithm that discovers a set of skills that can represent shared structures across changing environments. Our algorithm trains incremental skills and encourages a new skill to expand state coverage obtained with compositions of previously learned skills. We also introduce a skill evaluation process to prevent our skills from containing redundant skills, a common issue in previous work. Our experimental results show that our algorithm acquires skills that represent shared structures across changing maze navigation and locomotion environments. Furthermore, we demonstrate that our skills are more useful than baselines on downstream tasks.

Although contrastive learning methods have shown prevailing performance on a variety of representation learning tasks, they encounter difficulty when the training dataset is long-tailed. Many researchers have combined contrastive learning and a logit adjustment technique to address this problem, but the combinations are done ad-hoc and a theoretical background has not yet been provided. The goal of this paper is to provide the background and further improve the performance. First, we show that the fundamental reason contrastive learning methods struggle with long-tailed tasks is that they try to maximize the mutual information between latent features and input data. As ground-truth labels are not considered in the maximization, they are not able to address imbalances between classes. Rather, we interpret the long-tailed recognition task as a mutual information maximization between latent features and ground-truth labels. This approach integrates contrastive learning and logit adjustment seamlessly to derive a loss function that shows state-of-the-art performance on long-tailed recognition benchmarks. It also demonstrates its efficacy in image segmentation tasks, verifying its versatility beyond image classification. Code is available at https://github.com/bluecdm/Long-tailed-recognition.

Robotic agents trained using reinforcement learning have the problem of taking unreliable actions in an out-of-distribution (OOD) state. Agents can easily become OOD in real-world environments because it is almost impossible for them to visit and learn the entire state space during training. Unfortunately, unreliable actions do not ensure that agents perform their original tasks successfully. Therefore, agents should be able to recognize whether they are in OOD states and learn how to return to the learned state distribution rather than continue to take unreliable actions. In this study, we propose a novel method for retraining agents to recover from OOD situations in a self-supervised manner when they fall into OOD states. Our in-depth experimental results demonstrate that our method substantially improves the agent’s ability to recover from OOD situations in terms of sample efficiency and restoration of the performance for the original tasks. Moreover, we show that our method can retrain the agent to recover from OOD situations even when in-distribution states are difficult to visit through exploration. Code and supplementary materials are available at https://github.com/SNUChanKim/SeRO.

3D LiDAR is widely used in autonomous systems such as self-driving cars and autonomous robots because it provides accurate 3D point clouds of the surrounding environment under harsh conditions. However, a high-resolution LiDAR is expensive and bulky. Although a low-resolution LiDAR is compact and affordable, the obtained point clouds are so sparse that it is difficult to extract features that are meaningful for highlevel tasks. To solve this problem, several upsampling-based approaches have been proposed by estimating high-resolution point clouds from low-resolution point clouds. However, most works have focused on upsampling object-level or synthetic point clouds obtained from CAD models. Additionally, these approaches have a high computational cost, which makes them unusable in real-time applications such as autonomous driving vehicles. In this paper, we propose a real-time upsampling method with LiDAR for outdoor environments. The proposed method builds on conditional neural processes that are capable of uncertainty quantification. With this probabilistic property, we can remove the upsampled points that have high uncertainty, thus achieving high accuracy. Additionally, the proposed method can be trained in a simulated environment, and then directly applied to the real world. The experimental results on a simulated environment and a real-world dataset show that the proposed method is significantly faster than the state-of-the-art methods while achieving comparable performance.

Many robotic tasks are composed of a lot of temporally correlated sub-tasks in a highly complex environment. It is important to discover situational intentions and proper actions by deliberating on temporal abstractions to solve problems effectively. To understand the intention separated from changing task dynamics, we extend an empowerment-based regularization technique to situations with multiple tasks based on the framework of a generative adversarial network. Under the multitask environments with unknown dynamics, we focus on learning a reward and policy from the unlabeled expert examples. In this study, we define situational empowerment as the maximum of mutual information representing how an action conditioned on both a certain state and sub-task affects the future. Our proposed method derives the variational lower bound of the situational mutual information to optimize it. We simultaneously learn the transferable multi-task reward function and policy by adding an induced term to the objective function. By doing so, the multi-task reward function helps to learn a robust policy for environmental change. We validate the advantages of our approach on multi-task learning and multi-task transfer learning. We demonstrate our proposed method has the robustness of both randomness and changing task dynamics. Finally, we prove that our method has significantly better performance and data efficiency than existing imitation learning methods on various benchmarks.

A highly accurate and robust real-time localization process is crucial for autonomous driving applications. Numerous methods for localization have been proposed, which combine various kinds of input, such as data from environmental sensors, inertial measurement units (IMU), and the Global Positioning System (GPS). Because reliance on a single environmental sensor is a vulnerable approach, the use of multiple environmental sensors is a better alternative. However, the fusion methods from previous studies have not adequately compensated for the drawbacks due to the lack of sensor diversity nor have the methods considered the fail-safe issue. In this paper, we propose a multi-modal fusion-based localization framework that uses multiple map matching sources. The framework contains two independent map matching sources and integrates them in a stochastic situational analysis model. By applying a probabilistic model, the more reliable map matching between the multiple sources is determined and the system stability is verified via a fail-safe action. A number of experiments with autonomous vehicles within actual driving environments have shown that combining multiple map matching sources yield more robust results than the use of a single map matching.

Self-driving baggage tractors on airport ramps or aprons enable better airport operation procedures and support the expansion of the aviation market. Airport ramps have unique mobility requirements in terms of layout, population, demand, and patterns. Avoiding aircraft movement on an airport apron is a top priority because of critical security and safety issues. Existing aircraft detection approaches use remote-sensing images or surveillance cameras. However, these are not compatible with sensors for low-height equipment at airport ramps. Similarly, public road-based self-driving studies have not considered detecting the massive size and concave contours of movable objects. Camera sensors cannot accurately measure the distance of concave contours, whereas a lidar sensor cannot easily cluster or classify an object among point cloud data. In this paper, we present the fusion of cameras and lidar sensors for aircraft and object detection at airport ramps. We use parallel detection from lidar and camera sensors and then integrate both detection results to compensate for any issues. Using the proposed energy optimization model by adapting a conditional random field, we can handle over- and under-segmentation of the point cloud objects caused by the sparse point cloud generated by the aircraft. Our algorithm achieves 31.1% improvement on tracking and 5.5% improvement on classification over other fusion algorithms when applied to a dataset acquired from the Cincinnati and Northern Kentucky airport.

Retrosynthesis is the task of predicting reactant molecules from a given product molecule and is, important in organic chemistry because the identification of a synthetic path is as demanding as the discovery of new chemical compounds. Recently, the retrosynthesis task has been solved automatically without human expertise using powerful deep learning models. Recent deep models are primarily based on seq2seq or graph neural networks depending on the function of molecular representation, sequence, or graph. Current state-of-the-art models represent a molecule as a graph, but they require joint training with auxiliary prediction tasks, such as the most probable reaction template or reaction center prediction. Furthermore, they require additional labels by experienced chemists, thereby incurring additional cost. Herein, we propose a novel template-free model, i.e., Graph Truncated Attention (GTA), which leverages both sequence and graph representations by inserting graphical information into a seq2seq model. The proposed GTA model masks the self-attention layer using the adjacency matrix of product molecule in the encoder and applies a new loss using atom mapping acquired from an automated algorithm to the cross-attention layer in the decoder. Our model achieves new state-of-the-art records, i.e., exact match top-1 and top-10 accuracies of 51.1% and 81.6% on the USPTO-50k benchmark dataset, respectively, and 46.0% and 70.0% on the USPTO-full dataset, respectively, both without any reaction class information. The GTA model surpasses prior graph-based template-free models by 2% and 7% in terms of the top-1 and top-10 accuracies on the USPTO-50k dataset, respectively, and by over 6% for both the top-1 and top-10 accuracies on the USPTO-full dataset.

Curb detection is an essential function of autonomous vehicles in urban areas. However, curbs are difficult to detect in complex urban environments in which many dynamic objects exist. Additionally, curbs appear in a variety of shapes and sizes. Previous studies have been based on the traditional pipeline, which consists of the extraction and aggregation of hand-crafted features that are then fed to classifiers. However, this sequential process is inefficient and designing the hand-crafted features is a complex process. Recently, this kind of process has been replaced by Deep Neural Networks (DNN), in which classifiers and features are learned from large-scale data. Very few works have exploited DNN for the curb detection problem. Most works use multi-modal sensor-based methods that combine images and accumulated 3D point clouds from LIDAR. However, these approaches require synchronization and calibration between sensors. In addition, they do not quantify the uncertainty of their predictions for autonomous system safety. In this paper, we present a two-stage DNN-based curb detection method that includes uncertainty quantification. An autoencoder-based network predicts the curbs, and then conditional neural processes rectify the predictions with uncertainty estimations. The experimental results show that our approach achieves high accuracy and recall in complex areas. We also constructed a large-scale dataset to create benchmarks consisting of approximately 5,224 scans with bird’s-eye view labels collected from urban areas. To the best of our knowledge, there are no public datasets for DNN-based curb detectors. The benchmarks and datasets are publicly available at https://github.com/YounghwaJung/curb_detection_DNN.

Retrosynthesis, of which the goal is to find a set of reactants for synthesizing a target product, is an emerging research area of deep learning. While the existing approaches have shown promising results, they currently lack the ability to consider availability (e.g., stability or purchasability) of the reactants or generalize to unseen reaction templates (i.e., chemical reaction rules). In this paper, we propose a new approach that mitigates the issues by reformulating retrosynthesis into a selection problem of reactants from a candidate set of commercially available molecules. To this end, we design an efficient reactant selection framework, named RetCL (retrosynthesis via contrastive learning), for enumerating all of the candidate molecules based on selection scores computed by graph neural networks. For learning the score functions, we also propose a novel contrastive training scheme with hard negative mining. Extensive experiments demonstrate the benefits of the proposed selection-based approach. For example, when all 671k reactants in the USPTO database are given as candidates, our RetCL achieves top-1 exact match accuracy of 71.3% for the USPTO-50k benchmark, while a recent transformer-based approach achieves 59.6%. We also demonstrate that RetCL generalizes well to unseen templates in various settings in contrast to template-based approaches.

Autonomous vehicles must be able to understand the surrounding traffic flows and predict the future traffic conditions for planning a safe maneuver. During prediction, the action of autonomous vehicles should be considered, as it influences the interaction between vehicles sharing the same traffic scene and thus influences the future traffic flow. From this perspective, not only should the prediction be considered for planning, but also the action of autonomous vehicles generated by planning should be considered for traffic scene prediction. Therefore, prediction and planning must work interactively at every time step, considering results of each other. In this paper, we present a novel learning-based framework that simultaneously forecasts a nearby traffic scene and plans a maneuver of autonomous vehicle at every time step. Through experiments, we demonstrated that the proposed method exhibits better planning performance than baselines in complex traffic conditions involving various surrounding vehicles.

Autonomous driving with imitation learning is vulnerable to the quality of an expert dataset. Typical driving involves situations or online data that are biased toward specific scenarios such as lane following or stop. This property causes an imbalance in the driving dataset, and it is highly likely to deteriorate the performance of autonomous driving with imitation learning. In this paper, we propose a dataset self-balancing system with biased online data and an imbalanced dataset. By estimating the probability distribution of a dataset, we compute the probability and novelty of online data and then filter only qualified novel data. In addition, using the computed probability distribution, we determine the data that are non-informative in the current dataset and then exchange them with novel online data. At last, by retraining the driving neural network with high-entropy data batches, our method achieves incremental driving intelligence. We demonstrated the effectiveness of our method through open-loop evaluation and ablation studies in a CARLA simulator; the results show that our proposed system effectively balances the dataset with 100 scenarios and decreases test loss over time.

Most real-world tasks are compound tasks that consist of multiple simpler sub-tasks. The main challenge of learning compound tasks is that we have no explicit supervision to learn the hierarchical structure of compound tasks. To address this challenge, previous imitation learning methods exploit task-specific knowledge, e.g., labeling demonstrations manually or specifying termination conditions for each sub-task. However, the need for task-specific knowledge makes it difficult to scale imitation learning to real-world tasks. In this paper, we propose an imitation learning method that can learn compound tasks without task-specific knowledge. The key idea behind our method is to leverage a self-supervised learning framework to learn the hierarchical structure of compound tasks. Our work also proposes a task-agnostic regularization technique to prevent unstable switching between sub-tasks, which has been a common degenerate case in previous works. We evaluate our method against several baselines on compound tasks. The results show that our method achieves state-of-the-art performance on compound tasks, outperforming prior imitation learning methods.

How to explore environments is one of the most critical factors for the performance of an agent in reinforcement learning. Conventional exploration strategies such as ε-greedy algorithm and Gaussian exploration noise simply depend on pure randomness. However, it is required for an agent to consider its training progress and long-term usefulness of actions to efficiently explore complex environments, which remains a major challenge in reinforcement learning. To address this challenge, we propose a novel exploration method that selects actions based on their validity. The key idea behind our method is to estimate the validity of actions by leveraging zero avoiding property of kullback-leibler divergence to comprehensively evaluate actions in terms of both exploration and exploitation. We also introduce a framework that allows an agent to explore efficiently in environments where reward is sparse or cannot be defined intuitively. The framework uses expert demonstrations to guide an agent to visit task-relevant state space by combining our exploration strategy with imitation learning. We demonstrate our exploration strategy on several tasks ranging from classical control tasks to high-dimensional urban autonomous driving scenarios at roundabout. The results show that our exploration strategy encourages an agent to visit task-relevant state space to enhance validity of actions, outperforming several previous methods.

Curb detection and tracking is an essential component of autonomous vehicle operation in urban environments. Detecting curbs is a particularly challenging task in urban environments that contain countless dynamic objects. Previous studies have approached curb detection using different types of sensor such as cameras, radar, and LIDAR. Among these, LIDAR sensors have superior advantages in regard to detecting curbs because of their robustness in different weather conditions and they can provide accurate distance measurements. Previous methods based on LIDAR have exploited high-resolution 3D point clouds using high-cost LIDARs. However, the processing of large volumes of information is inefficient for autonomous driving technologies because of real time constraints. This paper presents a novel real-time curb detection and tracking algorithm that makes use of a low-resolution LIDAR. The proposed method consists of three steps. First is the extraction of curb candidates based on Principal Component Analysis (PCA) and Density-Based Spatial Clustering of Applications with Noise (DBSCAN). Second is the selection of the optimal candidate using an optimization framework. Lastly is the tracking of the detected curbs. In the tracking module, we use a combination of spatial consistency and validation gate to track the curb in the occlusion region with dynamic objects. Experiments on a public dataset show that the proposed method achieved 91.54% and 89.76% F1score on the straight and curved road while running at about 18 ms per frame, thereby outperforming the state-of-the-art by a large margin. In addition, we integrated the proposed method with the localization module of our autonomous driving platform. The localization module integrated with the proposed method reduces the positional and lateral root mean square (RMS) error of the vehicle localization by 3.58% and 6.68% respectively. In addition, we compare this method with a deep neural network based method from the perspective of a safety-critical system such as self-driving cars.

While object tracking for 3D point clouds has been widely researched in recent years, most trackers employ a direct point-to-point matching method under the assumption that target object clouds are dense, although the method is not suitable for sparse point clouds. In this paper, we introduce a novel object-tracking strategy that enables even sparse point clouds to be tracked properly. The strategy involves estimating distributions, called as Estimation of Vertical Distributions (EVD), by the proposed interpolation method to augment data and by a point-to-distribution matching technique. The EVD step generates vertical distributions of unoccupied areas on a target object using the distributions of the occupied areas and then seeks the optimal solution through a coarse-to-fine grid search to guarantee real-time performance. In order to verify the proposed tracking algorithm, we have tested our tracker on real world data collected by our own platform, and the results have demonstrated that the tracker outperforms other trackers.

Highly accurate and robust real-time localization is an essential technique for various autonomous driving applications. Numerous localization methods have been proposed that combine various types of sensors, including an environmental sensor, IMU and GPS. However, the usage of a single environmental sensor is rather fragile. Although the use of multi-environment sensors is a better alternative, fusion methods from previous studies have not adequately compensated for shortcomings in dissimilar sensors or have not considered errors in the pre-built map. In this paper, we propose a decentralized localization framework using heterogeneous map-matching sources. Decentralized localization performs two independent map-matchings and integrates them with a stochastic situational analysis model. By applying a stochastic model, the reliability of the two map matchings is collected and system stability is verified. A number of experiments with autonomous vehicles within the actual driving environment have shown that combining multiple map-matching sources ensures more robust results than the use of a single environmental sensor.

Over the last decade, automated vehicles have been widely researched and their massive potential has been verified through several milestone demonstrations. However, there are still many challenges ahead. One of the biggest challenges is integrating them into urban environments in which dilemmas occur frequently. Conventional automated driving strategies make automated vehicles foolish in dilemmas such as making lane-change in heavy traffic, handling a yellow traffic light and crossing a double-yellow line to pass an illegally parked car. In this paper, we introduce a novel automated driving strategy that allows automated vehicles to tackle these dilemmas. The key insight behind our automated driving strategy is that expert drivers understand human interactions on the road and comply with mutually-accepted rules, which are learned from countless experiences. In order to teach the driving strategy of expert drivers to automated vehicles, we propose a general learning framework based on maximum entropy inverse reinforcement learning and Gaussian process. Experiments are conducted on a 5.2 km-long campus road at Seoul National University and demonstrate that our framework performs comparably to expert drivers in planning trajectories to handle various dilemmas.

In driving environments, other vehicles are one of the most frequently appearing close range objects from the ego-vehicle. Thus, the development of high accuracy vehicle recognition algorithms is essential for safe and efficient automated driving. However, detecting vehicles with consistently high accuracy is difficult because there are various vehicle types with different appearances, such as sedans, buses, trucks, and SUVs. This intra-class variation must be addressed or, irregular recognition performance can occur, depending on vehicle type. Conventional machine learning-based algorithms are inadequate to address this problem because they are mostly trained on samples of entire appearance. Considering the wide variability in vehicle appearance, collecting samples of every vehicle type may not be ideal. In this study, we propose a vehicle recognition algorithm using common appearance characteristics of every vehicle type. Rectangular shapes are captured by a 3D LIDAR while tires and bumpers are captured by a monocular camera. Angular features extracted from these common appearances are then fused by the Dempster-Shafer theory framework for vehicle recognition. By performing real-world experiments, we demonstrated that common appearances captured by the proposed algorithm provide sufficiently generalized features to recognize diverse vehicle types in urban driving environments.

In this paper, we present a driverless taxi system for autonomous campus mobility services. College campuses have unique mobility requirements in terms of layout, population, and demand and patterns. It is typically recommended to minimize the presence of private automobiles on campuses due to teaching and research disturbances, visual degradation from parking provision, environmental pollution, and negative health effects. As an alternative to private automobiles, shared mobility systems have been considered for both campus and urban transportation. Conventional shuttle systems suffer from the first and last mile problem. A bicycle and pedestrian friendly policy is not a generalizable solution for all geographic locations and campus layouts. We suggest a driverless taxi service as an alternative point-to-point shared mobility system for campuses. We have demonstrated the feasibility of this service on a 4.5-km campus road at Seoul National University. The service has covered over 10 000 km autonomously since the first public demonstration was made in November 2015.

In LIght Detection And Ranging (LIDAR)-based object detection, accurate object segmentation is of great importance, since segmentation is an essential preprocessing step for other perception tasks, such as classification and tracking. For segmenting objects, most of the previous methods have tried to eliminate the ground first, which typically incurs considerable overhead in computation and inaccuracy in object detection with point clouds gathered by using 3-D LIDARs. However, in many real-time applications, such as automated driving, segmentation should be performed within a specified time, because even a small delay in computation could result in vehicle collisions. In this paper, we propose a real-time and accurate object segmentation algorithm for 3-D point clouds, which does not carry out ground extraction as a first step. In the proposed algorithm, we generate candidate points of objects and find their borders based on the integrated structure of a 2-D grid and an undirected graph, which enables fast processing and yields an accurate segmentation result independent of ground extraction error. In order to enhance segmentation accuracy, we employ Gaussian process, which reduces over-segmentation that separates an object into multiple portions. We apply two types of Gaussian process models to alternately provide cues for merging adjacent over-segmented objects. Experimental results demonstrate that this paper achieves a real-time processing speed and higher segmentation accuracy than previous works in most evaluation metrics. With the application to tracking, we show that the enhanced segmentation accuracy increases the tracking accuracy by 11.4% even in the worst case.

As the around-view monitoring (AVM) system becomes one of the essential components for advanced driver assistance systems (ADAS), many applications using AVM such as parking guidance system are actively being developed. As a key step for such applications, detecting road markings robustly is a very important issue to be solved. However, compared to the lane marking detection methods, detection of non-lane markings, such as text marks painted on the road, has been less studied so far. While some of methods for detecting non-lane markings exist, many of them are restricted to roadways only, or work poorly on AVM images. In this paper, we propose an algorithm which can robustly detect non-lane road markings on AVM images. We first propose a difference-of-Gaussian based method for extracting a connected component set, followed by a novel grouping method for grouping connected components based on convexity condition. For a classification task, we exploit the Random Forest classifier. We demonstrate the robustness and detection accuracy of our methods through various experiments by using the dataset collected from various environments.

Parking slot detection algorithms using visual sensors have been required for various automated parking assistant systems. In most previous studies, popular feature detectors, such as the Harris corner or the Hough line detector, have been employed for detecting parking slots. However, these algorithms were originally designed to find distinct features and are inadequate for the short, curvy, faint and distorted parking-lines of long-range surround-view images, especially in around-view monitoring systems. In this paper, we propose a robust parking slot detection algorithm based on the line-segment-level clustering method. The proposed algorithm consists of line-segment detection with the proposed Directional-DBSCAN line-level feature-clustering algorithm and slot detection with slot pattern recognition. In comparison to other feature detectors, we show that the Directional-DBSCAN algorithm robustly extracts lines even when they are short and faint. Moreover, we verify that the parking-slot detection algorithm with pattern recognition can be applicable to diverse slot types and environments with experiments on abundant dataset.

Accurate lateral localization of an ego-vehicle is one of the core technologies for autonomous driving. Conventional approaches have utilized GPS data, pre-built map information, and lane detection results to estimate the lateral location of an ego-vehicle. However, these approaches demonstrate several performance limitations due to inaccurate data from GPS, high costs for building and maintaining maps, and insufficient visual cues for handling various tasks in diverse driving environments. In this paper, we propose an accurate ego-lane recognition framework that utilizes multiple evidence from visual processing upon the theory of the Bayesian Network to overcome these limitation. We show that more accurate and reliable lateral localization results can be achieved by combining several visual cues, which increases confidence and reliability of the results. We also show that our approach can be applicable to various driving environments without maps because the framework analyzes multiple context information of driving environments simultaneously. We verify the robustness of our algorithm in various driving scenarios such as highways and wide/narrow urban roadways.

Multi-lane detection algorithms have been required for various vehicle safety-related applications. In most of the previous study, visual features are fundamental clues for multi-lane detection. However, since visual features vary with the illumination, weather condition and distance of the region, feature-based algorithm is restricted to the illuminant variation and laterally adjacent regions. On the other hand, conventional geometric estimation-based approaches, not relying on visual features, are inaccurate and susceptible to pitch or lateral movement. In this paper, we propose a robust multi-lane detection algorithm based on the accurate geometric estimation in highway scenarios. With the steps of adjacent lanes hypothesis generation (HG) and hypothesis verification (HV), the algorithm detects successfully independent of environmental changes. For accurate adjacent lane HG, we adopt the ‘cross ratio’ and propose ‘dynamic homography matrix estimation.’ Our approach is independent of the calibration, pitch angle changes and additional vehicle sensors. In addition, the proposed algorithm can covers six lanes including the driving lane and adjacent lanes that two-lanes away from the driving lane. We demonstrate robustness on the illumination variance including daytime, rainy and sunset by using trough simulations and video sequences with a resolution of 752 × 480.

Group key management (GKM) in mobile communication is important to enable access control for a group of users. A major issue in GKM is how to minimize the communication cost for group rekeying. To design the optimal GKM, researchers have assumed that all group members have the same leaving probabilities and that the tree is balanced and complete to simplify analysis. In the real mobile computing environment, however, these assumptions are impractical and may lead to a large gap between the impractical analysis and the measurement in real-life situations, thus allowing for GKM schemes to incorporate only a specific number of users. In this paper, we propose a new GKM framework supporting more general cases that do not require these assumptions. Our framework consists of two algorithms: one for initial construction of a basic key-tree and another for optimizing the key-tree after membership changes. The first algorithm enables the framework to generate an optimal key-tree that reflects the characteristics of users’ leaving probabilities, and the second algorithm allows continual maintenance of communication with less overhead in group rekeying. Through simulations, we show that our GKM framework outperforms the previous one which is known to be the best balanced and complete structure.

Over the past few decades, the need has arisen for multi-lane detection algorithms for use in vehicle safety-related applications. In this paper we propose a new multi-lane detection algorithm that works well in urban situations. This algorithm detects four lane marks, including driving lane marks and adjacent lane marks. Conventional research assumes that lanes are parallel. In contrast, our approach does not require this assumption, thus enabling the algorithm to manage various non-parallel lane situations, such as are found at intersections, in splitting lanes, and in merging lanes. To detect multi-lane marks successfully in the absence of parallelism, we adopt Conditional Random Fields (CRFs), which are strong models for solving multiple association tasks. We show that CRFs are very effective tools for multi-lane detection because they find an optimal association of multiple lane marks in complex and challenging urban road situations. Through simulations, and by using video sequences with 752-480 resolution and Caltech Lane Datasets with runtime rates of 30 fps, we verify that our algorithm successfully detects non-parallel lanes as well as parallel lanes appearing in urban streets.

In this study, the authors propose a new multi‐pattern matching algorithm, called BLAST (B‐LAyered bad‐character Shift Tables with a single‐byte search unit), which considers space‐time tradeoff in the context of shift values during the search. Here, the term ‘bad character’ is a character that causes a mismatch. While checking multiple bytes in scanning the text at a time, the BLAST algorithm overcomes the reduction of the average shift value in a typical search, which is caused by the dependency on the multi‐byte search unit (MBSU) and the large frequency of the last character of the given patterns. From the theoretical analysis, the authors validate the correctness of the BLAST algorithm. Also, from the experimental results across different setups, the authors show that the BLAST algorithm provides the faster search time than the other algorithms. For example, the authors obtain an enhancement by as much as 212.41% on average for various numbers of attack patterns and attack traffic conditions compared with that of the modified Wu‐Manber algorithm. In addition, it is shown that the BLAST algorithm drastically reduces the amount of memory required for constructing the shift table based on a MBSU from 64 KB to 1 KB.

Vehicle localization algorithms aim to provide an accurate location estimation of neighbor vehicles for critical applications in intelligent vehicles. For the initial location estimation, localization algorithms use either Global Positioning System (GPS), radio-based lateration techniques, or both. These techniques suffer from three major issues, namely, flip ambiguities, location information exchange (beacon) overhead, and forged relative location information. The accuracy of these algorithms at the early iterations is primarily affected by flip ambiguities, which in turn result in erroneous initial location estimates. The errors from flip ambiguities are a monotonically increasing function of time and propagated to the subsequent iterations to build an erroneous neighbor-vehicle map. In this paper, we propose a novel GPS-free neighbor-vehicle mapping framework that provides reliable initial relative position estimates of neighbor vehicles and mitigates aforementioned issues. This framework uses presence/absence status information of neighbor vehicles in binary form from a vision-based environment sensor system to associate each vehicle's cardinal location with its identification information, such as media access control (MAC)/Internet Protocol addresses. We represent a vehicle's neighborhood region and neighborhood topology using the Moore neighborhood (MN) and King's graph (KG), respectively, by analyzing a typical vehicle formation in a multilane roadway. We also introduce a KG-based neighborhood information overlap measure (IOM) algorithm for neighbor mapping by exploiting the perspective symmetric properties of the MN. Performance analysis and simulation results show that the proposed algorithm builds an accurate relative neighbor-vehicle map and outperforms trilateration- and multilateration-based methods in mitigating flip ambiguities and location information exchange overhead.

With the emergence of diverse group-based services, multiple multicast groups are likely to coexist in a single network, and users may subscribe to multiple groups simultaneously. However, the existing group key management (GKM) schemes, aiming to secure communication within a single group, are not suitable in multiple multicast group environments because of inefficient use of keys, and much larger rekeying overheads. In this paper, we propose a new GKM scheme for multiple multicast groups, called the master-key-encryption-based multiple group key management (MKE-MGKM) scheme. The MKE-MGKM scheme exploits asymmetric keys, i.e., a master key and multiple slave keys, which are generated from the proposed master key encryption (MKE) algorithm and is used for efficient distribution of the group key. It alleviates the rekeying overhead by using the asymmetry of the master and slave keys, i.e., even if one of the slave keys is updated, the remaining ones can still be unchanged by modifying only the master key. Through numerical analysis and simulations, it is shown that the MKE-MGKM scheme can reduce the storage overhead of a key distribution center (KDC) by 75 percent and the storage overhead of a user by up to 85 percent, and 60 percent of the communication overhead at most, compared to the existing schemes.

The dynamics of multi-agent in nature have been largely studied for a long time to investigate how the aggregation of agents can move smoothly in complex environments without collision. The main insights can be summarized such that the aggregated dynamics of animals and particles can be explained by an individual's simple rules. In a similar vein, we conjecture that such simple rules for vehicle maneuvering can accommodate the fluid flow of traffic and reduce car accidents in highway and urban areas. In this paper, we first show the Reynolds' three rules are applicable to autonomous driving on a single lane. Moreover, we provide additional requirements and algorithms for multiple lanes. Based on these results, we show that the proposed nature-inspired driving maneuver can increase traffic flow by 1) mitigating shockwave at bottlenecks and 2) extending the perception range for better path planning, which requires the support of the vehicle autonomy and wireless communication, respectively. Finally, we prove the feasibility of our work with experiments using multiple UAVs.

Beyond the individual independent unmanned autonomous vehicle (UAV), cooperative control of multiple UAVs has started to receive significant attention from industry, academia and the military. For the sake of UAV cooperation, proper wireless communication is imperative, but incurs several problems. Among them, spatially secure group communication (SSGC), which must maximize spatial UAV group size while minimizing the communication boundary of the group, is a unique problem for multiple UAV control from a security perspective. In particular, the SSGC problem must be considered for military applications such as multiple unmanned aerial or ground vehicle control. In this paper, we investigate the SSGC problem. To provide a solution, an analytical framework is first presented to model the dynamics of multiple UAVs and SSGC. The theoretical analysis and simulation results regarding how communication affects group dynamics and spatial communication security are also discussed. Our contribution is to suggest a new way to view multiple UAV control with spatially secure communication, and to provide a distributed method to address the problem cooperatively.

Although lots of research efforts have focused on group key management (GKM) for secure multicast, existing GKM schemes are inadequate for vehicle communication (VC) systems since they incur unnecessary rekeying overhead without considering the characteristics of VC systems such as Vehicle-to-Infrastructure communications and a great number of high mobility vehicles. Therefore, we propose a GKM scheme, called RSU-based decentralized key management (RDKM), dedicated for the multicast services in the VC systems. The RDKM scheme significantly reduces the rekeying overhead through delegating a part of the key management functions to the road-side infrastructure units (RSUs) and through updating the key encryption keys (KEKs) within a RSU. The performance of the RDKM scheme is analyzed in terms of communication overhead and storage overhead each of which has a strong impact on the performance of GKM. Furthermore, we propose an optimization algorithm that minimizes the weighted sum of the communication and the storage overhead, called the GKM overhead (GKMO), by appropriately determining the design parameters. The numerical results from the extensive analysis demonstrate that the RDKM scheme outperforms the existing GKM schemes in terms of the GKMO.

In group communications, an efficient rekeying scheme plays a key role in providing access control when a membership change happens. For reducing the communication cost in the rekeying operation, one proposed model is to rekey upon individual membership change. It is theoretically proved that given the forward secrecy requirement, the optimal amortized communication cost is at least O(log n) (n is the group size) for an Individual Rekeying (IR). Another model is to rekey upon a batch of multiple membership changes: Batch Rekeying (BR), which largely reduces the rekeying communication cost, and relieves implementation difficulties in the IR model (e.g., extremely intensive rekey messages and key arriving disorders in large-size and highly dynamic groups). Unlike IR, however, the communication lower bound in BR is not yet explicitly stated. This paper first extends the communication lower bound for IR to the BR model. Specifically, we prove that given the batch level forward secrecy, the communication costs for updating the whole group subset by subset in a sequence of b batch rekeyings are at least O(b · (log2b - 1)) + O(n). This bound, as a superset, inclusively explains the IR bound as a special case of b = n. Second, for achieving the found bound, we provide a departing-time related key topology that works optimally under the bound. Third, to further implement the proposed optimal topology, we propose two novel BR protocols, one with support of forward secrecies and the other with support of two-way secrecies. Through extensive analyses and simulations, the proposed protocols are shown to achieve notable upgrades in major performance metrics: 60% ~ 70% reduction in communication overheads, 50% ~ 60% reduction in key storage overheads, and elimination of key tree unbalance.

Control networks are widely deployed on mass produced mobile systems such as automotive systems, airplanes, and mobile robots. Previous works on control networks have focused on guaranteeing controllability, predictability, and dependability in the time domain because control networks manipulate actuators directly, and hence are highly related to safety. However, in contrast to data networks, control networks severely affect the manufacturing cost, fuel efficiency, and space effectiveness of mobile systems due to additional network devices, control unit (CU) arrangements, and task assignments. These problems have become more important as CUs have been extensively deployed in real systems in the pursuit of intelligence and energy efficiency. Therefore, system design using control networks must be considered with respect to the time and space domains simultaneously. We propose a design method to minimize space resources due to control networks in the target system while satisfying time constraints. We formulate this problem as a matching problem and provide an effective solution. Through extensive simulations, we demonstrate that our methodology is very effective and scalable, and saves significant time, space, and cost in control networks.

Epidemic malicious codes including Internet worms and botnets have continuously evolved to be more intelligent and complicated. In particular, the recent distributed denial-of-service (DDoS) attack that occurred in United States and South Korea in July, 2009 gives an opportunity to reconsider the epidemic malicious code. Since automatic patching systems and intelligent intrusion detection and prevention systems mitigate rapid infection, fast infections such as Slammer-like worms cannot successfully spread. As of the 2009 July DDoS attack, malicious codes prefer hiding their malicious activities and trying to infect others silently until D-day. Since slow infection is difficult to detect by the current IDS or IPS, this infection strategy is likely to become prevalent. In a slow infection, the incubation period is a key factor in determining the extent to which an epidemic malicious code spreads. This study provides an analysis framework to understand the impact of incubation period in the spread of epidemic malicious code. Intuitively, a longer latent period increases the number of infected hosts, but the detection probability also increases. This trade-off suggests an optimal incubation period determination problem to maximize the number of infected hosts. Solving this problem is essential to predicting the explicit or implicit intention of attackers and to counteract against the attack in a strategic manner. Through analysis and simulations, we provide data and insight regarding epidemic malicious code that exploits incubation period.

A logical key hierarchy (LKH) based key managementapproach is the most common way to manage a group keywith less rekeying overhead. However, the LKH approach causes inefficiency of rekeying the group key in mobile cellular networks since it does not consider the characteristics of the networks, such as the cell-based network topology and the user's mobility. This paper proposes an efficient and practical group key management scheme dedicated to the mobile cellular networks. This new approach can achieve better performance with less management overhead than other currently available schemes, by the cell-based decentralization of key management functions. Through comparisons with other possible approaches, it is shown that the proposed scheme can obtain much better performance in terms of the communication overhead.

To achieve both access control and service availability, many researchers have attempted to design an efficient key management system for secure multicast services. Periodic and batch rekeying (PBR) is well known for its significant improvement in rekeying efficiency for large-scale and highly dynamic groups at the cost of relaxing some forward secrecy. However, PBR is uncontrollably vulnerable in its worst case when departing users are uniformly distributed in the leaf level of the key tree. Given a lack of users' departure information, the system cannot efficiently plan for their accommodations in the key tree. We observe that in many applications, e.g. charge-by-duration services, users' departure information is accessible to the system when it joins the group. In this paper, we exploit the value of this information, and propose a novel time-based key management scheme called "departure-aware key tree structure" (DAKS). We employ a tree-star combined topology to schedule the key updates in DAKS. Using knowledge of departing times, our scheme can achieve high efficiency for batch rekeying. Specifically, we show through analyses and simulation that by applying our scheme, rekeying efficiency can be improved by approximately 50%~60% with less key storage overhead and no other side effects.

In this paper, we propose a novel load-balancing scheme for the Birkhoff-von Neumann input-queued (BvN-IQ) switch, which we call the cyclic exchange. According to the cyclic exchange scheme, in each time slot each linecard transfers a cell from its non-empty VOQ to the empty VOQ of another linecard which is destined for the same output. In order to guarantee the cell sequence in this procedure, we propose a simple rule of selecting the cells to be transferred for load balancing, and prove the sequence guarantee by the proposed rule. Since the cyclic exchange is performed locally between two linecards, its communication and computation overhead is not too heavy to implement. To be specific, the communication overhead of the proposed scheme is the transmission of N bits and its computation overhead corresponds to a priority encoder with a fixed highest priority. The simulation results show that the proposed scheme achieves 100% throughput asymptotically and shorter delay than the two-stage switch.

In this paper, we present an accurate throughput model of the IEEE 802.11e enhanced distributed coordination function (EDCF). Compared to the previous models, we newly consider a delay bound by predicting an effective retry limit and applying the retry limit to our model. To support this, the accurate description of the performance in a non-saturation condition is necessary, which is achieved by newly considering a queue length and a queue limit in the Markov chain. Simulation results show that our model is accurate in predicting the system throughput.

The wireless mesh network is emerging as a promising technology in providing economical and scalable broadband Internet accesses to communities. The backbone of the wireless mesh network consists of mesh routers, which connect each other in an ad hoc manner via wireless links. The presence of backbone mesh routers and utilization of multiple channels and interfaces allow the wireless mesh network to have better capacity than that of the infrastructure-free ad hoc network formed by mesh clients directly. A special type of the mesh routers, referred to as gateway nodes, is capable of Internet connection, and other mesh routers and associated terminal clients have to access the Internet through the gateway nodes. In this paper, we present the analytically traceable stochastic models to characterize the average delay and throughput performance in wireless mesh networks. We model the forwarding mesh routers as an open queuing network. The analytical model takes into account the mesh router density, the random packet arrival process, the degree of locality of traffic and the collision avoidance mechanism of the IEEE802.11 DCF random access MAC. Our simulation results suggest that the analytical results are quite accurate, which can provide valuable insights in system performance and an effective guideline for the scalable design and optimization in wireless mesh networks.

A signature-based network intrusion detection system (NIDS) identifies intrusions by comparing the data traffic with known signature patterns. In this process, matching of packet strings against signature patterns dominates the overall system performance. The MWM algorithm has been known as the fastest pattern matching algorithm when the patterns in a rule set rarely appear in packets. However, the matching time does not decrease if the length of the shortest pattern in a signature group is too short. In this paper, by extending the length of the shortest pattern, we minimize the pattern matching time of the algorithm which uses multi-byte unit. For example, when the length of the shortest pattern is less than 5, the proposed algorithm shows 38.87% enhancement in average.

In this paper, we consider time-and-frequency hopping (TFH) codes for optical code-division multiple-access (OCDMA) networks. To support the differentiated service requirements for multimedia data transmission, we propose two- dimensional TFH codes with arbitrary cross-correlation constraints. Using the proposed codes, we can increase the cardinality of the codes compared to the conventional OCDMA codes whose cross-correlation value is usually confined to at most one. To design a TFH code that can support differentiated requirements on bit error rates (BERs), we propose an efficient construction method which can generate TFH code sequences with hierarchical cross-correlation constraints. The cardinality bound of the proposed codes with mixed cross-correlation constraints is also derived. From the numerical results, we demonstrate that the proposed codes can obtain relatively differentiated BER performances by providing hierarchical constraints on the cross- correlation values.

The wavelength-division-multiplexing (WDM) optical packet switches (OPSes) using wavelength converters (WCs) have been focused to improve the optical network performance significantly. Among them, a shared-per-node (SPN) switch architecture has been considered as a way to utilize WCs efficiently. In this paper, we propose a new switch control algorithm for the architecture, which reduces the total number of wavelength conversion degree (WCD) of a wavelength converter block (WCB). The algorithm also reduces the number of WCs with higher WCD while minimizing the packet loss by wavelength contention at outbound links. Based on this algorithm, we then design a flexible WDM OPS architecture. The proposed algorithm, different from the previous works, focuses on using the heterogeneous wavelength converter blocks (HeWCBs), where a HeWCB consists of WCs with different WCD. The proposed HeWCBs are motivated by the observation that the conventional WDM OPS architecture seldom uses long-range convertible WCs. The architecture shows the same packet loss probability as that of the homogeneous WCBs (HoWCBs) consisting of WCs with the same WCD. Through analysis and simulation, it is shown that the WDM OPS architecture using a combination of WCs of WCD less than or equal to d achieves the same performance as using HoWCBs with WCs of WCD d.

In this paper, we propose a novel load-balancing scheme for two-stage switches which does not disturb the sequence of packets. The proposed scheme uses chamber queues(CQs) in front of the second crossbar fabric as well as VOQs in front of the first crossbar. A chamber queue is composed of N banks each of which can store only one packet destined for each output. The two crossbar fabrics in the proposed switch are configured by a deterministic sequence of N connection patterns as in other two-stage switches. In a time slot, the proposed switch transfers packets from non-empty VOQs to the corresponding empty banks of CQs via the first crossbar, and the packets from CQs are switched to their destinations via the second crossbar. While the proposed scheme is very simple, it can achieve 100% throughput under not only uniform but also non-uniform traffic. Moreover, the simulation results show that the average delay of packets in the proposed two-stage switch is lower than that in the original two-stage switch.

Blocking probability is the most widely used performance metric for the design and the dimensioning of wavelength-routed WDM networks. In this paper, we study the blocking performance of such networks under two heterogeneities: traffic heterogeneity and configuration heterogeneity. The former means that different sessions may have different kinds of traffic, and the latter that different nodes and links may have different wavelength conversion capabilities and different number of optical fibers in use, respectively. We also investigate how these heterogeneities impact on the blocking performance of such networks. To achieve these goals, we present a dedicated analytical model for each heterogeneity. First, we present two single-link models for estimating the arrival-point wavelength occupancy distribution on a link with heterogeneous traffic: the FP model and the RP model. Both models are based on the BPP/M/C/C model in which the first two moments of an arbitrary session are matched by those of a birth-death process whose arrival rate linearly varies with the average number of busy wavelengths occupied by its own calls. Next, we derive two recurrence formulas to estimate the number of free wavelengths on a multi-fiber link and the number of free wavelengths after limited-range wavelength conversion. We also present a comprehensive analytical framework for estimating the blocking performance of WDM networks in the presence of both heterogeneities. From the numerical results, we demonstrate that our model is highly accurate in evaluating the blocking probability for a wide range of the heterogeneities discussed above.

In this paper, we propose a new generation algorithm of multi-length time-and-frequency-hopping codes for the optical code-division multiple access network. The generation algorithm is more flexible compared to the conventional multi-length code generation algorithms, and thus can provide more sophisticated multimedia service differentiation with respect both to the transmission rate and bit error rate (BER). As a way to differentiate the multi-length codes for multiple service classes, we show that the ratio of the BER performance between any two service classes can be approximated by the ratio of the code weights independent of code lengths under high user population. We also present the performance results under various conditions to demonstrate the differentiation of services classes with respect to BER and packet delay.

Two asymmetric mechanisms are often employed in large-scale systems to achieve scalable and efficient authenticated broadcast. However, cryptographic asymmetry based on public-key schemes is computationally expensive, while time asymmetry based on delayed-key release requires time synchronization cross the entire network and temporal buffering of messages at receivers. Neither approach is suitable for large-scale sensor networks composed of computation and storage constrained low-end sensor nodes. In this paper, we propose novel flooding authentication mechanism based on our "information asymmetry" model. Our design is built on top of symmetric cryptography for computation efficiency, and leverages the asymmetric key distribution between the sink and sensor nodes. Through intensive analysis we demonstrate optimized tradeoff between the resilience to compromised sensor nodes and the scalability to system size through space-efficient bloom filters as the authenticator. With a novel "false negative" tuning knob introduced in the construction of bloom filter, we show that the scalability of the authentication primitive can be greatly improved at the cost of small controlled degradation of security, therefore rendering a practical authenticated flooding for large-scale sensor networks.

We show that the multiple input/output-queued (MlOQ) switch proposed in our previous paper H. I. Lee and S. W. Seo (May 2003) can emulate an output-queued switch only with two parallel switches. The MIOQ switch requires no speedup and provides an exact emulation of an output-queued switch with a broad class of service scheduling algorithms including FIFO, weighted fair queueing (WFQ) and strict priority queueing regardless of incoming traffic pattern and switch size. First, we show that an N /spl times/ N MIOQ switch with a (2, 2)-dimensional crossbar fabric can exactly emulate an N /spl times/ N output-queued switch. For this purpose, we propose the stable strategic alliance (SSA) algorithm that can produce a stable many-to-many assignment, and then apply it to the scheduling of an MIOQ switch. Next, we prove that a (2, 2)-dimensional crossbar fabric can be implemented by two N /spl times/ N crossbar switches in parallel for an N /spl times/ N MIOQ switch. For a proper operation of two crossbar switches in parallel, each input-output pair matched by the SSA algorithm must be mapped to one of two crossbar switches. For this mapping, we propose a simple algorithm that requires at most 2N steps for all matched input-output pairs. In addition, to relieve the implementation burden of N input buffers being accessed simultaneously, we propose a buffering scheme called redundant buffering which requires two memory devices instead of N physically-separate memories.

In this paper, we study a practical approach to match the performance of an output-queued switch statistically. For this purpose, we propose a novel switching architecture called a multiple input/output-queued (MIOQ) switch that requires no speedup for providing sufficient switching bandwidth. To operate an MIOQ switch in a practical manner, we also propose a multi-token-based arbiter which schedules the switch at a high operation rate and a virtual FIFO queueing scheme which guarantees the departure order of cells belonging to the same traffic flow at output. Additionally, we show that the proposed switch can naturally provide symmetric bandwidth for dealing with the links with different bandwidth demands. Finally, we compare the performance of an MIOQ switch with that of an output-queued switch and discuss the design criteria to match the performance of an output-queued switch.

We study a practical approach to match the performance of an output-queued switch statistically. For this purpose, we propose a novel switching architecture called a multiple input/output-queued (MIOQ) switch that requires no speedup for providing sufficient switching bandwidth. To operate an MIOQ switch in a practical manner, we also propose a multitoken-based arbiter which schedules the switch at a high operation rate and a virtual first-in first-out queueing scheme which guarantees the departure order of cells belonging to the same traffic flow at output. Additionally, we show that the proposed switch can naturally provide asymmetric bandwidth for inputs and outputs, which may be important in dealing with the links with different bandwidth demands. Finally, we compare the performance of an MIOQ switch with that of an output-queued switch and discuss the design criteria to match the performance of an output-queued switch.

We investigate multiwavelength optical orthogonal codes (MWOOCs) for optical code-division multiple access. Particularly, we present a new construction method for (mn,/spl lambda/+2,/spl lambda/) MWOOCs with the number of available wavelengths m, codeword length n, and constant Hamming weight /spl lambda/+2 that have autocorrelation and cross-correlation values not exceeding /spl lambda/. In the proposed scheme, there is no constraint on the relationship between the number of available wavelengths and the codeword length, and it is also possible to use an arbitrary /spl lambda/. We show that the constructed code is optimal, especially for /spl lambda/=1. Finally, we analyze the bit error rate of the new code and compare it with that of other optical codes.

We propose a new generation algorithm for frequency-hopping optical orthogonal codes (FH-OOC). The new algorithm generalizes the conventional FH-OOCs by considering the time blank patterns between two adjacent symbols. We show that it can generate more available codes than the previous algorithm which does not consider the effect of time blank patterns. We also derive the upper bound of the new code set. We conduct the performance analysis by considering the interference from unwanted frequency components, and compare the bit error rate of the new codes with those of other code sets in various cases.

We propose a heuristic wavelength routing algorithm for IP datagrams in WDM networks which operates in a distributed manner. We first present an efficient construction method for a loose virtual topology with a required connectivity property, which reserves a few wavelengths to cope with dynamic traffic demands properly. We then develop a high-speed distributed wavelength routing algorithm adaptive to dynamic traffic demands and derive the general bounds on average wavelength utilization in distributed wavelength routing algorithms. Finally, through simulation, it is shown that our algorithm is efficient enough to be used in distributed WDM networks in terms of the blocking performance, control traffic overhead, and computational complexity.

We deal with the problem of establishing a lightpath in a multihop manner under physical constraints. We provide both minimal-cost and heuristic algorithms for locating signal regeneration nodes (SRNs). For a minimal-cost algorithm, we formulate the problem using dynamic programming (DP) such that blocking of other lightpaths due to the lack of transmitters/receivers (TXs/RXs) and wavelengths is minimized throughout the network. The blocking performances of several algorithms are compared with one another in a ring.

In this paper, we investigate the performance characteristics of parallel switching architectures constructed by a stack of multistage switching networks. First, we propose a general analysis model which describes two directional traffic flows with a traffic-distribution characteristic. By applying this model to an MBCP (multiple banyan connected in parallel) switch, we show that the traffic-distribution characteristic plays an important role for the accuracy of a performance model. Next, to verify the accuracy of our approach to model the parallel switching architecture with a traffic-distribution capability, we select and analyze the WGSN (weaved generalized shuffle network) which is based on a multihop switching architecture. From the comparison with simulation results, we show that the developed model accurately predicts the performance of a WGSN under the assumption that the traffic-distribution characteristic is uniform.

Although designing a virtual topology for all-optical WDM wide-area networks has been extensively studied and several algorithms have been proposed, these algorithms assume error-free communication between two nodes. However, noises from optical amplifiers and optical cross-connects can degrade the signal, resulting in a nonzero bit-error rate. In this paper, we investigate the effect of physical limitations on the virtual topology design. We show that for wide-area all-optical networks where transmission distance is fairly long, virtual topology design algorithms must take physical limitations into account to ensure a low bit-error rate. We also propose a heuristic algorithm that can determine the locations of opto-electronic (OE) and electro-optic (EO) conversions to set up a connection request with a high BER in a multihop manner.

In this paper, we analyze ways of realizing permutations in a class of 2log/sub 2/N- or (2log/sub 2/N-1)-stage rearrangeable networks. The analysis is based on the newly developed inside-out routing algorithm and we derive the upper and lower bounds on the number of possible realizations of a permutation. It is shown that the algorithm can provide us with comparable degrees of freedom in realizing a given permutation as the well-known looping algorithm, while it can be more generally applied to a class of 2log/sub 2/N- or (2log/sub 2/N-1)-stage rearrangeable networks. In finding a set of complete assignments for the center-stage cycles, alternate realizations of a permutation can be obtained by changing the initial position, changing the assigning direction, or even interchanging the first-level decompositions of the permutation. We also show that these numerable alternate realizations can be utilized to make the networks tolerate some sets of faults, i.e., control faults of SEs including stuck-at-straight and stuck-at-cross. Various cases of single control faults at the center stages and other stages are examined through examples. These new approaches originate from routing outward from center stages to outer stages; therefore, the center stages and two half networks may be treated separately.

A new multipath multistage interconnection network called the Augmented Composite Banyan Network (ACBN) is proposed. The ACBN is created by adding a link to each SE of the Composite Banyan Network (CBN), which is a multipath network with at least two disjoint paths and was originally proposed in (Seo and Feng, 1995). Therefore, the basic building blocks in the ACBN are 4/spl times/4 SEs with log/sub 2/N stages. The ACBN inherits the favorable features of the CBN such as regularity, symmetry and easy rerouting capability under faults and conflicts. The ACBN also has an efficient and fast control algorithm that can easily generate a primary routing tag and alternative routing tags as in the CBN. A major improvement of the ACBN over the CBN is the higher connectivity with four disjoint paths between any source and destination pair. Moreover the ACBN can generate alternative routing tags in a much simpler way i.e., by a simple binary operation not by the conversion table as in the CBN. To compare the ACBN with other networks in connectivity, we introduce the definition of a degree of connectivity as a new connectivity measure function. The comparison results show that due to high connectivity the ACBN can resolve more random connection requests than other networks by using only a small amount of additional hardware.

In this paper, we propose a new high performance ATM switch architecture based on a high connectivity multipath multistage interconnection network called augmented composite banyan network (ACBN). The ACBN is created by adding a link to each switching element of the composite banyan network, which is a multipath network with at least two disjoint paths and was originally proposed in Seo and Feng (1995). The switch performance is studied under uniform and full load conditions. The analysis and simulation results show that the proposed switch can achieve a required cell loss probability using fewer stages than previously reported switches.

This paper describes the performance analysis of a class of two-connected multihop shufflenets, known as generalized shuffle networks. The topology of such networks is described mathematically by the equation N=kn, where N is the total number of nodes in the network, k the number of stages in the network and n the number of nodes in each stage. Compared to classical shufflenets, the definition of generalized shuffle networks allows a larger number of feasible network structures that are realizable for a given network size N. In attempting to find an optimum network structure, network characteristics are discussed and system performance is evaluated. Important relationships and interdependencies among the various network parameters are developed to facilitate cross-structural comparison.

Most research efforts to date on optical networks have concentrated on wavelength-division multiplexing (WDM) techniques where the information from different channels is routed via separate optical wavelengths. The data corresponding to a particular channel is selected at the destination node by a frequency filter. Optical time-division multiplexing (OTDM) has been considered as an alternative to WDM for future networks operating in excess of 10 Gb/s. Systems based on TDM techniques rely upon a synchronized clock frequency and timing to separate the multiplexed channels. Advances in device technologies have opened new opportunities for implementing OTDM in very high-speed long-haul transmission as well as networking. The multiterahertz bandwidth made available with the advent of optical fibers has spurred investigation and development of transparent all-optical networks that may overcome the bandwidth bottlenecks caused by electro-optic conversion. This paper presents an overview of current OTDM networks and their supporting technologies. A novel network architecture is introduced, aimed at offering both ultra-high speed (up to 100 Gb/s) and maximum parallelism for future terabit data communications. Our network architecture is based on several key state-of-the-art optical technologies that we have demonstrated.

Multihop networks with wavelength-division multiplexing (WDM) are one possible way to conduct high data-rate communication. We provide an in-depth study of the generalization of the well-known shuffle network for ultrafast multihop lightwave communication. In the classical definition of a shuffle network, i.e., N=kp/sup k/ where N is the number of nodes and k is the number of stages with nodes of degree p, the realizable values of N are very sparse and many of the intermediate values of N are not realizable. We use a new definition of the shuffle network, N=nk, where n is the number of nodes per stage, which was originally proposed by Krishna and B. Hajek (1990) as the shuffle-ring network. Based on this definition, we divide the shuffle networks into two classes: extra-stage and reduced-stage. We derive an exact model and an approximate model of the expected number of hops for various network topologies. The results can be used to determine an optimal network topology when given a value of N.

A new multipath multistage interconnection network called the composite banyan network is proposed. The network incorporates both the banyan and the reverse banyan networks and is constructed by superimposing the two. The basic building blocks in the composite banyan network are 3/spl times/3 switching elements with log/sub 2/N stages. A major advantage of the composite banyan network over existing networks with 3/spl times/3 SEs is an efficient and fast control algorithm that sets up a path between any source and destination pair. Instead of complex numerical calculations, the network can easily generate a primary routing tag and alternate tags through simple binary operations. Also, the network has a lot of favorable features, including regularity, symmetry, and easy rerouting capability under faults and conflicts. It is shown that at least two totally disjoint paths exist between any source and destination pair, which increase the degree of fault-tolerance. A deterministic permutation routing algorithm is also developed for the 8/spl times/8 composite banyan network, Using a simple tabular method, it is shown that the algorithm always finds a set of conflict-free tags.>

In this paper, we present a generalized version of the routing algorithm[1] for a class of 2log_2 N-stage networks which are made by concatenating two log_2 Nstage blocking networks. We show that the generalized algorithm can also cover a class of(2log_2 N - 1)-stage networks. It is shown that the inside-out algorithm is a more general algorithm which covers a large class of inherently symmetric rearrangeable networks, including the Benes and its equivalent networks. Moreover, it is shown that the time complexity of the algorithm is in O(N), which is superior to that of the looping algorithm. The algorithm is discussed using a graph representation of the network and its connectivity properties are shown by a graph describing rule. To show that the algorithm covers a class of 2log_2 N-stage networks, we introduce the concept of a base-network. These base-networks satisfy some common connectivity properties, and we show that any concatenation of two base-networks can be routed by our new algorithm.

This paper presents a routing algorithm for a class of multistage interconnection networks. Specifically, the concatenation of two Omega networks which has 2 log/sub 2/ N stages is treated. It is shown that this kind of asymmetric Omega+Omega network can be converted into a symmetric Omega/sup -1spl times/Omega network or a symmetric Omega/spl times/Omega/sup -1/ network. However, they have butterfly connections between the two center stages. A general algorithm is developed which routes a class of symmetric networks. The algorithm routes the network from center stages to outer stages at both the input and the output sides simultaneously. The algorithm presented is simpler and more flexible than the well-known looping algorithm in that it can be applied adaptively according to the structure of the network. It can be applied to routing the Omega-based networks regardless of the center-stage connection patterns, i.e., straight, skewed straight, simple butterfly or skewed butterfly as long as the networks are symmetric. The sufficient conditions for proper routing are shown and proved. In addition, an example is shown to demonstrate the algorithm.>