Publications

Refereed Journal Publications

• Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi, "Hybrid Systems: From Verification to Falsification by Combining Motion Planning and Discrete Search." Formal Methods in System Design, vol. 34(2), pp. 157--182, 2009.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @Article{PlakuKavrakiVardi_FMSD2008,
   author = {Erion Plaku and Lydia E. Kavraki and Moshe Y. Vardi}, 
   title  = {Hybrid Systems: From Verification to Falsification by
             Combining Motion Planning and Discrete Search},  
   journal= {Formal Methods in System Design},
   year   = {2009},
   volume = {34},
   number = {2},
   pages  = {157--182}}
  

  
  We propose HyDICE, Hybrid DIscrete Continuous Exploration, a multi-layered approach for hybrid-system falsification that combines motion planning with discrete search and discovers safety violations by computing witness trajectories to unsafe states. The discrete search uses discrete transitions and a state-space decomposition to guide the motion planner during the search for witness trajectories. Experiments on a nonlinear hybrid robotic system with over one million modes and experiments with an aircraft conflict-resolution protocol with high-dimensional continuous state spaces demonstrate the effectiveness of HyDICE. Comparisons to related work show computational speedups of up to two orders of magnitude.

• Erion Plaku, Hernan Stamati, Cecilia Clementi, and Lydia E. Kavraki, "Fast and Reliable Analysis of Molecular Motion Using Proximity Relations and Dimensionality Reduction." Proteins: Structure, Function, and Bioinformatics, 2007, vol. 67(4), pp. 897--907.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @Article{PlakuStamatiClementiKavraki_ProtSci2007,
   author = {Erion Plaku and Hernan Stamati and 
             Cecilia Clementi and Lydia E. Kavraki}, 
   title  = {Fast and Reliable Analysis of Molecular Motion Using 
             Proximity Relations and Dimensionality Reduction},
   journal= {Proteins: Structure, Function, and Bioinformatics},
   year   = {2007},
   volume = {67},
   number = {4},
   pages  = {897--907}}
  

  
  The analysis of molecular motion starting from extensive sampling of molecular configurations remains an important and challenging task in computational biology. Existing methods require a significant amount of time to extract the most relevant motion information from such data sets. In this work we provide a practical tool for molecular motion analysis. The proposed method builds upon the recent ScIMAP (Scalable Isomap) method, which, by using proximity relations and dimensionality reduction, has been shown to reliably extract from simulation data a few parameters that capture the main, linear and/or nonlinear, modes of motion of a molecular system. The results we present in the context of protein folding reveal that the proposed method characterizes the folding process essentially as well as ScIMAP. At the same time, by projecting the simulation data and computing proximity relations in a low-dimensional Euclidean space, it renders such analysis computationally practical. In many instances, the proposed method reduces the computational cost from several CPU months to just a few CPU hours, making it possible to analyze extensive simulation data in a matter of a few hours using only a single processor. These results establish the proposed method as a reliable and practical tool for analyzing motions of considerably large molecular systems and proteins with complex folding mechanisms.

• Erion Plaku and Lydia E. Kavraki, "Distributed Computation of the knn Graph for Large High-Dimensional Point Sets." Journal of Parallel and Distributed Computing, 2007, vol. 67(3), pp. 346--359.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @Article{PlakuKavraki_JPDC2007,
   author = {Erion Plaku and Lydia E. Kavraki},
   title  = {Distributed Computation of the knn Graph for 
             Large High-Dimensional Point Sets},
   journal= {Journal of Parallel and Distributed Computing},
   year   = {2007},
   volume = {67},
   number = {3},
   pages  = {346--359}}
  

  
  High-dimensional problems arising from robot motion planning, biology, data mining, and geographic information systems often require the computation of k nearest neighbor (knn) graphs. The knn graph of a data set is obtained by connecting each point to its k closest points. As the research in the abovementioned fields progressively addresses problems of unprecedented complexity, the demand for computing knn graphs based on arbitrary distance metrics and large high-dimensional data sets increases, exceeding resources available to a single machine. In this work we efficiently distribute the computation of knn graphs for clusters of processors with message passing. Extensions to our distributed framework include the computation of graphs based on other proximity queries, such as approximate knn or range queries. Our experiments show nearly linear speedup with over one hundred processors and indicate that similar speedup can be obtained with several hundred processors.

