We address the problem of visually monitoring a terrain path using ground and aerial robots. This is a coupled problem that involves computation of a guard set for the environment and route planning for a heterogeneous group of robots through the points in the guard set. A terrain path that needs to be monitored can be transformed to generate a 1.5D terrain and robot paths can be modeled as chain visible curves to the terrain to ensure visibility. To efficiently monitor this 1.5D terrain, we present two solutions - a dynamic programming approach that finds the optimal solution but is slower and a integer linear programming solution that is faster in practice and that can take more constraints into account. We perform extensive simulations and do a comparative analysis of the two solution techniques.

Affine Control Loops (ACLs) occur frequently in data- and computeintensive applications. Implementing ACLs directly on dedicated hardware has the potential for spectacular performance improvement in area, time and energy. An important challenge for such direct hardware compilation of ACLs is the interconnection between the different processing elements, which may be non-local as well as dynamic. We propose a generic, reconfigurable interconnection fabric which can realize the data-path of any ACL and be dynamically reconfigured in constant time. We have applied for a patent for this technology.

The polyhedral model is extensively used for analyses and transformations of regular loop programs, one of the most important being automatic parallelization. The model, however, is limited in expressivity and the need for the generalization to more general class of programs has been widely known. Analyses and transformations in the polyhedral model rely on certain closure properties. Recently, these closure properties were extended to programs where variables may be defined over unions of Z-polyhedra which are the intersection of polyhedra and lattices. We present the scheduling analysis for the automatic parallelization of programs in the Z-polyhedral model, and obtain multidimensional schedules through an ILP formulation that minimizes latency. The resultant schedule can then be used to construct a space-time transformation to obtain an equivalent program in the Z-polyhedral model.

The polyhedral model is a well developed formalism and has been extensively used in a variety of contexts viz. the automatic parallelization of loop programs, program verification, locality, hardware generationand more recently, in the automatic reduction of asymptotic program complexity. Such analyses and transformations rely on certain closure properties. However, the model is limited in expressivity and the need for a more general class of programs is widely known.

We present optimization techniques for high level equational programs that are generalizations of affine control loops (ACLs). Significant parts of the SpecFP and PerfectClub benchmarks are ACLs. They often contain reductions: associative and commutative operators applied to a collection of values. They also often exhibit reuse: intermediate values computed or used at different index points being identical. We develop various techniques to automatically exploit reuse to simplify the computational complexity of evaluating reductions. Finally, we present an algorithm for the optimal application of such simplifications resulting in an equivalent specification with minimum complexity.

This paper is a summary of an effort to develop a powerful motion planning algorithm for the mobile manipulator. The mobile manipulator is expected to work in partially defined or unstructured environments. In our global/local approach to path planning, joint trajectories are generated for a desired Cartesian space path, designed by the global path planner. For local path planner, inverse kinematics for a redundant system is used. Obstacle avoidance and joint displacement limits for the manipulator links are considered in the motion planner. In an event of failure to obtain feasible trajectories, the task can not be accomplished. In the case of the joint constraint violation, use of Jacobian matrix element as gradient is proposed. At the point of failure, a derivation in the Cartesian space path is obtained and the re-planner gives a new path that would achieve the goal position. To calculate the deviation, a non-linear optimization problem is formulated and solved by standard sequential quadratic programming (SQP) method.

Many computations can be modeled with systems of affine recurrence equations (SAREs) over polyhedral domains. We study the problem of scheduling individual computations of an SARE in the presence of reductions i.e., operations specifying the accumulation of a set of values to produce a single value. Reductions involve a commutative and associative operator and therefore, per se, do not impose any specific order. However, on realistic machines, operators have bounded fan-in and therefore an order of accumulation (serialization) is needed. Arbitrary serializations may adversely affect the running time of a program. We develop an algorithm to determine efficient serializations of all reductions. We illustrate our methods with two significant examples.