MALLET, a multi-agent logic language for encoding teamwork, is intended to enable expression of teamwork emulating human teamwork, allowing experimentation with different levels and forms of inferred team intelligence. A consequence of this goal is that the actual teamwork behavior is determined by the level of intelligence built into the underlying system as well as the semantics of the language. In this paper, we give the design objectives, the syntax, and an operational semantics for MALLET in terms of a transition system. We show how the semantics can be used to reason about the behaviors of team-based agents. The semantics can also be used to guide the implementation of various MALLET interpreters emulating different forms of team intelligence, as well as formally study the properties of team-based agents specified in MALLET. We have explored various forms of proactive information exchange behavior embodied in human teamwork using the CAST system, which implements a built-in MALLET interpreter.

Despite the significant progress in multi-agent communication decision, existing research does not address two important issues: 1) how to optimize timing and currency of communication when dealing with dynamically changing information, and 2) what kinds of communication decision interdependency exist in a team and how this interdependency impacts a single agent's communication decision. To provide a more comprehensive solution to the communication problem, we present a new model, DTPC (decision-theoretic proactive communication), which uses statistical analysis of information production and need of team members and a dynamic decision-theoretic determination of communication policies. We show experimentally how DTPC decreases communication load while improving performance of distributed teamwork.

Supporting proactive communication among agents in multi-agent teamwork is crucial. In this paper, we focus on how to represent observability, and how to include it into the basic reasoning for proactive communication. We show how agents can use observation of the environment and of teammates' actions to estimate the teammates' beliefs without generating unnecessary messages. The experiment shows that agents can anticipate information needs among the team members and proactively communicate the information, reducing the total volume of communication.

Urban search and rescue (USAR) is the rescue of people trapped by disasters involving the collapse of man-made structures. Introducing robots to USAR has the potential to increase the speed and effectiveness of rescue operations considerably and make them safer for rescuers. Robots have been used in recent rescue operations, including the WTC terrorist attack, leading to the identification of several problems in robot-assisted search and rescue. This paper proposes a solution to one such problem that has been encountered repeatedly in the use of robots for USAR: the determination of the scale of unrecognizable objects in the camera views from the robot. We describe a procedure that would allow the extraction of size and orientation information using a laser pointer and camera mounted on a robot, and experiments that verify the effectiveness of this procedure have been shown.

This paper presents an approach to human-agent mixed teams for distributed team training, demonstrated through the integration of the domain independent multiagent architecture CAST with the military command-and-control simulation software DDD (distributed dynamic decision-making). We extend the CAST architecture in a way such that agents can replace any number of teammates on a DDD team. To capture the overall picture of teamwork, we explore the MALLET language in CAST for the specification of team structures and processes that involve both humans and agents.

How agents accomplish a goal task in a multi-agent system is usually specified by multi-agent plans built from basic actions (e.g. operators) of which the agents are capable. The plan specification provides the agents with a shared mental model for how they are supposed to collaborate with each other to achieve the common goal. Making sure that the plans are reliable and fit for the purpose for which they are designed is a critical problem with this approach. To address this problem, this paper presents a formal approach to modeling and analyzing multi-agent behaviors using Predicate/Transition (PrT) nets, a high- level formalism of Petri nets. We model a multi-agent problem by representing agent capabilities as transitions in PrT nets. To analyze a multi-agent PrT model, we adapt the planning graphs as a compact structure for reachability analysis, which is coherent to the concurrent semantics. We also demonstrate that one can analyze whether parallel actions specified in multi-agent plans can be executed in parallel and whether the plans can achieve the goal by analyzing the dependency relations among the transitions in the PrT model.

In a multi-agent system, how agents accomplish a goal task is usually specified by multi-agent plans built from basic actions (e.g. operators) of which the agents are capable. A critical problem with such an approach is how can the designer make sure the plans are reliable. To tackle this problem, this paper presents a formal approach for modeling and analyzing multi-agent behaviors using Predicate/Transition (PrT) nets, a high-level formalism of Petri nets. We construct a multi-agent model by representing agent capabilities as transitions. To verify a multi-agent PrT model, we adapt the planning graphs as a compact structure for the reachability analysis. We also demonstrate that, based on the PrT model, whether parallel actions specified in multi-agent plans can be executed in parallel and whether the plans guarantee the achievement of the goal can be verified by analyzing the dependency relations among the transitions.

