Modern modeling of a classic multiperiod problem

In this paper we discuss the integration of modeling and programming in order to solve problems in operations research and decision support. Our goal is to integrate modeling into the larger programming scheme of things and, conversely, to inject programming into modeling. This integration leads to a technologically open way to handle problems in OR, AI, etc. since the full programming arsenal can be brought to bear on these problems and since both problem solving and model management can be abetted by software engineering techniques. Here, by means of variations on a single example, we will illustrate the solution of a linear program, a goal program, a disjunctive program, a hill climbing search, a branch and bound search, and a parallel solution to a stochastic problem.     

Holarchy formation and optimization in holonic manufacturing systems with contract net

Holonic manufacturing systems (HMS) is based on the notion of holon, an autonomous, cooperative and intelligent entity to provide a econfigurable, flexible and decentralized manufacturing environment to respond to changing needs and opportunities. A set of holons that cooperate to achieve a goal forms a holarchy. How to design a mechanism to form a holarchy to achieve a goal while minimizing the overall cost is a challenge. The objectives of this paper are to propose models and develop collaborative algorithms to guide the holons to form a holarchy to coherently move toward the desired goal state ultimately. We adopt contract net protocol (CNP) to model mutual selection of holons in forming a holarchy. We formulate a holarchy optimization problem to minimize the cost subject to the feasibility constraints. To analyze the feasibility of a holarchy, a Petri net (PN) model is proposed. As classical PN models do not take into account the cost involved in firing transitions, we augment the PN model with cost functions in the problem formulation. Due to the distributed architecture of HMS, the internal structure of each potential holarchy that acts as bidder in CNP is not available to the manager. A key issue is to determine the feasibility of a holarchy without constructing the whole PN model of the given hierarchy. We study the feasible conditions for a holarchy and propose a collaborative algorithm to analyze the feasibility and award contracts to holons without constructing the whole model of a holarchy.     

Inferring robot goals from violations of semantic knowledge

A growing body of literature shows that endowing a mobile robot with semantic knowledge and with the ability to reason from this knowledge can greatly increase its capabilities. In this paper, we present a novel use of semantic knowledge, to encode information about how things should be, i.e. norms, and to enable the robot to infer deviations from these norms in order to generate goals to correct these deviations. For instance, if a robot has semantic knowledge that perishable items must be kept in a refrigerator, and it observes a bottle of milk on a table, this robot will generate the goal to bring that bottle into a refrigerator. The key move is to properly encode norms in an ontology so that each norm violation results in a detectable inconsistency. A goal is then generated to bring the world back in a consistent state, and a planner is used to transform this goal into actions. Our approach provides a mobile robot with a limited form of goal autonomy: the ability to derive its own goals to pursue generic aims. We illustrate our approach in a full mobile robot system that integrates a semantic map, a knowledge representation and reasoning system, a task planner, and standard perception and navigation routines.     

Allocating Independent Tasks to Parallel Processors: An Experimental Study

We study a scheduling or allocation problem with the following characteristics: The goal is to execute a number of unspecified tasks on a parallel machine in any order and as quickly as possible. The tasks are maintained by a central monitor that will hand out batches of a variable number of tasks to requesting processors. A processor works on the batch assigned to it until it has completed all tasks in the batch, at which point it returns to the monitor for another batch. The time needed to execute a task is assumed to be a random variable with known mean and variance, and the execution times of distinct tasks are assumed to be independent. Moreover, each time a processor obtains a new batch from the monitor, it suffers a fixed delay. The challenge is to allocate batches to processors in such a way as to achieve a small expected overall finishing time. We introduce a new allocation strategy, the Bold strategy, and show that it outperforms other strategies suggested in the literature in a number of simulations.     

Disruptive technology: How Kodak missed the digital photography revolution

The purpose of this paper is to analyze how a firm responds to a challenge from a transformational technology that poses a threat to its historical business model. We extend Christensen’s theory of disruptive technologies to undertake this analysis. The paper makes two contributions: the first is to extend theory and the second is to learn from the example of Kodak’s response to digital photography. Our extensions to existing theory include considerations of organizational change, and the culture of the organization. Information technology has the potential to transform industries through the creation of new digital products and services. Kodak’s middle managers, culture and rigid, bureaucratic structure hindered a fast response to new technology which dramatically changed the process of capturing and sharing images. Film is a physical, chemical product, and despite a succession of new CEOs, Kodak’s middle managers were unable to make a transition to think digitally. Kodak has experienced a nearly 80% decline in its workforce, loss of market share, a tumbling stock price, and significant internal turmoil as a result of its failure to take advantage of this new technology.     

