Optimizing the Cabling Layout on a Wind Farm
Laying out cables between turbines incurs a significant cost when building a wind farm. For small farms, an expert can propose a good layout based on his or her domain knowledge. But as we plan for larger and larger farms, it becomes increasingly difficult to ensure that a hand-crafted layout is efficient. We aim to develop a software tool that will automatically find a cabling layout that minimizes costs.
Results:
- Worked with the domain expert to formulate an accurate model of the problem
- Reviewed the literature on related problems
- Decomposed the problem into three layers (circuit, substation, full farm) and two cases (single cable type, multiple cable types)
- For the single-cable-type case, mapped the three layers to existing problems, and developed a greedy top-down algorithm to find a feasible solution for the full farm problem (up to 1000 turbines). This algorithm can be used as a baseline for comparison, and as an initial solution in a more advanced optimization algorithm.
- For the multiple-cable-types case, developed an algorithm to find the optimal circuit. This algorithm can be used to determine whether a particular instance of the problem can be simplified to the single-cable-type case without a large sacrifice in cost.
Publications:
- technical report
- poster (large 4800 x 3600 PNG file)
Geometric Decision Rules for Instance-Based Learning
The Gabriel decision rule for instance-based learning has been shown before to perform well on low-dimensional data sets. We investigated the performance of the Gabriel decision rule on high-dimensional data sets, where we hypothesized that the Gabriel graph would become too dense to be useful. We also investigated two sparser graphs: the relative neighborhood graph (RNG) and the minimum spanning tree (MST). We compared these geometric decision rules against the traditional k-nearest-neighbor (KNN) rule, and against the support-vector-machine (SVM) classifier.
Results:
- Implemented the K-NN, Gabriel, and RNG decision rules
- Confirmed that the Gabriel Graph becomes very dense in high dimensions
- The RNG remained sparse in high dimensions, but it usually did not beat KNN
- The MST was too sparse to capture sufficient discriminating information
- The SVM beat the instance-based methods in almost all cases
Publications:
- paper submitted to MLDM 2012 (currently under review)
Extracting a State Transition Model from Robot Logs
We aim to build a state-transition model of the robot's behavior by data-mining the robot's logs. The resulting model could be useful in detecting and preventing failure before it happens. Also, the robot could save energy by shutting down subsystems that are unlikely to be needed in the near future, and it could save time by starting up subsystems that are likely to be needed soon.
Results:
- Built an interval-based algorithm for extracting states from the log
- Identified the limitations of the above algorithm
- Developed an alternative state extraction algorithm, based on function polling frequencies
- Tested state extraction on increasingly complex scenarios
- Studied and implemented the Baum-Welch algorithm for HMM training, but ultimately decided to focus our efforts on state extraction
Publications:
- paper submitted to AAMAS 2012 (currently under review)
N-Replica File Synchronization
Current methods for synchronizing file systems are either limited to two replicas, or depend on a central server to maintain an authoritative version of the data. We aim to develop a synchronizer that does not exhibit either of these limitations. The synchronizer is based on an algebra of file system operations, making it easier to formally verify its behavior.
Results:
- Implemented the file system algebra in Haskell
- Implemented an existing sequence-based synchronization algorithm, and tested it with QuickCheck
- Developed an alternative synchronization algorithm based on a tree data structure, and proved that the two produce equivalent results
- Discovered that synchronization policies vary on a liberal-conservative spectrum, according to which operations they propagate in the presence of conflicts
- Investigated binary relations between pairs of file system operations
- Prototyped composable file system abstractions to enable read-only operation, ignoring certain paths, or transparently synchronizing several directories in the file system
Publications:
- technical report
- poster (large 4400 x 5600 PNG file)
Final Project: Convex Hull with Graham Scan and Heuristics
I implemented and tested the Graham Scan algorithm for computing the convex hull of a set of points. I also explored the Akl-Toussaint point-pruning heuristic and several of its variations. To test the algorithms, I generated random points with various distributions. Finally, I analyzed the real-world running time of the generation, pruning, and hull algorithms, and compared it to the theoretical asymptotic running time.
Files:
- source code (detailed description in README)
Final Project: Replicate Active Learning and EM Results in Text Classification
The goal of my final project has been to replicate McCallum and Nigam's text classification results, using query-by-committee active learning and EM.
Highlights:
- Implemented Naive Bayes for text classification
- Implemented query-by-committee active learning
- Implemented an Expectation-Maximization algorithm to take advantage of unlabeled data
- Confirmed that EM and pool-based active learning improve performance, but due to gaps in McCallum and Nigam's presentation, I was unable to replicate their results exactly
Files:
- source code (available upon request)
- final report
Final Project: Simultaneous Localization and Mapping
(Worked with Andy Sayler.)
In Simultaneous Localization and Mapping (SLAM), a robot builds a map of an unknown environment, while at the same time keeping track of its location within the map. The goal of our project has been to implement a SLAM system based on the Extended Kalman Filter (EKF). We discovered major gaps in the tutorial we were following, and were unable to get the EKF to converge. One of the main lessons for us was the difficulty in implementing and debugging the EKF.
Highlights:
- Implemented schema-based navigation and obstacle avoidance
- Implemented landmark extraction based on RANSAC line detection
- Implemented simple mapping based on an occupancy grid
- Short-circuited the EKF and used the pure odometry data to estimate position
Files:
Final Project: Running Genetic Algorithms in Parallel
This project was inspired by Roger Alsing's attempt at evolving a set of transparent polygons to closely match the portrait Mona Lisa. I aimed to replicate his results with a GA that ran on a cluster of computers.
Highlights:
- Designed and implemented a C++ library to facilitate running GAs on a cluster using MPI
- Designed a way to serialize solutions so that they could be saved to disk, or transferred between machines
- Implemented the polygon evolution program and ran it on 64 CPUs
Files:
Final Paper: A Strategy for the Turing Test Judge
A paper describing a strategy of questioning for the judge in the Turing Test. The goals were:
- to develop a strategy that would remain valid even if shared with the programmers of the computer participating in the test.
- to reflect on the strengths and weaknesses of the Turing Test as a test of intelligence or consciousness
Files:
Final Portfolio: Short Stories
Some stories I wrote as part of the course:
- The Chairs (short story)
- Wheels (flash fiction)
- Wish (flash fiction)
Konvert2Ogg: an audio book converter for KDE 4
A frontend I wrote to facilitate converting audio books from one format to another.
Links:
Akonadi Mail Dispatcher Agent (KDE)
In the summer of 2009, I did a Google Summer of Code with the wonderful people at KDE. I worked on building a mail dispatcher agent for Akonadi, the new PIM framework in KDE SC 4. As part of the project, I learned a lot about how email works (SMTP, MIME, public-key encryption). Akonadi is a very fast-moving project, and unfortunately I have been unable to keep up with it during the school year.
Links:
exit's /dev/urandom blog
My blog in high school. I've made very few updates since coming to Tufts, and now the blog is archived (no new posts).
Links: