Coverage of Known Spaces: The Boustrophedon Cellular Decomposition

Coverage path planning is the determination of a path that a robot must take in order to pass over each point in an environment. Applications include de-mining, floor scrubbing, and inspection. We developed the boustrophedon cellular decomposition, which is an exact cellular decomposition approach, for the purposes of coverage. Essentially, the boustrophedon decomposition is a generalization of the trapezoidal decomposition that could allow for non-polygonalobstacles, but also has the side effect of having more efficient coverage paths than the trapezoidal decomposition. Each cell in the boustrophedon decomposition is covered with simple back and forth motions. Once each cell is covered, then the entire environment is covered. Therefore, coverage is reduced to finding an exhaustive path through a graph which represents the adjacency relationships of the cells in the boustrophedon decomposition. This approach is provably complete and experiments on a mobile robot validate this approach.     

B-Theta*: an Efficient Online Coverage Algorithm for Autonomous Cleaning Robots

We propose a novel approach to deal with the online complete-coverage task of cleaning robots in unknown workspaces with arbitrarily-shaped obstacles. Our approach is based on the boustrophedon motions, the boundary-following motions, and the Theta* algorithm known as B-Theta*. Under control of B-Theta*, the robot performs a single boustrophedon motion to cover an unvisited region. While performing the boustrophedon motion, if the robot encounters an obstacle with a boundary that has not yet been covered, it switches to the boundary mode to cover portions along the obstacle boundary, and then continues the boustrophedon motion until it detects an ending point. To move to an unvisited region, the robot detects backtracking points based on its accumulated knowledge, and applies an intelligent backtracking mechanism thanks to the proposed Theta* for multi-goals in order to reach the next starting point. Complete coverage is achieved when no starting point exists for a new boustrophedon motion. Computer simulations and experiments on real workspaces show that our proposed B-Theta* is efficient for the complete-coverage task of cleaning robots.     

An algorithmic approach to resolutions

We provide an algorithmic method for constructing projective resolutions of modules over quotients of path algebras. This algorithm is modified to construct minimal projective resolutions of linear modules over Koszul algebras.     

An algorithmic approach for fuzzy inference

To apply fuzzy logic, two major tasks need to be performed: the derivation of production rules and the determination of membership functions. These tasks are often difficult and time consuming. This paper presents an algorithmic method for generating membership functions and fuzzy production rules; the method includes an entropy minimization for screening analog values. Membership functions are derived by partitioning the variables into the desired number of fuzzy terms and production rules are obtained from minimum entropy clustering decisions. In the rule derivation process, rule weights are also calculated. This algorithmic approach alleviates many problems in the application of fuzzy logic to binary classification     

Algebraic solutions of holomorphic foliations: An algorithmic approach

We present two algorithms that can be used to check whether a given holomorphic foliation of the projective plane has an algebraic solution, and discuss the performance of their implementations in the computer algebra system Singular.     

Generalized approach for model algorithmic control

This paper considers the development of a general model algorithmic control (MAC). It is shown that the proposed structure contains all the features and principles of MAC. The scheme developed allows choices of prediction and reference trajectories. The regulation effect is studied and non-minimum phase systems are also exemplified. The tracking and regulation properties of the proposed MAC depend on the choice of regulator and controller parameters. Results of simulation studies indicate the effectiveness of the developed algorithmic control.     

The indecomposability problem in binary morphology: An algorithmic approach

An indecomposable shape is like a prime number. It cannot be decomposed further as a Minkowski sum of two simpler shapes. With respect to Minkowski addition (dilation), therefore, the indecomposable shapes are the fundamental building blocks of all geometric shapes. However, just as it is difficult to identify whether a given number is a prime number or not, it is equally or more difficult to say whether a given shape is indecomposable or not. In this paper we take up a subdomain of binary images, called the weakly taxicab convex image domain, and show how the indecomposability problem in that shape domain can be approached in a manner closely analogous to the number theoretic way. Apart from our attempt to show that the indecomposability problem is an extremely interesting mathematical problem, our algorithmic treatment of the problem also leads to an efficient method of computing Minkowski addition and decomposition of binary images.     

An algorithmic approach to combining belief functions