We present two methods of rapidly (less than 1 ms) identifying contact formations from force sensor patterns, including friction and measurement uncertainty. Both principally use force signals instead of positions and detailed geometric models. First, fuzzy sets are used to model patterns and sensor uncertainty; membership functions are generated automatically from training data. Second, a neural network is used to generate confidence levels for each contact formation. Experimental results are presented for both classifiers, showing excellent results. New insights into the data sets are discussed, and a modified training method is presented that further improves the performance. The classification techniques are discussed in the context of robot programming by demonstration.

Robots have been used successfully in structured settings, where the environment is controlled; this research is inspired by the vision of robots moving beyond structured, controlled settings. The work focuses on the problem of teaching robots force-based assembly skills from human demonstration. To avoid position dependencies, force-based discrete states (contact formations) are used to describe qualitatively how contact is being made with the environment. Sensorimotor skills are modeled using a hybrid control model, which provides a mechanism for combining continuous low-level force control with higher-level discrete event control. A change in qualitative, discrete state constitutes an event and triggers a new control command to the robot, which moves the assembly toward a new contact formation. In this way, the skill execution is not dependent on absolute position but rather responds to changes in the force-based qualitative state. Experimental results are presented which validate the approach and show how skill acquisition can be accomplished even with an imperfect demonstration.

Contact formations have proven useful for programming robots by demonstration for operations involving contact. These techniques require real time recognition of contact formations. Single ended contact formation (SECF) classifiers using only the force/torque measured at the wrist of the robot have been shown to be quite effective for this purpose. To function properly, however, previous SECF classifiers have required a sizable training set and a constant pose between the force/torque sensor and the manipulated object. Thus, if an object is re-grasped and the pose changes, one expects to have to repeat the creation of the training set. We discuss the impact of sensor-object pose changes have on two successful classifiers. Experimental data shows that they perform poorly when sensor-object pose changes. We discuss a method to regain the performance of both classifiers while minimizing the retraining necessary.

Robots have been used successfully in structured settings, where the environment is controlled; this research is inspired by the vision of robots moving beyond the structured, controlled settings. The work focuses on the problem of learning low-level force-based assembly skills from human demonstration. To avoid position dependencies, force-based discrete states are used to describe qualitatively how contact is being made with the environment. Sensorimotor skills are modeled using a hybrid control model, which provides a mechanism for combining continuous low-level force control with higher level discrete event control. A change in qualitative, discrete state constitutes an event and triggers a new control command to the robot. In this way, the skill execution is not dependent on absolute position but rather responds to changes in the force-based qualitative state. Experimental results are presented which validate the approach and show how skill acquisition can be accomplished even with an imperfect demonstration.

AERCam is a free-flying camera being developed by NASA to assist in Space Shuttle or Space Station operations. We have developed a system for controlling AERCam remotely from the ground when significant communication delays are involved and have simulated its use. Our telerobotic control system includes a predictive display that is based on a simulation of Shuttle and AERCam dynamics. For a number of physical and numeric reasons, the behavior of the remote AERCam system may drift from what is expected by the predictive simulation on the ground. To correct for this, we have developed a technique for periodically reestablishing correspondence of the ground system with AERCam based on data about AERCam's actual behavior. Our system also provides a basis for development of more advanced autonomous AERCam ground control systems in the future.

The motivation behind this work is to transfer force-based assembly skills to robots by using human demonstration. For this purpose, we model the skills as a sequence of contact formations (which describe how a workpiece touches its environment) and desired transitions between contact formations. In this paper, we present a method of identifying single-ended contact formations from force sensor patterns. Instead of using geometric models of the workpieces, fuzzy logic is used to learn and model the patterns in the force signals. Membership functions are generated automatically from training data and then used by the fuzzy classifier. This classification scheme is used to learn desired sequences of contact formations which comprise a force-based skill. Experimental results are presented which use the technique to extract skill information from human demonstration data.

This paper presents a pattern recognition approach to identifying contact formations from force sensor signals. The approach is sensor-based and does not use geometric models of the workpieces. The design of a fuzzy classifier is described, when membership functions are generated automatically from training data. The technique is demonstrated using supervised learning. Test results are included for experiments using both rigid and non-rigid workpieces. The technique is discussed in the context of robot programming by human demonstration.

The Universities Space Automation and Robotics Consortium (USARC) was established to promote research into robotics and telerobotics for remote applications. An important part of the work of the Consortium has been the design and implementation of the Telerobotic Construction Set (TCS), which enables the building of modular telerobotic networks. Online and off-line performance analyses are integrated into TCS using quantitative analytical models. This provides the capabilities of measuring and predicting performance and system work loads quantitatively under different conditions, such as different levels of remote autonomy or different operator interfaces. This paper presents the methodology used in the performance/workload analysis and describes experiments, measuring teleoperation performance under time delay.