Voices that cannot be heard: Can shyness explain how we communicate on Facebook versus face-to-face?

Social networking sites have gained popularity among all populations, especially young adults. Personality traits were found to be predictive of how individuals use social media. Therefore, this study sought to examine the association between shyness and self-disclosure to a Facebook friend as well as self-disclosure to a face-to-face friend. Two studies were conducted. The first study tested how shyness and social loneliness are related to self-disclosure to a Facebook friend to whom an individual talks most often. The second, follow-up study tested how shyness is related to self-disclosure to a Facebook friend to whom a person speaks to only though Facebook, and also to a face-to-face friend to whom the participants talk only face-to-face and never through Facebook. Participants were college students from a large research university in the United States. Study 1 found a negative association between shyness and self-disclosure to a Facebook friend. Study 2 found a negative association between shyness and self-disclosure to a face-to-face friend. The theoretical implications and limitations are discussed.     

A dung beetle-inspired robotic model and its distributed sensor-driven control for walking and ball rolling

A typical approach when designing a bio-inspired robot is to simplify an animal model and to enhance the functionality of interest. For hexapod robots, this often leads to a need of supplementary mechanics to become multifunctional. However, a preferable solution is to employ the embodied multifunctional capabilities of the animal as inspiration for robot design. Using this approach, we present a method for translating the kinematic chain of a dung beetle from which an accurate kinematic model and a simplified one were simulated and compared. The beetle was selected due to its multifunctional locomotory capabilities including walking as well as standing on and rolling a ball. For testing the models, we developed a distributed sensor-driven controller that can generate walking and ball-rolling behaviors. A comparison of the two modeling approaches shows a similar performance with regards to walking stability and accuracy, but differences when it comes to speed and multifunctionality. This is because the accurate model is able to use its legs to walk faster and roll a ball, which the simplified one is not. In conclusion, the accurate model of a dung beetle-inspired robot is advantageous as it, together with our novel control mechanism, is able to elicit behaviors comparable to those of the real dung beetle (i.e., walking and rolling a dung ball).     

A Flexible Architecture for Navigation Control of a Mobile Robot

In order to meet new mission requirements or to adapt environmental changes, robots perform a task switch or role switch. When a robot is required to perform a specific task, which is beyond its skills, it might need to request other robots' help. In order to improve the flexibility, we use the concept of a software mobile agent to design an architecture called Virtual Operator MultiAgent System (VOMAS). In VOMAS, intelligent agents, called a virtual operator (VO) and a robot agent (RA), work together to control a robot to fulfill a specific task. Each task is represented by a VO and the RA handles reactive control. Based on this architecture, VOMAS can perform the dynamic task switch to handle missions, which are not initially given. Two case studies, a wheelchair and formation control, are introduced for explaining our approach and to show the feasibility and effectiveness of dynamic task switch. Furthermore, VOMAS can be treated as a telerobotic architecture, and the network-load test shows that VOMAS requires less network load than direct control     

A fully-digital and ultra-low-power front-end for differential capacitive sensors

In this paper, we present a simple, compact and low-power interface for differential capacitive sensors with a direct digital output. The complete system is composed with a current to voltage converter, an integrator, a comparator and a one-bit digital to analog converter as a feedback. The so-obtained Sigma–Delta modulator is able to deliver directly a bit stream with a ratio of logical ‘1’ directly proportional to the differential capacitance to be measured. A partially integrated prototype has been realized to demonstrate accuracy and non-linearity compatible with a 9-bit sensor.

     

Formal executable semantics for conformance in the MDE framework

