Browsing by Author "HSU, David"

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    Accelerating Point-Based POMDP Algorithms through Successive Approximations of the Optimal Reachable Space
    (2007-04-29) HSU, David; LEE, Wee Sun; RONG, Nan
    Point-based approximation algorithms have drastically im-proved the speed of POMDP planning. This paper presents a new point-based POMDP algorithm called SARSOP. Like earlier point-based algorithms, SARSOP performs value iter-ation at a set of sampled belief points; however, it focuses on sampling near the space reachable from an initial belief point under the optimal policy. Since neither the optimal policynor the optimal reachable space is known in advance, SARSOP builds successive approximations to it through sampling and pruning. In our experiments, the new algorithm solved dif-.cult POMDP problems with more than 10,000 states. Its running time is competitive with the fastest existing point-based algorithm on most problems andfasterby manytimes on some. Our approach is complementary to existing point-based algorithms and can be integrated with them to improve their performance.
  • No Thumbnail Available
    Item
    Efficient Constrained Delaunay Triangulation for Large Spatial Databases
    (2006-01-27) WU, Xinyu; HSU, David; TUNG, Anthony K. H.
    Delaunay Triangulation (DT) and its extension Constrained Delaunay Triangulation (CDT) are spatial data structures that have wide applications in spatial data processing. Our recent survey shows, however, that there is a surprising lack of algorithms for computing DT/CDT for large spatial databases. In view of this, we propose an efficient algorithm based on the divide and conquer paradigm. It computes DT/CDT on in-memory partitions before merging them into the final result. This is made possible by discovering mathematical property that precisely characterizes the set of triangles that are involved in the merging step. Our extensive experiments show that the new algorithm outperforms another provably good disk-based algorithm by roughly an order of magnitude when computing DT. For CDT, which has no known disk-based algorithm, we show that our algorithm scales up well for large databases with size in the range of gigabytes.
  • No Thumbnail Available
    Item
    Protein Conformational Flexibility Analysis with Noisy Data
    (2007-01-18T09:54:03Z) NIGHAM, Anshul; HSU, David
    Protein conformational changes play a critical role in biological functions such as ligand-protein and protein-protein interactions. Due to the noise in structural data, determining salient conformational changes reliably and efficiently is a challenging problem. This paper presents an efficient algorithm for analyzing protein conformational changes, using noisy data. It applies a statistical flexibility test to all contiguous fragments of a protein and combines the information from these tests to compute a consensus flexibility measure for each residue of the protein. We tested the algorithm, using data from the Protein Data Bank and the Macromolecular Movements Database. The results show that our algorithm can reliably detect different types of salient conformational changes, including well-known examples such as hinge and shear, as well as the flap motion of HIV-1 protease. The software implementing our algorithm is available at http://motion.comp.nus.edu.sg/projects/proflexana/proflexana.html.