Information-based Robot Navigation for Bandwidth-constrained Sensor Networks(2005-2006)

Information can be used as a mobile robot localizability metric -- a tool for computing the ability of different regions in an environment to aid in robot localization. In particular, for each region in the environment, the information computes the change in estimation entropy expected for a robot (utilizing Markov Localization) in this area. This project studies the use of combining information and a bandwidth utilization metric into a navigation map for a mobile robot embedded in a wireless sensor network. This approach allows for planning paths that can manage the trade-off between localization accuracy, consumption of shared network bandwidth, and path length. These maps also show promise as a tool for determining deployment topologies and maintenance schemes for ensuring consistent levels of localization in the face of mote failures. We have demonstrated that this technique is effective for generating paths that increase the accuracy of localization while requiring fewer detections.

read more

Large-Scale Wireless Sensor Network for Multi-object Pursuit-Evasion Games(2005)

In the summer of 2005, we deployed an outdoor large-scale wireless sensor network to demonstrate a variety of concepts: multi-object tracking, pursuit-evasion games, unmanned aerial vehicle exfiltration, and user-level interaction and debugging. A wireless sensor network (WSN) of 557 Trio motes was deployed in an outdoor area at UC-Berkeley's Richmond Field Station. We demonstrated a multi-object tracking and simulated pursuit of 2 human evaders crossing a 12 by 12 grid of motes. The detected tracks were registered on aerial images of the field station and relayed to mobile displays in the field. We additionally demonstrated data exfiltration from the WSN to a remotely piloted fixed wing aerial vehicle (called the BAT) via the standard mote radios. The BAT, equipped with an 802.11 WiFi link, then relayed the data to a base station for analysis and display. This was joint work with the NEST Team under the supervision of David Culler, Shankar Sastry, David Wagner, and Eric Brewer.

• P. Chen, S. Oh, M. Manzo, B. Sinopoli, C. Sharp, K. Whitehouse, G. Tolle, J. Jeong, P. Dutta, J. Hui, S. Schaffert, S. Kim, J. Taneja, B. Zhu, T. Roosta, M. Howard, D. Culler, and S. Sastry. Experiments in Instrumenting Wireless Sensor Networks for Real-Time Surveillance, In the Proceedings of the International Conference on Robotics and Automation Video, 2006.

Monstro: Outdoor Ground Robot and Mobile Sensor Network Platform(2005)

Monstro is a custom, rugged, cost effective, unmanned ground vehicle (UGV) hardware and software platform for use indoors and outdoors. Our final design consists of a 4 wheel drive, 2 axis steering, carbon fiber chassis capable of supporting a 30 pound payload. The robot was equipped with high precision differential GPS, 802.11 WiFi networking, a 1.6 GHz PentiumM Linux-based mobile computer, a programmable motor controller, and a Telos wireless sensor mote. A client-server software platform was developed to facilitate quick interaction and testing of control concepts. Interfacing with a wireless sensor network (WSN) is provided by an onboard Telos mote and supporting software interface. Additionally, the onboard computer is interfaced with the motor controller (running the TinyOS operating system) which provides control of wheel steering and speed while ensuring safety by disabling the motors during communication disruption. Additional onboard software utilizes a client-server model allowing a remote client (such as a desktop or laptop) to employ all the robot resources such as the motor control, the GPS, and the WSN. Special thanks to Dr. Khalid Al-Ali's team at Carnegie Mellon West who developed the chassis for their MAX platform and graciously allowed us to use it for our project. Special thanks to John Breneman for obtaining, modifying, and assembling the chassis. Thanks to Cory Sharp for code debugging assistance.

read more

Control within Wireless Sensor Networks (CWSNs) Simulator(2004-2005)

Motivated by several previous implementations, we developed a simulator to allow rapid prototyping and investigation of control systems embedded in wireless sensor networks (CWSNs). The simulator is designed for easy and automatic composition of simulation components (such as a state observer, a wireless network model, or a feedback controller). This is supported by a well-defined component API with named ports for information exchange, and a protocol for automatically connecting such components. Additionally, the simulator's default library of components was developed to support realistic simulation of pursuit-evasion games (PEGs) embedded in WSN. To this end, several crucial features of our previous PEG implementation were modeled such as nonholonomic robot dynamics, a lossy and laggy multihop wireless networking channel, mote hardware failure, and sensor failure and saturation.

ACTIONS: Control Architecture for Wireless Sensor Network Applications(2004-2005)