• Erion Plaku, Kostas E. Bekris, Brian Y. Chen, Andrew M. Ladd, and Lydia E. Kavraki, "Sampling-Based Roadmap of Trees for Parallel Motion Planning." IEEE Transactions on Robotics, 2005, vol. 21(4), pp. 587--608.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @Article{PlakuBekrisChenLaddKavraki_SRT2005,
   author = {Erion Plaku and Kostas E. Bekris and Brian Y. Chen and
             Andrew M. Ladd and Lydia E. Kavraki},
   title  = {Sampling-Based Roadmap of Trees for Parallel Motion Planning},
   journal= {IEEE Transactions on Robotics},
   year   = {2005},
   volume = {21},
   number = {4},
   pages  = {587--608} 
  

  
  This paper shows how to effectively combine a sampling-based method primarily designed for multiple query motion planning (Probabilistic Roadmap Method - PRM) with sampling-based tree methods primarily designed for single query motion planning (Expansive Space Trees, Rapidly-Exploring Random Trees, and others) in a novel planning framework that can be efficiently parallelized. Our planner not only achieves a smooth spectrum between multiple query and single query planning but it combines advantages of both. We present experiments which show that our planner is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of our planner is that it is significantly more decoupled than PRM and sampling-based tree planners. Exploiting this property, we designed and implemented a parallel version of our planner. Our experiments show that our planner distributes well and can easily solve high-dimensional problems that exhaust resources available to single machines and cannot be addressed with existing planners.

Refereed Conference Publications

• Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi, "Falsification of LTL Safety Properties in Hybrid Systems." International Conference on Tools and Algorithms for the Construction and Analysis of Systems, York, UK, 2009 (acceptance: 20%)

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{PlakuKavrakiVardi_TACAS2009,
   author = {Erion Plaku and Lydia E. Kavraki and Moshe Y. Vardi},
   title  = {Falsification of {LTL} Safety Properties in Hybrid Systems},
   booktitle = {International Conference on Tools and Algorithms for the
                Construction and Analysis of Systems},
   year   = {2009},
   address= {York, UK}} 
  

  
  This paper develops a novel computational method for the falsification of safety properties specified by syntactically safe linear temporal logic (LTL) formulas φ for hybrid systems with general nonlinear dynamics and input controls. The method is based on an effective combination of robot motion planning and model checking. Experiments on a hybrid robotic system benchmark with nonlinear dynamics show significant speedup over related work. The experiments also indicate significant speedup when using minimized DFA instead of non-minimized NFA, as obtained by standard tools, for representing the violating prefixes of φ.

• Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi, "Impact of Workspace Decompositions on Discrete Search Leading Continuous Exploration (DSLX) Motion Planning." IEEE International Conference on Robotics and Automation, Pasadena, CA, 2008, pp. 3751--3756.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{PlakuKavrakiVardi_ICRA2008,
   author = {Erion Plaku and Lydia E. Kavraki and Moshe Y. Vardi},
   title  = {Impact of Workspace Decompositions on Discrete Search
             Leading Continuous Exploration (DSLX) Motion Planning},
   booktitle = {IEEE International Conference on Robotics and Automation},
   year   = {2008},
   address= {Pasadena, CA},
   pages  = {3751--3756}} 
  

  
  We have recently proposed DSLX, a motion planner that significantly reduces the computational time for solving challenging kinodynamic problems by interleaving continuous state-space exploration with discrete search on a workspace decomposition. An important but inadequately understood aspect of DSLX is the role of the workspace decomposition on the computational efficiency of the planner. Understanding this role is important for successful applications of DSLX to increasingly complex robotic systems. This work shows that the granularity of the workspace decomposition directly impacts computational efficiency: DSLX is faster when the decomposition is neither too fine-nor too coarse-grained. Finding the right level of granularity can require extensive fine-tuning. This work demonstrates that significant computational efficiency can instead be obtained with no fine-tuning by using conforming Delaunay triangulations, which in the context of DSLX provide a natural workspace decomposition that allows an efficient interplay between continuous state-space exploration and discrete search. The results of this work are based on extensive experiments on DSLX using grid, trapezoidal, and triangular decompositions of various granularities to solve challenging first and second-order kinodynamic motion-planning problems.

• Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi, "Discrete Search Leading Continuous Exploration for Kinodynamic Motion Planning" Robotics: Science and Systems, Atlanta, Georgia, 2007, MIT Press, pp. 326--333

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{PlakuKavrakiVardi_RSS2007,
   author    = {Erion Plaku and Lydia E. Kavraki and Moshe Y. Vardi},
   title     = {Discrete Search Leading Continuous Exploration for 
                Kinodynamic Motion Planning},
   booktitle = {Robotics: Science and Systems},
   year      = {2007},
   address   = {Atlanta, GA},
   publisher = {{MIT} Press},
   pages     = {326--333}}
  

  
  This paper presents the Discrete Search Leading continuous eXploration (DSLX) planner, a multi-resolution approach to motion planning that is suitable for challenging problems involving robots with kinodynamic constraints. Initially the method decomposes the workspace to build a graph that encodes the physical adjacency of the decomposed regions. This graph is searched to obtain leads, that is, sequences of regions that can be explored with sampling-based tree methods to generate solution trajectories. Instead of treating the discrete search of the adjacency graph and the exploration of the continuous state space as separate components, DSLX passes information from one to the other in innovative ways. Each lead suggests what regions to explore and the exploration feeds back information to the discrete search to improve the quality of future leads. Information is encoded in edge weights, which indicate the importance of including the regions associated with an edge in the next exploration step. Computation of weights, leads, and the actual exploration make the core loop of the algorithm. Extensive experimentation shows that DSLX is very versatile. The discrete search can drastically change the lead to reflect new information allowing DSLX to find solutions even when sampling-based tree planners get stuck. Experimental results on a variety of challenging kinodynamic motion planning problems show computational speedups of two orders of magnitude over other widely used motion planning methods.

• Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi, "Hybrid Systems: From Verification to Falsification." International Conference on Computer Aided Verification, Berlin, Germany, 2007. Lecture Notes in Computer Science, editors W. Damm and H. Hermanns, vol. 4590, pp. 468--481 (acceptance: 10%)

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InCollection{PlakuKavrakiVardi_CAV2007,
   author   = {Erion Plaku and Lydia E. Kavraki and Moshe Y. Vardi},
   title    = {Hybrid Systems: From Verification to Falsification},
   booktitle= {International Conference on Computer Aided Verification},
   address  = {Berlin, Germany},
   year     = {2007},
   series   = {Lecture Notes in Computer Science},
   editor   = {W. Damm and H. Hermanns},
   volume   = {4590},
   pages    = {468--481}}
  

  
  We propose HyDICE, Hybrid DIscrete Continuous Exploration, a multi-layered approach for hybrid-system testing that integrates continuous sampling-based robot motion planning with discrete searching. The discrete search uses the discrete transitions of the hybrid system and coarse-grained decompositions of the continuous state spaces or related projections to guide the motion planner during the search for witness trajectories. Experiments presented in this paper, using a hybrid system inspired by robot motion planning and with nonlinear dynamics associated with each of several thousand modes, provide an initial validation of HyDICE and demonstrate its promise as a hybrid-system testing method. Comparisons to related work show computational speedups of up to two orders of magnitude.

• Erion Plaku and Lydia E. Kavraki, "Nonlinear Dimensionality Reduction Using Approximate Nearest Neighbors." SIAM International Conference on Data Mining, Minneapolis, MN, 2007, pp. 180--191 (acceptance: 12%).

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{PlakuKavraki_SDM2007,
   author   = {Erion Plaku and Lydia E. Kavraki},
   title    = {Nonlinear Dimensionality Reduction Using 
               Approximate Nearest Neighbors},
   booktitle= {SIAM International Conference on Data Mining},
   address  = {Minneapolis, MN},
   year     = {2007},
   pages    = {180--191}}
  

  
  Nonlinear dimensionality reduction methods often rely on the nearest-neighbors graph to extract low-dimensional embeddings that reliably capture the underlying structure of high-dimensional data. Research however has shown that computing nearest neighbors of a point from a highdimensional data set generally requires time proportional to the size of the data set itself, rendering the computation of the nearest-neighbors graph prohibitively expensive. This work significantly reduces the major computational bottleneck of many nonlinear dimensionality reduction methods by efficiently and accurately approximating the nearest-neighbors graph. The approximation relies on a distance-based projection of high-dimensional data onto low-dimensional Euclidean spaces. As indicated by experimental results, the advantage of the proposed approximation is that while it reliably maintains the accuracy of nonlinear dimensionality reduction methods, it significantly reduces the computational time.

• Erion Plaku, Lydia E. Kavraki, and Moshe Y. Vardi, "A Motion Planner for a Hybrid Robotic System with Kinodynamic Constraints." IEEE International Conference on Robotics and Automation, Rome, Italy, 2007, pp. 692--697.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{PlakuKavrakiVardi_ICRA2007Hybrid,
   author    = {Erion Plaku and Lydia E. Kavraki and Moshe Y. Vardi},
   title     = {A Motion Planner for a Hybrid Robotic System with 
                Kinodynamic Constraints},
   booktitle = {IEEE International Conference on Robotics and Automation},
   address   = {Rome, Italy},
   year      = {2007},
   pages     = {692--697}}
  

  
  The rapidly increasing complexity of tasks robotic systems are expected to carry out underscores the need for the development of motion planners that can take into account discrete changes in the continuous motions of the system. Completion of tasks such as exploration of unknown or hazardous environments often requires discrete changes in the controls and motions of the robot in order to adapt to different terrains or maintain operability during partial failures or other mishaps. The contribution of this work toward this objective is the development of an efficient motion planner for a hybrid robotic system. The controls and motion equations of the robot could change discretely in order to enable the robot to operate in different terrains. The framework in this paper blends discrete searching with sampling-based motion planning for continuous state spaces and is well-suited for robotic systems modeled as hybrid systems with numerous discrete modes and transitions. This multi-layered approach offers considerable improvements over existing methods addressing similar problems, as indicated by the experimental results.

• Erion Plaku, Kostas E. Bekris, and Lydia E. Kavraki, "OOPS for Motion Planning: An Online Open-source Programming System." IEEE International Conference on Robotics and Automation, Rome, Italy, 2007, pp. 3711--3716.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{PlakuBekrisKavraki_ICRA2007OOPSMP,
   author    = {Erion Plaku and Kostas E. Bekris and Lydia E. Kavraki},
   title     = {{OOPS} for Motion Planning: 
                An Online Open-source Programming System},
   booktitle = {IEEE International Conference on Robotics and Automation},
   address   = {Rome, Italy},
   year      = {2007},
   pages     = {3711--3716}}
  

  
  The success of sampling-based motion planners has resulted in a plethora of methods for improving planning components, such as sampling and connection strategies, local planners and collision checking primitives. Although this rapid progress indicates the importance of the motion planning problem and the maturity of the field, it also makes the evaluation of new methods time consuming. We propose that a systems approach is needed for the development and the experimental validation of new motion planners and/or components in existing motion planners. In this paper, we present the Online, Open-source, Programming System for Motion Planning (OOPSMP), a programming infrastructure that provides implementations of various existing algorithms in a modular, object-oriented fashion that is easily extendible. The system is open-source, since a community-based effort better facilitates the development of a common infrastructure and is less prone to errors. We hope that researchers will contribute their optimized implementations of their methods and thus improve the quality of the code available for use. A dynamic web interface and a dynamic linking architecture at the programming level allows users to easily add new planning components, algorithms, benchmarks, and experiment with different parameters. The system allows the direct comparison of new contributions with existing approaches on the same hardware and programming infrastructure.

• Erion Plaku and Lydia E. Kavraki, "Quantitative Analysis of Nearest-Neighbors Search in High-Dimensional Sampling-Based Motion Planning." International Workshop on Algorithmic Foundations of Robotics, New York, NY, 2006. Springer Tracts in Advanced Robotics, editors S. Akella, N.M. Amato, W.H. Huang, and B. Mishra, vol. 47, pp. 3--18 (acceptance: ~11%)

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InCollection{PlakuKavraki_WAFR2006,
   author   = {Erion Plaku and Lydia E. Kavraki},
   title    = {Quantitative Analysis of Nearest-Neighbors Search in 
               High-Dimensional Sampling-Based Motion Planning},
   booktitle= {International Workshop on Algorithmic 
               Foundations of Robotics},
   series   = {Springer Tracts in Advanced Robotics},
   address  = {New York, NY},
   editor   = {S. Akella and N. M. Amato and W. H. Huang and B. Mishra},
   volume   = {47},
   pages    = {3--18},
   year     = {2006}}
  

  
  We quantitatively analyze the performance of exact and approximate nearest-neighbors algorithms on increasingly high-dimensional problems in the context of sampling-based motion planning. We study the impact of the dimension, number of samples, distance metrics, and sampling schemes on the efficiency and accuracy of nearest-neighbors algorithms. Efficiency measures computation time and accuracy indicates similarity between exact and approximate nearest neighbors. Our analysis indicates that after a critical dimension, which varies between 15 and 30, exact nearest-neighbors algorithms examine almost all the samples. As a result, exact nearest-neighbors algorithms become impractical for sampling-based motion planners when a considerably large number of samples needs to be generated. The impracticality of exact nearest-neighbors algorithms motivates the use of approximate algorithms, which trade off accuracy for efficiency. We propose a simple algorithm, termed Distance-based Projection onto Euclidean Space (DPES), which computes approximate nearest neighbors by using a distance-based projection of high-dimensional metric spaces onto low-dimensional Euclidean spaces. Our results indicate DPES achieves high efficiency and only a negligible loss in accuracy.

• Erion Plaku and Lydia E. Kavraki, "Distributed Sampling-Based Roadmap of Trees for Large-Scale Motion Planning." IEEE International Conference on Robotics and Automation, Barcelona, Spain, 2005, pp. 3879--3884.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{PlakuKavraki_ICRA2005,
   author    = {Erion Plaku and Lydia E. Kavraki},
   title     = {Distributed Sampling-Based Roadmap of Trees 
                for Large-Scale Motion Planning},
   booktitle = {IEEE International Conference on Robotics and Automation},
   address   = {Barcelona, Spain},
   year      = {2005},
   pages     = {3879--3884}}
  

  
  High-dimensional problems arising from complex robotic systems test the limits of current motion planners and require the development of efficient distributed motion planners that take full advantage of all the available resources. This paper shows how to effectively distribute the computation of the Sampling-based Roadmap of Trees (SRT) algorithm using a decentralized master-client scheme. The distributed SRT algorithm allows us to solve very highdimensional problems that cannot be efficiently addressed with existing planners. Our experiments show nearly linear speedups with eighty processors and indicate that similar speedups can be obtained with several hundred processors.

• Mert Akinc, Kostas E. Bekris, Brian Y. Chen, Andrew M. Ladd, Erion Plaku, and Lydia E. Kavraki, "Probabilistic Roadmaps of Trees for Parallel Computation of Multiple Query Roadmaps." International Symposium of Robotics Research (ISRR), Siena, Italy, 2003. Springer Tracts in Advanced Robotics, editors D. Paolo and R. Chatila, vol. 15, pp. 80--89.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract       Note

  
  

  @InCollection{Plaku_ISRR2003,
   author   = {Mert Akinc and Kostas E. Bekris and Brian Y. Chen and 
               Andrew M. Ladd and Lydia E. Kavraki},
   title    = {Probabilistic Roadmaps of Trees for
               Parallel Computation of Multiple Query Roadmaps},
   booktitle= {International Symposium of Robotics Research},
   series   = {Springer Tracts in Advanced Robotics},
   address  = {Siena, Italy},
   volume   = {15},
   pages    = {80--89},
   year     = {2003}}
  

  
  We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners in a motion planning framework that can be efficiently parallelized. In multiple query motion planning, a data structure is built during a preprocessing phase in order to quickly respond to on-line queries. Alternatively, in single query planning, there is no preprocessing phase and all computations occur during query resolution. This paper shows how to effectively combine a powerful sample-based method primarily designed for multiple query planning (the Probabilistic Roadmap Method - PRM) with sample-based tree methods that were primarily designed for single query planning (such as Expansive Space Trees, Rapidly Exploring Random Trees, and others). Our planner, which we call the Probabilistic Roadmap of Trees (PRT), uses a tree algorithm as a subroutine for PRM. The nodes of the PRM roadmap are now trees. We take advantage of the very powerful sampling schemes of recent tree planners to populate our roadmaps. The combined sampling scheme is in the spirit of the non-uniform sampling and refinement techniques employed in earlier work on PRM. PRT not only achieves a smooth spectrum between multiple query and single query planning but it combines advantages of both. We present experiments which show that PRT is capable of solving problems that cannot be addressed efficiently with PRM or single-query planners. A key advantage of PRT is that it is significantly more decoupled than PRM and sample-based tree planners. Using this property, we designed and implemented a parallel version of PRT. Our experiments show that PRT distributes well and can easily solve high dimensional problems that exhaust resources available to single machines.
  
  Authors are in alphabetical order. Main contributor is Erion Plaku.

• Kostas E. Bekris, Brian Y. Chen, Andrew M. Ladd, Erion Plaku, and Lydia E. Kavraki, "Multiple Query Motion Planning using Single Query Primitives." IEEE/RSJ International Conference on Intelligent Robots and Systems, Las Vegas, NV, 2003, pp. 656--661.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract       Note

  
  

  @InProceedings{BekrisChenLaddPlakuKavraki_IROS2003,
   author   = {Kostas E. Bekris and Brian Y. Chen and 
               Andrew M. Ladd and Lydia E. Kavraki},
   title    = {Multiple Query Motion Planning using 
               Single Query Primitives},
   booktitle= {IEEE/RSJ International Conference on 
               Intelligent Robots and Systems},
   address  = {Las Vegas, NV},
   pages    = {656--661},
   year     = {2003}}
  

  
  We propose the combination of techniques that solve multiple queries for motion planning problems with single query planners. Our implementation uses a probabilistic roadmap method PRM with bidirectional rapidly exploring random trees BI-RRT as the local planner. With small modifications to the standard al- gorithms, we obtain a multiple query planner which is significantly faster and more reliable than its compo- nent parts. Our method provides a smooth spectrum between the PRM and BI-RRT techniques and obtains the advantages of both. We observed that the per- formance differences are most notable in planning instances with several rigid non-convex robots in a scene with narrow passages. This planner is in the spirit of non-uniform sampling and refinement tech- niques used in earlier work on PRM.
  
  Authors are in alphabetical order. Main contributors are Erion Plaku and Kostas E. Bekris.

• Erion Plaku and Igor E. Shparlinski, "On Polynomial Representations of Boolean Functions Related to some Number Theoretic Problems." Foundations of Software Technology and Theoretical Computer Science, Bangalore, India, 2001. Lecture Notes in Computer Science, editors R. Hariharan, M. Mukund, and V. Vinay, vol. 2245, pp. 305--316.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InCollection{PlakuShparlinski_FSTTCS2001,
   author   = {Erion Plaku and Igor E. Shparlinski},
   title    = {On Polynomial Representations of 
               Boolean Functions Related to some 
               Number Theoretic Problems},
   booktitle= {Foundations of Software Technology and
               Theoretical Computer Science},
   series   = {Lecture Notes in Computer Science},
   address  = {Bangalore, India},
   editor   = {R. Hariharan and M. Mukund and V. Vinay},
   year     = {2001},
   volume   = {2245},
   pages    = {305--316}}
  

  
  We say a polynomial P over Z_M strongly M-represents a Boolean function F if F(x) ≡ P(x) (mod M) for all x ∈ {0, 1}ⁿ. Similarly, P one-sidedly M-represents F if F(x) = 0 iff P(x) ≡ 0 (mod M) for all x ∈ {0, 1}ⁿ . Lower bounds are obtained on the degree and the number of monomials of polynomials over Z_M , which strongly or one-sidedly M-represent the Boolean function deciding if a given n-bit integer is square-free. Similar lower bounds are also obtained for polynomials over the reals which provide a threshold representation of the above Boolean function.

• Ziya Arnavut and Erion Plaku, "Lossless Compression of ECG Signals." IEEE International Conference of the Engineering in Medicine and Biology Society, Atlanta, GA, 1999.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @InProceedings{ArnavutPlaku_EMBS1999,
   author    = {Ziya Arnavut and Erion Plaku},
   title     = {Lossless Compression of ECG Signals},
   booktitle = {IEEE International Conference of the 
                Engineering in Medicine and Biology Society},
   address   = {Atlanta, GA},
   year      = {1999}}
  

  
  In this paper we study the compression techniques for electrocardiogram (ECG) signals based on Block Sorting Techniques. We introduce a new and faster block transformation than the Burrows and Wheeler Transformation (BWT), and later compare them for ECG data compression. We show that our algorithm yields better compression gain than the Burrows and Wheeler’s algorithm (BWA), Gzip and the Shorten waveform coder for lossless ECG data compression.

Ph.D. Thesis

• Erion Plaku, "From High-Level Tasks to Low-Level Motions: Motion Planning for High-Dimensional Nonlinear Hybrid Robotic Systems" Ph.D. Thesis, Rice University, Houston, TX. July 2008.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @PhDThesis{Plaku_PhD,
   author = {Erion Plaku},
   title  = {From High-Level Tasks to Low-Level Motions:
             Motion Planning for High-Dimensional 
             Nonlinear Hybrid Robotic Systems},
   school = {Rice University},
   address= {Houston, TX},
   year   = {2008}}
  

  
  

  A significant challenge of autonomous robotics in transportation, exploration, and search-and-rescue missions lies in the area of motion planning. The overall objective is to enable robots to automatically plan the low-level motions needed to accomplish assigned high-level tasks.

  Toward this goal, this thesis proposes a novel multi-layered approach, termed Synergic Combination of Layers of Planning (SyCLoP), that synergically combines high-level discrete planning and low-level motion planning. High-level discrete planning, which draws from research in AI and logic, guides low-level motion planning during the search for a solution. Information gathered during the search is in turn fed back from the low-level to the high-level layer in order to improve the high-level plan in the next iteration. In this way, high-level plans become increasingly useful in guiding the low-level motion planner toward a solution.

  This synergic combination of high-level discrete planning and low-level motion planning allows SyCLoP to solve motion-planning problems with respect to rich models of the robot and the physical world. This facilitates the design of feedback controllers that enable the robot to execute in the physical world solutions obtained in simulation.

  In particular, SyCLoP effectively solves challenging motion-planning problems that incorporate robot dynamics, physics-based simulations, and hybrid systems. Hybrid systems move beyond continuous models by employing discrete logic to instantaneously modify the underlying robot dynamics to respond to mishaps or unanticipated changes in the environment. Experiments in this thesis show that SyCLoP obtains significant computational speedup of one to two orders of magnitude when compared to state-of-the-art motion planners.

  In addition to planning motions that allow the robot to reach a desired destination while avoiding collisions, SyCLoP can take into account high-level tasks specified using the expressiveness of linear temporal logic (LTL). LTL allows for complex specifications, such as sequencing, coverage, and other combinations of temporal objectives.

  Going beyond motion planning, SyCLoP also provides a useful framework for discovering violations of safety properties in hybrid systems.

M.S. Thesis

• Erion Plaku, "Multiplicity Automata, Polynomials and the Complexity of Small-Depth Boolean Circuits." M.S.Thesis, Clarkson University, Postdam, New York. May 2002.

  PDF [publisher]         PDF [preprint]       BibTeX Citation       Abstract

  
  

  @MastersThesis{Plaku_Clarkson2002,
   author = {Erion Plaku},
   title  = {Multiplicity Automata, Polynomials and the 
             Complexity of Small-Depth Boolean Circuits},
   school = {Clarkson University},
   address= {Potsdam, NY},
   year   = {2002}}