In the MDE framework, a metamodel is a language referring to some kind of metadata whose elements formalize concepts and relations providing a modeling language. An instance of this modeling language which adheres to its concepts and relations is called a valid model, i.e., a model satisfying structural conformance to its metamodel. However, a metamodel frequently imposes additional constraints to its valid instances. These conditions are usually written in OCL and are called well-formedness rules. In presence of these constraints, a valid model must adhere to the concepts and relations of its metamodel and fullfill its constraints, i.e., a valid model is a model satisfying semantical conformance to its metamodel. In this work, we provide a formal semantics to the notions of structural and semantical conformance between models and metamodels building on our previous work. Our definitions can be automatically checked using the ITP/OCL tool.     

Plan Execution Based on Active Perception: Adding Hints to Plans

In this paper we present a complete control architecture for a mobile robot which enables it to achieve a set of proposed goals with a high degree of autonomy and to react to the changing environment in real time. Autonomy and robustness are achieved through careful selection and incremental implementation of a set of basic Motor-Behaviors that interpret the sensor readings (sonar, vision and odometric sensors) and actuate the motors. The plan is provided by a user, and is expressed as a sequence of goals and a series of hints on how to achieve them. These hints are based on the user's knowledge of the environment and of the robot's behavioral and perceptual abilities. A new set of behaviors, called Conductor-Behaviors, which inspect and modify Motor-Behaviors' attributes, have been introduced in order to link the robot's Motor-Behaviors to the user's plan. Finally, a canonical set of symbols, attached to the Motor-Behaviors, serves as well grounded symbols that the user can utilize to express the plans. We also report experimental results with a real robot that demonstrate how plans expressed as goals and hints to achieve them improve the robot's performance.     

Design of phononic materials/structures for surface wave devices using topology optimization

We develop a topology optimization approach to design two- and three-dimensional phononic (elastic) materials, focusing primarily on surface wave filters and waveguides. These utilize propagation modes that transmit elastic waves where the energy is contained near a free surface of a material. The design of surface wave devices is particularly attractive given recent advances in nano- and micromanufacturing processes, such as thin-film deposition, etching, and lithography, which make it possible to precisely place thin film materials on a substrate with submicron feature resolution. We apply our topology optimization approach to a series of three problems where the layout of two materials (silicon and aluminum) is sought to achieve a prescribed objective: (1) a grating to filter bulk waves of a prescribed frequency in two and three dimensions, (2) a surface wave device that uses a patterned thin film to filter waves of a single or range of frequencies, and (3) a fully three-dimensional structure to guide a wave generated by a harmonic input on a free surface to a specified output port on the surface. From the first to the third example, the resulting topologies increase in sophistication. The results demonstrate the power and promise of our computational framework to design sophisticated surface wave devices.     

Semantic Network Language Generation based on a Semantic Networks Serialization Grammar

This paper studies the Semantic Network Language Generation (SNLG), which is used to generate natural language from the information represented as Semantic Networks (SN). After a brief analysis of the challenges faced by SNLG, a Semantic Network Serialization Grammar (SNSG) is proposed to generate natural language from semantic networks. The SNSG is constituted by four components: (a) a semantic pattern approach to serializing a trivial semantic star into a language stream. (b) a transformative generation to serialize a trivial semantic tree by serializing semantic star recursively. (c) a procedure of trivialization to convert any complicated semantic star or semantic tree into composition of trivial semantic tree. (d) a mechanism of semantic pattern priority and semantic pattern network to guarantee a sentence generated from a semantic tree to be well formed. Based on the SNSG, a new approach of the content planning for SNLG is proposed to improve the content integrity. For discourse planning, a trivialization time splitting method is presented to make well-formed sentence, and a splitting time aggregation method is proposed to improve the readability of sentence. Finally a fully semantized Semantic Wiki system, the Natural Wiki, is developed to verify and demonstrate the theory and techniques addressed in this paper.     

Generating queries and replies during information-seeking interactions