ACTIONS is architecture for control theory implementations on networks of sensors. ACTIONS is the result of an effort to develop a unified framework for designing control systems that interact with wireless sensor networks (WSNs). In particular, using insight from our pursuit-evasion game (PEG) demonstration, we define 3 categories of WSN characteristics that frustrate control design: sensor error, missing and spurious readings, and network characteristics. These categories encompass design difficulties from inter-mote calibration error to multi-hop latency. After exploring the challenge space, we enumerate techniques for addressing each challenge and integrate these into a unified service architecture framework. The final design employs several design philosophies: multi-modal control, neighborhood models, hand-shaking, status query, time synchronization, coordination, predictive control, and maintenance routines.

Wireless Sensor Network for Mobile Robot Pursuit-Evasion Games(2003)

In July 2003, we demonstrated a mobile robot pursuit-evasion game on a medium-scale wireless sensor network. On an outdoor field, we deployed 100 motes in an 10 by 10 regular grid with 2 meter spacing for tracking a unmanned ground vehicle (UGV). Using landmark routing and periodic beacons from the robots, the sensor network provided the capability of wirelessly routing messages amongst motes and mobile robots. A human controlled evader robot driving in the field was detected by nearby motes using magnetometers. These detections were aggregated and relayed to the pursuer robot. Using these detections and an onboard D-GPS system, the pursuer localized itself and the evading robot and followed an intercept course to the evader. In all runs (about half a dozen), the pursuer successfully captured the evader.This was joint work with the NEST Team under the supervision of David Culler, Eric Brewer, David Wagner, and Shankar Sastry.

• Cory Sharp, Shawn Schaffert, Alec Woo, Naveen Sastry, Chris Karlof, Shankar Sastry, David Culler, Design and Implementation of a Sensor Network System for Vehicle Tracking and Autonomous Interception, In the Proceedings of the European Workshop on Wireless Sensor Networks 2005, Jan-Feb 2005.

read more

Distributed Control Applications Within Sensor Networks(2002-2003)

Wireless sensor networks (WSNs) are becoming an important sensing platform for many applications including environmental monitoring and vehicle tracking. As we move to augment these platforms with control systems, classical control theory will prove to be insufficient in addressing many of the properties of the WSN platform. In particular, WSNs provide sensor measurements aperiodically, with large latency, and often lacking sufficiently accurate time stamps. This project seeks to provide control system design methodologies for combating these characteristics. We provide an overview of the intended hardware and software platforms and our target control application. Focusing on our application, we discuss several models of computation potentially applicable to our system, and suggest a mixed model that provides for time triggers at the control level and discrete events at the sensor network detection level. Joint work with Bruno Sinopoli, Cory Sharp, Luca Schenato, and Shankar Sastry.

• B. Sinopoli, C. Sharp, L. Schenato, S. Schaffert, S.S. Sastry. Distributed control applications within sensor networks. In Proceedings of the IEEE, Volume: 91, Issue: 8, Aug. 2003.

Predictive Control for Vehicle Navigation in Wireless Sensor Networks(2002)

We investigate the ability of predictive and adaptive control to combat the laggy and aperiodic nature of sensor network data streams. In particular, we test the ability of a model predictive controller (MPC) with adaptive parameters to learn the parameters of the dynamics and successfully navigate to given way-points. For these experiments, we used a COTS-BOTS robot navigating on a flat high traction surface with a network of Mica motes suspended above detecting the magnetic disturbance created by the robot. We also developed a hardware-in-the-loop simulator capable of interacting with this environment and a color tracking camera for providing ground truth localization of the robot. Initial experiments were successful: after 2 initialization way points, the robot typically learned its parameters with sufficient precision to reach proceeding way-points. The COTS-BOTS robot was developed by Sarah Bergbreiter.

Wireless Sensor Network for Vehicle Tracking and Camera Control(2002)

This project seeks to understand the challenges and design requirements for tracking and control using a wireless sensor network (WSN). We implemented an indoor 5 by 5 network of the Berkeley Mica motes for tracking a small RC car. The car is tracked with the mote's magnetic sensor, and the estimated location of the vehicle is relayed to a base-station that controls a pan-tilt-zoom camera to follow the vehicle. In particular, as individual motes sense the vehicle, they broadcast their reading to share this information with neighboring motes. Periodically, the mote with the largest, recent magnetic sensing, elects itself as a leader, aggregates recent readings from a small neighborhood, and multi-hops this message back to the root node. The multi-hop broadcast works using a fixed routing table: messages are routed down and to the left. The base-station, using a snooping mote, receives aggregated magnetic readings and controls the camera to point at the center of mass of these readings. The implementation was successful for tracking the RC car with relatively low noise. Occasional spurious and missing magnetic detections caused the camera to lose the car or pan to the wrong region of the network. This was joint work with the NEST Team under the supervision of David Culler, Eric Brewer, David Wagner, Kris Pister, and Shankar Sastry.