Methods of combination are used to synthesize pieces of evidence of equal standing that represent different aspects of a specific system about which a diagnosis is to be made. Combination is distinct from consensus, when complete diagnoses rendered by different knowledge sources require synthesis, and conditionalization, where pieces of evidence to be synthesized have dissymmetric relationships to each other. The Dempster-Shafer Rule is the quintessential combination method. However, it has been criticized for its inability to handle inconsistent pieces of evidence and for the way it focuses the weight of evidence. This article presents an alternative combination method that is capable of handling inconsistent evidence and relates evidence focusing to the amount of information resident in pieces of evidence. The method is capable of combining belief functions. Future research should address extending the method to the combination of a broad class of imprecise probability functions. © 1996 John Wiley & Sons, Inc.     

A complexity analysis and an algorithmic approach to student sectioning in existing timetables

We show that the following fundamental question in student sectioning can be efficiently decided in polynomial time: Is it possible to assign \(m\) students to \(k\) sectioned courses with respect to a given timetable with \(l\) timeslots such that the individual capacities of all sections are not exceeded and no student has more than one appointment per timeslot? Our result opens the possibility of efficiently checking the feasibility of candidate timetables with respect to this question as part of timetabling algorithms. Based on a succinct representation of solutions, we also provide an algorithm to compute optimal assignments in \(O( k^2l^2 \log (\mathrm{sum}_{A}))\), where \(\mathrm{sum}_{A}\) is the sum of all specified section capacities. On the other hand, we prove that adding any single of the following constraints turns the above question into an NP-complete problem:

• Course-selection constraint: Student’s course-selections must be respected.
• Timeslot constraint: Students have individual timeslot restrictions.
• Multiple-event constraint: Sections may have multiple events in the timetable, and there must be no timeslot clashes between all section-events for each student.

Hence our investigation gives insight into the location of the borderline between efficiently solvable and computationally hard problem variations.

     

An algorithmic approach to discovering and provingq-series identities

An algorithmic method of producingq-series identities from any given power series is discassed. This recursive technique is then used to give new proofs of several classicalq-identities of Gauss and Rogers. Dedicated to the memory of John Knopfmacher, 1937–1999, the inventor of the Engel expansions for q-series. The first author was partially supported by National Science Foundation Grant DMS-9206993 and by The Centre for Applicable Analysis and Number Theory of the University of the Witwatersrand. He wishes to express his gratitude to the second author who provided the hospitality and support which made his participation possible This paper was presented at the fourth International Conference on Average-Case Analysis of Algorithms, Princeton, NJ, by the second author. Online publication September 6, 2000.     

2D-VPC: An Efficient Coverage Algorithm for Multiple Autonomous Vehicles

International Journal of Control, Automation and Systems - In this paper, we address a problem of multi-robotic coverage, where an area of interest is covered by multiple sensors, each mounted on...     

Efficient algorithmic learning of the structure of permutation groups by examples

This paper discusses learning algorithms for ascertaining membership, inclusion, and equality in permutation groups. The main results are randomized learning algorithms which take a random generator set of a fixed group G ≤ S_n as input. We discuss randomized algorithms for learning the concepts of group membership, inclusion, and equality by representing the group in terms of its strong sequence of generators using random examples from G. We present O(n³ log n) time sequential learning algorithms for testing membership, inclusion and equality. The running time is expressed as a function of the size of the object set. (G ≤ S_n can have as many as n! elements.) Our bounds hold for all input groups. We also introduce limited parallelism, and our lower processor bounds make our algorithms more practical.Finally, we show that learning two-groups is in class NC by reducing the membership, inclusion, and inequality problems to solving linear systems over GF(2). We present an O(log³ n) time learning algorithm using n^ω processors for learning two-groups from examples (where n × n matrix product takes logarithmic time using n^ω processors).     

Charles Babbage as an algorithmic thinker

While the career of the Charles Babbage (1791-1871) shows a remarkable range of interests, strong threads bind together several of the principal ones: algorithmic thinking, with intimate links to algebra and to semiotics. The links connect especially his mathematical researches in functional equations with his work on mathematical tables and on calculating machines, but they are evident also in some of his social and industrial concerns. Evidence is presented to show that Babbage was consciously aware of at least some of these links. Attention to them casts light upon his achievements     

An algorithmic approach to coordinate transformation for robotic manipulators