The establishment of a unique infrastructure for distributed robotics and remote operations research within an educational environment is reported. The distributed laboratory consists of sites at four universities and NASA's Johnson Space Center. The distributed laboratory configuration provides the opportunity to quantitatively study the effects of various system components and technologies on overall telerobotic task performance. The ability to execute representative inspection and manipulation tasks with multiple control, robot, and performance/workload monitoring sites simultaneously connected has been demonstrated. Operations are carried out on a routine basis. During the process, needs for hardware and software standards development have been identified. The current implementation provides a basis for linking government, industrial, and university facilities to realize a truly collaborative research and development environment, enabling graduate students to experience educational opportunities that would otherwise not be possible.>

An integrated approach to developing the control software for efficient and dependable manufacturing systems is presented. The formal model of a manufacturing system is used in planning the sequence of operations of each class of jobs to be manufactured by this system. To achieve efficiency, the reservation table technique is used to create optimum cyclic job-shop schedules for processing a batch of jobs. To achieve dependability, a plan-oriented fault detection and correction strategy is proposed.>

The authors have coined the term teleautonomous to describe methods for producing intelligent action at a distance. Teleautomation goes beyond autonomous control in that it blends in human intelligence and action as appropriate. It goes beyond teleoperation in that it incorporates as much autonomy as is possible or reasonable. A novel approach for solving one of the fundamental problems facing teleautonomous systems is discussed in detail: the need to overcome time delays due to telemetry and signal propagation. Concepts called time and position clutches are introduced; these allow the time and position frames, respectively, between the local user control and the remote device being controlled to be desynchronized. The design and implementation of these mechanisms lead to substantial telemanipulation performance improvements, including the novel result of improvements even in the absence of time delays. The controls also yield a simple protocol for handoffs of the control of manipulation tasks between local operators and remote systems.>

The authors' long-term goal is to discover reasonable constraints under which an automatic uncertainty-handling strategy (for robot part-mating tasks) is guaranteed to succeed. As the first step they introduce a concept of contact formations to describe contacts among parts in a system, aiming at reducing the dimensionality of assembly verification. They also describe a technique for identifying contact formations in spite of errors in sensing and geometric uncertainties. It is impossible to verify termination conditions in general. The notion of design constraints is introduced, and design constraints for which verification can be guaranteed are formulated. The constraints are reasonable in the sense that they do not impose unrealistic conditions on typical designs. Results of implementation on a robot system consisting of PUMA robot with RTI force/torque sensors support the theoretical derivations and show empirically that the theoretical constraints can be relaxed somewhat and good results still be obtained.>

High-precision assembly tasks cannot be successfully done by robots without taking into account the uncertainties that can cause failure of robot motion. The authors address this problem by planning robot motions at two levels: nominal planning, which assumes no uncertainty, and dynamic replanning, to deal with uncertainties that would cause nominal plans to fail. They introduce a replanning approach based on knowledge of contacts among assembly parts. It consists of patch planning to resolve the case when a commanded robot motion prematurely stops at a contact other than those planned, and motion strategy planning, to regulate robot motions in order to guarantee the eventual success of a task. A task-independent strategy for patch-plan generation based on concepts of contact planes and abstract obstacles is developed. It is also shown how to apply motion strategies so that, under proper design and motion constraints, the replanning can be guaranteed to succeed.>

An important issue in real-time computing is the development of a sufficiently abstract computational model. This model must enable one to specify, analyze, and implement distributed real-time systems. Therefore, there must also be a programming language based on the model. A description is given of such a programming language and its operational semantics. In the design of the language the applicative paradigm is extended to permit specification of parallelism, distribution, and time and temporal constraints. The language has constructs that use ideas from temporal logic and polymorphism to specify timing constraints. It uses the concept of events and a declarative event-handling style to represent communication and asynchrony. The formal model described is an operational semantics for the language and is based on dynamic algebras. The initial structure of the abstract machine for the language is described, and examples of transition rules are presented.>

Some of the fundamental issues and tradeoffs involved in the translation and execution of programs written in the Ada language and intended for distributed execution are examined. The memory access architecture, binding time and degree of system homogeneity are the three basic characteristics in terms of which target systems can be described. Library subprograms and library packages are identified as natural distributable units of the language. The program-to-process/memory mapping and the unit of the language to be distributed are the key issues in the distribution of Ada. The implications of various alternatives for these are analyzed.>

