Protocol design for an automated highway system

A structured use of control, communication and computing techologies in vehicles and in the highway can lead to major increases in highway capacity. Our context is an automated highway system (AHS) in which traffic is organized in platoons of closely spaced vehicles under automatic control. The AHS control tasks are arranged in a three-layer hierarchy. At the top or link layer a centralized controller assigns to each vehicle a path through the highway and sets the target size and speed for platoons to reduce congestion. The remaining two layers are distributed among controllers on each vehicle. A vehicle's platoon layer plans its trajectory to conform to its assigned path and to track the target size. The plan consists of a sequence of elementary maneuvers: merge (combines two platoons into one), split (separates one platoon into two), and change lane (enables a single car to change lane). Once the protocol layer determines that a particular maneuver can safely be initiated, it instructs its regulation layer to execute the corresponding precomputed feedback control law which implements the maneuver. This paper focuses on the design of the platoon layer. In order of ensure that it is safe to initiate a maneuver, the platoon layer controller enters into a negotiation with its neighbors. This negotiation is implemented as a protocol—a structured sequence of message exchanges. After a protocol terminates successfully, the movement of the vehicles involved is coordinated and the maneuver can be initiated. A protocol is designed in two stages. In the first stage, the protocol is described as an informal state machine, one machine per vehicle. The informal state machine does not distinguish between actions and conditions referring to the vehicle's environment and those referring to the protocol itself. In the second stage this distinction is enforced and the protocol machines are specified in the formal language COSPAN. COSPAN software is then used to show that the protocol indeed works correctly. One can now be reasonably confident that, properly implemented, the protocol designed here will work as intended.Work supported by the PATH program, Institute of Transportation Studies, University of California, Berkeley, and NSF Grant ECS-911907. It is a pleasure to thank Dr. Bob Kurshan for providing COSPAN and explaining its use, Ellen Sentovich for help with COSPAN, Max Holm for computer support, Anuj Puri for comments which improved parts of the design, and members of the PATH Seminar on AVCS where this design was first presented and discussed. The authors alone are responsible for the views expressed here.     

Extending Proxy Caching Capability: Issues and Performance

Proxy caching is an effective approach to reduce the response latency to client requests, web server load, and network traffic. Recently there has been a major shift in the usage of the Web. Emerging web applications require increasing amount of server-side processing. Current proxy protocols do not support caching and execution of web processing units. In this paper, we present a weblet environment, in which, processing units on web servers are implemented as weblets. These weblets can migrate from web servers to proxy servers to perform required computation and provide faster responses. Weblet engine is developed to provide the execution environment on proxy servers as well as web servers to facilitate uniform weblet execution. We have conducted thorough experimental studies to investigate the performance of the weblet approach. We modify the industrial standard e-commerce benchmark TPC-W to fit the weblet model and use its workload model for performance comparisons. The experimental results show that the weblet environment significantly improves system performance in terms of client response latency, web server throughput, and workload. Our prototype weblet system also demonstrates the feasibility of integrating weblet environment with current web/proxy infrastructure.     

Transductive multi-label learning from missing data using smoothed rank function

Pattern Analysis and Applications - In this paper, we propose two new algorithms for transductive multi-label learning from missing data. In transductive matrix completion (MC), the challenge is...     

Fast strong planning for fully observable nondeterministic planning problems

The ability to find strong solutions to fully observable nondeterministic (FOND) planning problems, if they exist, is desirable because unlike weak and strong-cyclic solutions, strong solutions are guaranteed to achieve the goal. However, only limited work has been done on FOND planning with strong solutions. In this paper, we present a sound and complete strong planning algorithm and incorporate it into our planner, FIP, which has achieved outstanding performance on strong cyclic planning problems. This new strong planning approach enables FIP to first search for strong solutions, and then search for strong-cyclic solutions only if strong solutions do not exist. We conduct extensive experiments to evaluate the new strong planning approach to (1) find a strong solution if one exists and (2) determine the non-existence of a strong solution. Experimental results demonstrate the superior performance of our planner to Gamer and MBP, the two best-known planners capable of solving strong FOND planning problems, on a variety of benchmark problems. Not only is our planner on average three orders of magnitude faster than Gamer and MBP, but it also scales up to larger problems.     

A new class of B/W halftoning algorithms

A new class of dithering algorithms for black and white (B/W) images is presented. The basic idea behind the technique is to divide the image into small blocks and minimize the distortion between the original continuous-tone image and its low-pass-filtered halftone. This corresponds to a quadratic programming problem with linear constraints, which is solved via standard optimization techniques. Examples of B/W halftone images obtained by this technique are compared to halftones obtained via existing dithering algorithms.     

The implementation of an unstable system with a realizable stable system

Unstable systems are normally confronted in control, signal processing and communication systems when one tries to model the inverse of a plant for output control and the inverse of a filter or transmission channel characteristics in the frequency domain for the equalization of the distortion. Various methods are shown and proved in this tutorial paper to approximate an unstable system by stable ones. The idea is to model an unstable system with a noncausal one and then implement it with an appropriate delay. The methods are applicable for both analog and digital systems.     

Relational programs: An architecture for robust real-time safety-critical process-control systems

Software for safety-critical systems, such as avionic, medical, defense, and manufacturing systems, must be highly reliable since failures can have catastrophic consequences. While existing methods, such as formal techniques, testing, and fault-tolerant software, can significantly enhance software reliability, they have some limitations in achieving ultrahigh reliability requirements. Formal methods are not able to cope with specification faults, testing is not able to provide high assurance, and fault-tolerant software based on diverse designs is susceptible to common-mode failures. We present a new approach that starts with a decomposition of the system requirements into a conjunction of subtasks (goals and constraints). The system state space is then projected onto a restricted space that is specialized for a subtask. The control problem corresponding to each subtask is solved and validated in its restricted “view” of the system state space. To allow the programs for the individual subtasks to be easily composed together, the model for each subtask is relational rather than functional, i.e., it represents a set of control trajectories for each input rather than just one trajectory. The overall system is obtained by composing the models for the subtasks using well-defined set intersection and union operations. The relational approach has several significant advantages. With appropriate priority assignments, it provides strong guarantees that the safety-critical components are immune to defects in other components of the system. Also, the system reliability can be rigorously derived from the component reliabilities. This significantly reduces the validation effort since the number of states and transitions in the decomposition is a fraction of those in the overall system. The system can be composed from its components either statically or dynamically; the latter facilitates on-the-fly maintenance as well as incorporation of advanced adaptive and evolving control programs. The paper contains a detailed example to illustrate the relational approach. This revised version was published online in June 2006 with corrections to the Cover Date.