Modeling Control in Wireless Sensor Networks(2002)

Integrating wireless sensor networks (WSNs) and control systems present several challenges. Classical control theory assumes a periodic, time-triggered model of computation and is unable to cope with WSN design issues such as task scheduling and sensor synchronization. On the other hand, models of computation useful for computer networks are incapable of modeling continuous dynamics and lack the depth to analyze controller properties such as stability or safety. This project examines how we can effectively model and implement distributed control systems in WSNs using an informative example problem: a single lane automobile bridge with mote access controllers. Using the Ptolemy II modeling system, we develop a continuous time and discrete event hybrid model that accounts for networking collision and latency, distributed unsynchronized sensor measurements, and continuous dynamics. We discuss the advantages and disadvantages of such an approach. Furthermore, we instantiate our control design in the synchronous-reactive language Esterel and use this to generate TinyOS code capable of running on Berkeley's Mica motes. Joint work with Bruno Sinopoli. Thanks to Alessandro Pinto and Yanmei Li for their contribution in the Esterel implementation.

Feasibility of Semi-definite Programming for Determining Node Topology from Ranging Information(2000)

Many areas of research require a fast and accurate method to determine the geometry of nodes in an N-dimensional space given only pairwise range information. For instance, researchers working on wireless sensor networks (WSNs) distribute many sensing nodes throughout an environment. Once deployed, the WSN should initialize itself and begin reporting sensor measurement and position information. In order for the network to determine position information, each node needs to localize itself relative to the other nodes. Typically, the received signal strength indicator (RSSI) or groups of ultrasonic transceivers can be used to gather range values amongst pairs of nodes. Using semi-definite programming (SDP), we develop an algorithm for determining the relative position of nodes given this ranging information. Another field in which such a procedure is useful is molecular modeling where the range between atoms is known, but the geometry of the molecule is unknown. After developing the solution algorithm, we investigate its empirical performance using MATLAB.

• S. Schaffert. Position Estimation from Distance Information. Project Report. December 2000.

Dynamic Surface and PID Controller Comparison for Slightly Nonlinear Helicopter Dynamics(2000)

Nonlinear helicopter dynamics can be complex and unstable requiring extensive controller design effort and testing. Sliding mode controllers provide a design for addressing nonlinear systems. This project is a comparative study of the design effort and effectiveness of PID controllers compared to sliding mode controllers for slightly nonlinear helicopter dynamics. In particular, using a technique shown to reduce complex helicopter dynamics, we present a reduced complexity set of helicopter dynamics. A typical PID controller, along with a dynamic surface controller and nonlinear observer is designed for these dynamics. The two control designs are compared for different frequency inputs and noise rejection.

Dynamic Priority Task Scheduler for Mission Critical Control Systems(2000)

This project develops a task scheduler for mission critical control systems. We seek to find a scheduler that will ensure no task is starved, mission critical tasks complete first, overall task latency is minimized, and specified deadlines are achieved. We assume that each task has a given minimum and maximum execution time, that the dependencies between tasks is specified by a directed acyclic graph (DAG), and that each task will announce when it requires CPU time. With this model, we develop a hierarchical parent-child scheduler. The parent simply maintains a FIFO task queue, which is dynamically shuffled by the child scheduler. We develop and study three child schedulers: ratcheting priority, optimal ratcheting priority, and output sensitive optimal. As an example, we take a helicopter control system, encode it in our task model, and compare the simulated performance of our schedulers to that of a round-robin, a static priority, and a FIFO scheduler. This project was joint work with Mark Donahue.

Maximal Controlled Invariant Sets and Least Restrictive Controller(1999-2001)