A novel method is presented for grouping range image regions such that each group of regions represents a meaningful part of an object. The set of regions, defined as a convex region set (CRS), is obtained by analyzing the boundary types between a pair of regions. The boundary types are classified as convex, concave and jump boundaries. If two regions share a convex boundary it is assumed that they are inseparable regions, thus describing the same part (object). The CRSs are determined by a region boundary graph (RBG) which is defined as a graph whose nodes represent regions, and the edges represent boundaries: convex and concave. Since jump boundaries represent no physical contact in 3-D, they are represented as null edges. A CRS is defined as a set of regions (or nodes in an RBG) such that for each pair of regions in the set, there is a path, which is represented only by convex edges. The physical interpretation is that a CRS represents part of an object such that the regions in the set cannot be separated.>

The authors assume a nominal motion plan for the zero-error situation and devise a simple replanning strategy based on the availability of force, moment, and position sensors to handle errors that may arise during program execution. They develop design constraints relating the parameters of the strategy, parameters of the sensor, control and manufacturing errors, and nominal design parameters. If the constraints are satisfied, the replanning strategy can theoretically be guaranteed to be successful. The constraints are shown to be reasonable in the sense that they do not impose unrealistic conditions on typical design. Simulation results uphold the theoretical derivations and show empirically that the theoretical constraints can be relaxed somewhat with excellent results obtained.>

As a result of recent advances in artificial intelligence, human cognitive modelling, autonomous systems and telerobotics, there is an opportunity to broaden our concepts of technology for projecting action at a distance. We draw on these advances to develop a conceptual and architectural framework that enables efficient projection in time and space of intermingled manipulation and cognition tasks. Where AI-based autonomous systems have previously been concerned with human supervisory intervention primarily at a cognitive level, we add methods for rendezvous, capture and rehandoff of embedded manipulation tasks. Where telerobotics has been concerned with the projection of sensory-motor manipulation, we add the projection of cognitive processing. Thus extended, the two technologies mirror one another and merge into one of "tele-autonomous systems". We introduce notions of how the sensory, cognitive and motor functions of tele-autonomous systems can be factored and transferred back and forth between human and machine. We illustrate how the times to complete tele-autonomous tasks can be reduced through time and space constraint relaxations effected through simple controls: We employ the concepts of forward simulation and predictor display, augmented by "time and position clutches", "time ratio controls" and "time brakes", to control the resulting manipulation paths and event transitions. We sketch some generic architectural and human interface implications of these methods. Finally, we describe our environment for exploring these methods and the results of some recent experiments.

This paper addresses the problem of extracting certain types of surfaces for 3-dimensional object recognition in the presence of partial occlusion and noise using range information. We restrict consideration to man made industrial parts. In this case, we need only work with a small set of surface shapes such as planes, cylinders, and spheres since such shapes are common in industrial parts and it is only necessary to recognize and locate a sufficient set of surface regions to uniquely distinguish the part being observed from all others that might be present. We describe a way of extracting the parameters of these types of surfaces using normal analysis. The use of surface parameters then allows efficient and robust use of a matching process for object recognition and pose determination even though there are many undefined or occluded surface regions.

A graphical off-line robot programming system should not only be able to simulate various types of robot movement graphically, it should also be able to use graphics to interact with binary sensors, actuators and etc., in order to simulate logic-related and other functions of robot languages, such as testing and branching, looping, communication and external event handling graphically. We present a graphical off-line robot programming system which has some of these additional features. In particular, it incorporates a geometrical representation of logical conditions into the geometrical representation of the robot and workspace and it allows conditional statements to be programmed in a geometric setting.

This paper examines, in the context of distributed execution, the meaning of Ada constructs involving time. In the process, unresolved questions of interpretation and problems with the implementation of a consistent notion of time across a network are uncovered. It is observed that there are two Ada mechanisms that can involve a distributed sense of time: the conditional entry call, and the timed entry call. It is shown that a recent interpretation by the Language Maintenance Committee resolves the questions for the conditional entry calls but results in an anomaly for timed entry calls. A detailed discussion of alternative implementations for the timed entry call is made, and it is argued that: 1) timed entry calls imply a common sense of time between the machines holding the calling and called tasks; and 2) the measurement of time for the expiration of the delay and the decision of whether or not to perform the rendezvous should be made on the machine holding the called task. The need to distinguish the unreadiness of the called task from timeouts caused by network failure is pointed out. Finally, techniques for realizing a single sense of time across the distributed system (at least to within an acceptable degree of uncertainty) are also discussed.