Coordinate transformation is one of the most important issues in robotic manipulator control. Robot tasks are naturally specified in work space coordinates, usually a Cartesian frame, while control actions are developed on joint coordinates. Effective inverse kinematic solutions are analytical in nature; they exist only for special manipulator geometries and geometric intuition is usually required. Computational inverse kinematic algorithms have recently been proposed; they are based on general closed-loop schemes which perform the mapping of the desired Cartesian trajectory into the corresponding joint trajectory. The aim of this paper is to propose an effective computational scheme to the inverse kinematic problem for manipulators with spherical wrists. First an insight into the formulation of kinematics is given in order to detail the general scheme for this specific class of manipulators. Algorithm convergence is then ensured by means of the Lyapunov direct method. The resulting algorithm is based on the hand position and orientation vectors usually adopted to describe motion in the task space. The analysis of the computational burden is performed by taking the Stanford arm as a reference. Finally a case study is developed via numerical simulations.     

Model discrimination using an algorithmic information criterion

A method of choosing between competing models of small sets of observations is presented. The intended application is to the modelling of ‘badly defined’ systems. The ideas of algorithmic information theory are surveyed, and applied to model discrimination. A novel definition of a model as a program which computes the observations exactly is given; this allows the size of a model to be interpreted as a measure of the informativeness of the model. It also imposes a trade-off between approximation and complexity, which is essential if overfitting of models is to be avoided. Two examples of discriminating between models of field data are presented.     

一种能量有效的无线传感器网络覆盖控制算法

覆盖问题是WSN(无线传感器网络)的基本问题,合理的覆盖控制可以有效地延长WSN的生存时间.提出一种能量有效的WSN覆盖控制算法(EECCA).算法中,节点采用布尔感知模型,节点根据自己的能量大小和连续未当选工作节点的轮数,来触发定时器进行工作节点选择,并根据邻居节点的能量信息进行了工作节点优化.仿真实验结果表明,算法不仅可以满足覆盖率要求,而且在减少总体能量消耗方面也有很好的改善.     

An algorithmic approach to adaptive state filtering using recurrentneural networks

Practical algorithms are presented for adaptive state filtering in nonlinear dynamic systems when the state equations are unknown. The state equations are constructively approximated using neural networks. The algorithms presented are based on the two-step prediction-update approach of the Kalman filter. The proposed algorithms make minimal assumptions regarding the underlying nonlinear dynamics and their noise statistics. Non-adaptive and adaptive state filtering algorithms are presented with both off-line and online learning stages. The algorithms are implemented using feedforward and recurrent neural network and comparisons are presented. Furthermore, extended Kalman filters (EKFs) are developed and compared to the filter algorithms proposed. For one of the case studies, the EKF converges but results in higher state estimation errors that the equivalent neural filters. For another, more complex case study with unknown system dynamics and noise statistics, the developed EKFs do not converge. The off-line trained neural state filters converge quite rapidly and exhibit acceptable performance. Online training further enhances the estimation accuracy of the developed adaptive filters, effectively decoupling the eventual filter accuracy from the accuracy of the process model.     

An algorithmic approach to constructing mixed-level orthogonal and near-orthogonal arrays

Due to run size constraints, near-orthogonal arrays (near-OAs) and supersaturated designs, a special case of near-OA, are considered good alternatives to OAs. This paper shows (i) a combinatorial relationship between a mixed-level array and a non-resolvable incomplete block design (IBD) with varying replications (and its dual, a resolvable IBD with varying block sizes); (ii) the relationship between the criterion E(d²) proposed by Lu and Sun [Lu, X., Sun, Y., 2001. Supersaturated designs with more than two levels. Chinese Ann. Math. B 22, 183-194] or E(f_NOD) proposed by Fang et al. [Fang, K.T., Lin, D.K.J., Liu, M.Q., 2003b. Optimal mixed-level supersaturated design. Metrika 58, 279-291] used in the (near-) OA construction and the (M,S)-optimality criterion used in the IBD construction; (iii) the derivation of a tighter bound for E(d²); (iv) how to modify the IBD algorithm of Nguyen [Nguyen, N.-K., 1994. Construction of optimal incomplete block designs by computer. Technometrics 36, 300-307] to obtain efficient (near-) OA algorithms. Some new (near-) OAs are presented and some near-OAs are compared with arrays constructed by other authors. Examples showing the use of the constructed arrays are given.     

RVM的分层式验证平台及覆盖率驱动技术

本文介绍了应用RVM方法学搭建分层式验证平台,并阐述了基于RVM方法学的覆盖率驱动技术.这两种技术的应用帮助验证工程师提高验证效率并能确保验证的完备性.