Synthesis of the maximal controlled invariant sets and least restrictive controllers for classes of discrete time linear and discrete time hybrid systems with safety specifications is investigated. The existence and uniqueness of a controlled invariant set and least restrictive controller associated with a system is established. An iterative solution algorithm for classes of systems definable in a decidable theory is proposed and investigated. It is shown that if the algorithm converges in a finite number of iterations, the problem is completely solved. Additionally, for certain classes of linear discrete time systems, the algorithm is shown to converge in a finite number of iterations. Examples and software tools are discussed to demonstrate an implementation of the proposed solution algorithm. This was joint work with Rene Vidal, Omid Shakernia, John Lygeros, and Shankar Sastry.

• S. Schaffert. Masters Thesis. Master of Science, Plan II. Research Project. Controller synthesis for discrete time hybrid systems with safety specifications. 2001.
• R. Vidal, S. Schaffert, O. Shakernia, J. Lygeros and S. Sastry. Decidable and Semi-decidable Controller Synthesis for Classes of Discrete Time Hybrid Systems. In Proceedings of the 40th IEEE Conference on Decision and Control, pp. 1243-1248, Orlando, December 2001.
• R. Vidal, S. Schaffert, J. Lygeros and S. Sastry. Controlled Invariance of Discrete Time Systems. In Hybrid Systems: Computation and Control, volume 1790 of Lecture Notes in Computer Science, pages 437-450. Springer Verlag, 2000.
• R. Vidal, S. Schaffert, J. Lygeros and S. Sastry. Controlled Invariance of Discrete Time Systems. UC Berkeley Memorandum No. UCB/ERL M99/65, 1999.

Local Community Integration and Fundraising Web Portal(2006-2008)

The web provides a great opportunity for bringing together and enriching local communities. This venture focused on developing a web portal that would allow local communities to actively interact and raise money for local organizations. As the Principal Architect and Director of Technology, I contributed to the strategic business and technical vision of this project. I configured and maintained the necessary hardware and software infrastructure. I developed components of the software and database architecture for various software services including automatic image enhancement, accounting and business tracking, user reliability estimation, automatic sitemap generation, continuity (backup, restoration, and migration) assurance, efficient keyword search, search engine optimization, email tracking, virtual URL namespace support, traffic monitoring, similar content grouping, privileged user security, and user interface design.

Raised Boxes Web Theme(2009-2010)

I wanted a new look for my website that would be simple, clean, professional, and provide excellent readability. This design is the result of that effort. To enable a clean and readable look, I built this design on the Blueprint CSS framework. This also provides instant cross browser compatibility. Additionally, I wanted to use open source tools, so I built the graphics using Inkscape (earlier versions were built using Gimp). To enable easy navigation, I made several clearly delineated sections of each page: a header area, a navigation area, a content area, and a footer. Since long lines are difficult to read in browsers, I kept the width of the content area relatively small: 630px in total and 600px within paragraphs. Finally, to provide a bit of depth in the design, I added rounded corners and drop shadows around the major sections of the page.

read more

Keyboard Key Assignment: Qwerty? Dvorak? Neither?(2005)

Could a different keyboard key layout reduce the amount of work required of our fingers during daily typing? Almost everyone I encounter uses Qwerty and, those who have used both Qwerty and Dvorak, are conflicted on which is the right choice. This project was a brief experiment to determine if I would personally be well suited to using Dvorak, and if I could reduce overall hand fatigue. Analyzing much of the code and publications I have written in the last five years, I computed a histogram of my character usage. Analysis showed that with Qwerty only 25% of the characters I used were on the home row. With Dvorak, about 53% of the characters I used were on the home row. Further analysis revealed that my fingers traveled approximately 46% further using a Qwerty key layout than with a Dvorak key layout. Using a personalized comfort metric, I further made minor changes to the Dvorak key assignment. In particular, I made keys commonly used in code development, such as $ or #, more accessible. I switched to the new key assignments and was successful at regaining my previous typing speed and reducing overall hand fatigue.

Scape: Exploring Pleasing Geometry(2004)

Golden rectangles, the golden ratio, and the Fibonacci sequence have been claimed to echo, at least approximately, natural phenomenon such as the geometry present in sea shells or the pedals of a flower. Additionally, it has been suggested that many artists throughout history knowingly exploited such rules to create realistic and pleasing images. This project was a brief study to explore the use of geometry and precise ratios in attaining pleasing images: an exploration to determine my personal opinion. The final piece, titled 'scape, is acrylic on an 8 foot by 10 inch canvas. The geometry was well planned out; the paint choice and application, however, was glib. Whether the designer achieved pleasing imagery in the face of sloppy color choice and application is, as always, left to the viewer.