The scheduling of timed tasks is generally based, at the hardware level, upon the use of time intervals. For example, most microprocessor families provide their only hardware support for timing control in the form of a programmable interval timer chip accessible as an I/O device over the system bus. In this paper we will argue that a more natural and elegant solution bases timing on a local (to a particular CPU) absolute timer. Furthermore, we will show that the desired timing functions can be provided by simple extensions to existing CPU architectures. The widespread use of the ``time interval'' view has also influenced, in a negative way, the design of many programming languages. An important example is Ada, a language designed with real-time multitasking explicitly in mind. We will describe the difficulty with the current timing methods used in Ada, and present a method for overcoming the timing weakness by using the proposed timing mechanisms, while still remaining within the definition of the Ada language.

Grip determination is essential to any task-level planning process. The complete force/moment equations are presented for grasping employing a rigid two-fingered gripper with a thin elastic layer on the contacting surface. The surface contact is modeled as a linear pressure variation. The quality measure of a grip is taken to be the coefficient of friction needed to keep the held object from slipping between the fingers under applied forces and moments. The lower the coefficient of friction, the better the grip. Incorporation of this evaluation into general grip selection strategy is discussed, and several examples are given.

Grip determination is essential to any task level planning process and to situations in which the pose of the part to be grasped is not known a priori. This paper presents the complete force/moment equations for grasping via a rigid two-fingered gripper. Surface contact is modeled as a linear pressure variation. The quality measure of a grip is taken to be the coefficient of friction needed to keep it from slipping under applied forces and moments, the lower the coefficient of friction, the better the grip. The incorporation of this evaluation into a general grip selection strategy is discussed and several examples given.

A new approach to model based object recognition employing multiple views is described. The emphasis is given on the determination of camera viewpoints for succesive views looking for distinguishing features of objects. The distance and direction of the camera are determined separately. The distance is determined by the size of the object and the feature, while the direction is determined by the shape of the feature and the presence of the occluding objects.

In this paper, an approach is described for recognizing and locating partially hidden objects in an image. The method is based upon matching pairs of boundary segments of the template of an object with pairs of boundary segments in the image. Using a Bayesian based signal detection approach, pairs of segments are selected from the template of the object such that the probability of correctly identifying the object given that the pair is matched in the image is close to one. Assuming that models of all objects which might appear in the scene (a reasonable assumption for industrial applications) are known a priori, suitable pairs of segments can be determined a priori. Preliminary investigation suggests that the technique is robust and that subsecond recognition time can be achieved.

The problem of recognizing an object from a partially occluded boundary image is considered, and the concept of saliency of a boundary segment is introduced. Saliency measures the extent to which the boundary segment distinguishes the object to which it belongs from other objects which might be present. An algorithm is presented which optimally determines the saliency of boundary segments of one object with respect to those of a set of other objects. An efficient template matching algorithm using templates weighted by boundary segment saliency is then presented and employed to recognize partially occluded parts. The results of these experiments illustrate the effectiveness of the new technique.

The problem of automatically determining gripping positions for objects based upon geometrical knowledge of the object and its environment is addressed. Both the question of what constitutes a good grip and the efficiency of the computational algorithms are considered. Two new criteria for the stability of a grip are proposed: resilience to slippage and twisting in the gripper due to external forces and torques. Resilience to slippage is expressed in terms of friction effects of the surfaces involved, the shape of the contact between the gripper and object, and the distance of the grip point from the center of mass of the object. Two new performance measures are introduced to reflect resilience to twisting. A general grip planning strategy is introduced that is both run-time efficient and robust. The problem is divided into three parts: one depends only upon the geometry of the object to be gripped, the second takes into account a priori geometric constraints, and the third handles constraints unknown until run-time.

The use of Ada to program a robot-based manufacturing cell, an example of real-time embedded system, is described. The computing issues in manufacturing cells are discussed with respect to Ada. Using an experimental manufacturing cell presently under construction as an example, a strategy for robot programming based on Ada is described. A case study of the software for the vision subsystem is used to illustrate a central feature of Ada, namely, data abstraction. Additional important features of Ada for software management, that is, multitasking and program abstraction through generics and operator overloading, are also illustrated. The principal advantages and difficulties in using Ada for programming robot-based manufacturing cells are summarized on the basis of the software issues described and the case study.