Analysis of naturally occurring information-seeking dialogues indicates that they usually consist of a number of distinct discourse segments, such as a greeting segment, a request issued by a user, an optional clarification segment, a transfer of information segment and a final closing segment. The clarification interaction is often initiated by the information provider and it may be due to one of the following reasons: (1) there is confusion regarding the user's intentions, (2) there is insufficient information to formulate a plan to satisfy a recognized intention, or (3) there is difficulty in formulating a plan that satisfies a recognized intention. Once the information provider determines the user's intention and formulates a plan to achieve this intention, the information transfer phase is initiated to inform the user about the proposed plan.In this paper, we present a mechanism for generating queries during the clarification stage and answers during the information transfer stage. Given a hierarchical representation of the alternatives possibly intended by a user and the probabilities of these alternatives, our mechanism determines the hierarchy level at which a query must be directed and the query to be posed in order to determine the alternative intended by the user. Once the user's intentions are ascertained, the mechanism determines whether additional information is required and the manner in which queries may be posed to acquire this information. When a user's intentions cannot be satisfied by means of a single plan, our mechanism enters into a negotiation process to alter the user's specifications until a valid plan is formulated. In the final stages of the interaction, the mechanism determines the information to be transferred and generates an answer to effect the transfer. The mechanisms for negotiation and for the generation of queries and answers described in this paper have been implemented in a system called , a computerized information providing system that functions as a travel agent.     

Requirements-driven deployment

Deployment is a main development phase which configures a software to be ready for use in a certain environment. The ultimate goal of deployment is to enable users to achieve their requirements while using the deployed software. However, requirements are not uniform and differ between deployment environments. In one environment, certain requirements could be useless or redundant, thereby making some software functionalities superfluous. In another environment, instead, some requirements could be impossible to achieve and, thus, additional functionalities would be required. We advocate that ensuring fitness between requirements and the system environment is a basic and critical step to achieve a comprehensive deployment process. We propose a tool-supported modelling and analysis approach to tailor a requirements model to each environment in which the system is to be deployed. We study the case of a contextual goal model, which is a requirements model that captures the relationship between the variability of requirements (goal variability space) and the varying states of a deployment environment (context variability space). Our analysis relies on sampling a deployment environment to discover its context variability space and use it to identify loci in the contextual goal model where a modification has to take place. Finally, we apply our approach in practice and report on the obtained results.     

Postural analysis of paramedics simulating frequently performed strenuous work tasks

Paramedics who perform emergency rescue functions are highly susceptible to musculoskeletal injuries. Through an interview and survey process firefighters, many of whom are cross-trained paramedics in a consortium of 14 suburban fire departments, identified and rated tasks that were perceived to be both strenuous and frequently performed. The objective of the current study was to describe the working postures and the forces applied as firefighter/paramedics (FF/Ps) simulated specific roles within the following tasks identified by the survey: (1) transferring a patient from a bed to a stretcher using bedsheets, (2) transferring a patient from the ambulance stretcher to a hospital gurney, (3) carrying a victim down a set of stairs and around a landing using a stairchair, (4) carrying a victim down a set of stairs and around a landing using a backboard, and (5) carrying a victim down a set of stairs using a stretcher. Ten two-person teams of FF/Ps participated and were videotaped to obtain postural data for the upper and lower extremities as they performed each role in the simulated two-person tasks. Trunk postures were obtained using lumbar motion monitors. Static hand forces were estimated using a hand-held dynamometer at the most physically demanding points for each role within each task. The postural and force data were averaged across subjects performing identical roles to quantify the postures assumed by the FF/Ps at the most strenuous moments during task performance. Based on these analyses we concluded that: (1) when transferring victims from a bed to a stretcher the FF/P on the bed was able to maintain an upright and more stable posture by standing as opposed to kneeling, (2) an interface board should be used to reduce the frictional forces when transferring victims from a bed to a stretcher or from a stretcher to a gurney, thereby reducing the need to lift the victim with flexed torsos and/or shoulders, and (3) equipment and training that encourages the FF/P in the leader role to walk facing forward during victim transport, especially when descending stairs, potentially results in safer transit.     

文本搜索排序中构造训练集的一种方法

在文本搜索领域,用自学习排序的方法构建排序模型越来越普遍。排序模型的性能很大程度上依赖训练集。每个训练样本需要人工标注文档与给定查询的相关程度。对于文本搜索而言,查询几乎是无穷的,而人工标注耗时费力,所以选择部分有信息量的查询来标注很有意义。提出一种同时考虑查询的难度、密度和多样性的贪心算法从海量的查询中选择有信息量的查询进行标注。在LETOR和从Web搜索引擎数据库上的实验结果,证明利用本文提出的方法能构造一个规模较小且有效的训练集。     

A hybrid system approach for supporting digital libraries

A digital library (DL) consists of a database which contains library information and a user interface which provides a visual window for users to search relevant information stored in the database. Thus, an abstract structure of a digital library can be defined as a combination of a special purpose database and a user-friendly interface. This paper addresses one of the fundamental aspects of such a combination. This is the formal data structure for linking an object oriented database with hypermedia to support digital libraries. It is important to establish a formal structure for a digital library in order to efficiently maintain different types of library information. This article discusses how to build an object oriented hybrid system to support digital libraries. In particular, we focus on the discussion of a general purpose data model for digital libraries and the design of the corresponding hypermedia interface. The significant features of this research are, first, a formalized data model to define a digital library system structure; second, a practical approach to manage the global schema of a library system; and finally, a design strategy to integrate hypermedia with databases to support a wide range of application areas. Received: 15 December 1997 / Revised: June 1999     

Correlation between learning (probability of success) and fuzzy entropy in control of intelligent robot's part macro-assembly tasks with sensor fusion techniques

A correlation between a learning and a fuzzy entropy, using the control of robotic part macro-assembly (part-bringing) task as an example, is introduced. Two intelligent part-bringing algorithms, to bring a part from an initial position to an assembly hole or a receptacle (target or destination) for a purpose of a part mating in a partially unknown environment containing obstacles, related to a robotic part assembly task are introduced. An entropy function, which is a useful measure of the variability and the information in terms of uncertainty, is introduced to measure its overall performance of a task execution related to the part-bringing task. The degree of uncertainty associated with the part-bringing task is used as an optimality criterion, e.g. minimum entropy, for a specific task execution. Fuzzy set theory, well-suited to the management of uncertainty, is used to address the uncertainty associated with the macro-assembly procedure. In the first algorithm, a macro-assembly, locating various shaped assembly holes (targets) in the workspace corresponding to the shapes of the parts and then bringing the part to the corresponding target, despite existing obstacles is introduced. This is accomplished by combining a neural network control strategy coordinating with a mobile rectilinear grid composed of optical sensors as well as fuzzy optimal controls. Depending on topological relationships among the part's present position, the position of obstacles, and the target position in the workspace, a specific rulebase from a family of distinct fuzzy rulebases for avoiding obstacles is activated. The higher the probability, the input pattern (or value) of the neural network to be identified as the desired output is, the lower the fuzzy entropy is. Through the fuzzy entropy, a degree of identification between the input pattern and the desired output of the neural network can be measured. In the second algorithm, a macro-assembly with a learning algorithm and a sensor fusion for bringing the part to the target is introduced. By employing a learning approach, the uncertainty associated with the part-bringing task is reduced. The higher the probability of success is, the lower the fuzzy entropy is. The results show clearly the correlation between a probability of success related to the task execution of the part-bringing and the fuzzy entropy, and also show the effectiveness of above methodologies. The proposed technique is not only a useful tool to measure the behaviour of the learning but applicable to a wide range of robotic tasks including motion planning, and pick and place operations with various shaped parts and targets.     

Toward an analytical solution to task allocation,processor assignment,and performance evaluation of network processors

Message-passing network-based multicomputer systems emerge as a potential economical candidate to replace supercomputers. Despite enormous effort to evaluate the performance of those systems and to determine an optimum scheduling algorithm (which is known as an NP-complete), we still lack a complete and a good performance model to analyze distributed computing systems. The model is complete if all system parameters, network parameters, communication overhead parameters, and application parameters are considered explicitly in the solution. A good performance model, like a good scientific theory, should be able to explain all normal behavior, predict any abnormality in the system, and allow the designer to adjust some of the parameters, while abstracting unimportant details.In this paper, we develop a good and complete performance model, which predicts a minimum finish time, equally the maximum speed up. In addition, we develop a closed form solution which forecasts the optimum share of the parallel job (task) that has to be assigned to each processor (node). Task assignment may then be undertaken in a distributed manner, which enhances the distributive nature of the system and, thus, improve system performance. Most importantly, our analytical solution presents a mechanism to select, based on system and application parameters, the optimum number of processors (nodes) that has to be assigned to a given parallel job.The model helps the designer to study the effect of each individual parameter on the overall system performance. This then becomes a tool for a designer of a multicomputer system to manage limited resources in an optimal manner paying attention only to those parameters that are most critical.