- "Facilitating
Meetings with Playful Feedback", Ying Zhang, Marshall Bern, Juan
Liu, Kurt Partridge, Bo Begole, Bob Moore,
Jim Reich, CHI Work in Progress, 2010
Abstract
Effective group meetings are important for the productivity of
corporations. Various types of meeting facilitators have been developed
over the past couple of years. We present a prototype that is unique
because it captures both individual and group behaviors and provides real time playful feedback. The
portable prototype includes a set of table-top microphones with an audio
interface to a laptop PC, where audio data are processed and an
avatar-based UI displays the shared state of individual and group
behaviors during a meeting. The interface reveals not only level of
participation, but also several other
meaningful but harder to detect behaviors such as turn taking,
interruptions, and group laughter. The presentation's design is
deliberately playful to keep participants monitor, self-estimate and
improve their meeting behavior.
- "Controlling
Error Propagation in Mobile-Infrastructure Based Localization", Ying
Zhang and Juan Liu, 2nd Int. Workshop on Mobile Entity Localization and
Tracking, 2009, with UbiComp 2009, LNCS 5801
Abstract
Many iterative localization schemes suffer from the
negative effect of error propagation, where sensor noise results in
estimation errors which then get accumulated and amplified over
localization iterations.
This paper extends our earlier work in mobile-infrastructure based
localization and proposes a computationally efficient error control
mechanism to mitigate the error propagation effect. In particular, we
show how the error can be characterized and controlled. Simulation
results have shown that our error control mechanism achieves comparable
location accuracy as global optimization-based localization methods and
has the advantage of being much more computationally efficient and
easily distributable.
- "Rigidity
guided localization for mobile robotic sensor networks", Changhua Wu, Ying Zhang, Weihua
Sheng, Saroja Kanchi, accepted to Int. J Ad Hoc and Ubiquitous
Computing, 2009
Abstract
This paper introduces a rigidity-guided localization
approach for mobile robotic sensor networks. The localization uses a
distance graph composed of both the robot-to-robot ranging data and the
motion trajectories from robot odometry. The motion of a robot depends on the
result of the rigidity test of its local distance graph: if the graph is
not uniquely localizable, the robot moves around in its neighborhood to
collect at least two extra ranging data with each of its neighbors in
order to make the extended graph uniquely localizable. Locally unique
maps are then merged into a globally consistent map.
- "Error Control
in Distributed Node Self-Localization", Juan Liu and Ying
Zhang, accepted to EURASIP, 2008
Abstract
Location information of nodes in an ad hoc sensor
network is essential to many tasks such as routing, cooperative sensing,
and service delivery. Distributed node self-localization is lightweight
and requires little communication overhead, but often suffers from the
adverse effects of error propagation. Unlike other localization papers
which focus on designing elaborate localization algorithms,
this paper takes a different perspective, focusing on the error
propagation problem, addressing questions such as where localization
error comes from and how it propagates from node to node. To prevent
error from propagating and accumulating, we develop an error control
mechanism based on characterization of node uncertainties and
discrimination between neighboring nodes. The error control
mechanism uses only local knowledge and is fully decentralized.
Simulation results have shown that the active selection strategy
significantly mitigates the effect of error propagation for both range
and directional sensors. It greatly improves localization accuracy and
robustness.
- "Distributed
Time-Optimal Scheduling for Convergecast in Wireless Sensor Networks", Shashidhar Gandham, Ying
Zhang, Qingfeng Huang, Computer Networks,
2008
Abstract
We consider applications of sensor networks wherein data packets
generated by every node have to reach the base station. This results in a many-to-one communication paradigm
referred to as convergecast. We are interested
in determining a TDMA schedule that minimizes the total time
required to complete the convergecast. We
consider a simple version of the problem wherein every node generates
exactly one packet. We propose a distributed convergecast
scheduling algorithm that requires at most $3N$ timeslots, where $N$
represents the number of nodes in the network. Through extensive simulations,
we demonstrate that actual number of timeslots needed is around 1.5N.
In addition to time efficiency, we prove that our convergecast
scheduling algorithm requires the nodes to buffer no more than two
packets at any instance. We propose a sleep schedule that conserves more
than 50% of the energy. We present simulation results for a real
application scenario to show that our convergecast
scheduling algorithm performs significantly better than existing convergecast algorithms.
- "Distributed
Minimal Time Convergecast Scheduling for Small
or Sparse Data Sources", Ying Zhang, Shashidhar
Gandham, Qingfeng Huang, RTSS07, 2007
Abstract
Many applications of sensor networks require the base
station to collect all the data generated by sensor nodes. As a consequence
many-to-one communication pattern, referred to as convergecast, is prevalent in sensor networks. In this
paper, we address the challenge of fast and reliable convergecast
on top of the collision-prone CSMA MAC layer. More specifically, we
extend previous work by considering the following two situations: (1)
the length of the packets generated by nodes is much smaller than the
maximum length of a data frame that can be transmitted in one time slot
and (2) not every node in the network has data to transmit and for those
that have, may have lots of data that require more than one packet. The
first situation leads to the possibility of improvement by data
piggybacking/aggregation; the second scenario arises in networks where
nodes locally store the data and serves query request on-demand. We
present distributed minimal time scheduling algorithms for both the
cases. Simulation results have shown significant performance
improvements of our new approaches over existing solutions.
- "Dynamic
Information Sharing using a Distributed Traffic Surveillance
Infrastructure", Ying Zhang and Qingfeng Huang, ITSC07, 2007
Abstract
In this paper, we propose and study a novel
distributed traffic information system. The contributions of the paper
include a road-network-aware (RNA) information publication protocol, a
distributed query processing protocol with transient memory, and an
adaptive interaction model between the two, all in the context of a
distributed traffic surveillance infrastructure. Our study focuses on
(1) the impact of various information demand characteristics on
dissemination strategies, and (2) the adaptive optimal strategies in
a distributed manner without prior knowledge of information demand
characteristics. Both theoretical and simulation results are presented.
- "Localizing
Tags Using Mobile Infrastructure", Ying Zhang, Kurt Partridge
and Jim Reich, best paper in LoCA07, Sep. 2007
Abstract
This paper presents algorithms, simulations, and empirical results of a
system that finds relative tag positions in 3D space using a new
approach called ``mobile infrastructure.'' Mobile infrastructure
consists of one or more sensors in a fixed configuration on a mobile
platform, and a set of tags affixed to objects or locations in the
environment which the users want to localize. It is especially useful in
cases where infrastructure is needed only temporarily, such as during
installation, calibration, or maintenance. Mobile infrastructure can
cover a much larger area than installed infrastructure with the same
number of sensors, and is especially useful in cases where localization
hardware costs are asymmetric, with expensive sensors and inexpensive
tags. The data collected at various positions are combined by a simple
``leapfrog'' procedure, with constrained optimization to obtain better
accuracy. Our system achieves about one foot (0.3 meter) accuracy with
$90\%$ confidence in indoor environments.
- "SDIP3:
Structured and Dynamic Information Push and Pull Protocols for
Distributed Sensor Networks", Ying Zhang and Qingfeng Huang, DOCSS07, June 2007
Abstract
We propose and study a class of structured and dynamic information push
and pull protocols for wireless sensor networks. For structured
information dissemination, our study focuses on the impact of various
information demand characteristics on dissemination along some type of
backbone structures. Our exploration of dynamic information push and
pull focuses on finding optimal strategies in a distributed manner
without prior knowledge of information demand characteristics and/or
with heterogeneous query distributions. Our theoretical analysis uses a
simple grid structure, but the protocol is applicable to arbitrary
network topologies. A distributed traffic information system is used as
the context of study and the simulation study uses a microscopic traffic
simulator to demonstrate some of the ideas discussed in the paper.
- "Mobile
Sensor Networks Self Localization based on Multi-dimensional
Scaling", Chang-Hua Wu, Weihua Sheng, Ying Zhang, IEEE
ICRA07, April 2007
Abstract
In this paper, we define a mobile self-localization (MSL) problem
for sparse mobile sensor networks, and propose an algorithm named
Mobility Assisted MDS-MAP(P), based on Multi-dimensional Scaling
(MDS) for solving the problem. For sparse sensor networks, all the
existing localization algorithms fail to work properly due to the lack
of distance or connectivity data to uniquely calculate the
geo-locations. In MSL, we use mobile sensors to add extra distance
constraints to a sparse network, by moving the mobile sensors in the
area of deployment and recording distances to neighbors at some
intermediate locations. MSL can also be used for localizing and tracking
mobile objects in a robotic or body sensor network. Experiments and
evaluations of the new algorithm are provided.
- "Minimum
Power Configuration for Wireless Communication in Sensor Networks",
Guoliang Xin, Chenyang Lu, Ying Zhang, Qingfeng
Huang, Robert Pless, ACM TOSN, 2007
Abstract
This paper proposes the Minimum Power Configuration (MPC)
approach to power management in wireless sensor networks. In contrast to
earlier research that treats different radio states
(transmission/reception/idle) in isolation, MPC integrates them in a
joint optimization problem that depends on both the set of active nodes
and the transmission power. We propose four approximation algorithms
with provable performance bounds and two practical routing protocols.
Simulations based on realistic radio models show that the MPC approach
can conserve more energy than existing minimum power routing and
topology control protocols. Furthermore, it can flexibly adapt to
network workload and radio platforms.
- "Dynamic
Balancing of Push and Pull in a Distributed Traffic Information
System", Qingfeng Huang and Ying Zhang, CCNC, 2007
Abstract
In this paper, we propose and study a novel distributed vehicle traffic
information system using a wireless sensor network. Besides the system
model, the contributions of the paper include a road network aware
information publication protocol, a distributed query processing
protocol with transient memory, and the adaptive interaction model
between the two, all in the context of a vehicle traffic information
system. Both theoretical and simulation results are presented.
- "Mobile
Self-Localization using Multi-Dimensional Scaling in Robotic Sensor
Networks", Chang-Hua Wu, Weihua Sheng and Ying
Zhang, accepted to International Journal on Intelligent Control
and Systems, 2006
Abstract
In this paper, we define a mobile self-localization (MSL) problem
for sparse and/or mobile robotic sensor networks, and propose an
algorithm, MA-MDS-MAP(P), based on Multi-Dimensional Scaling (MDS) for
solving the problem. For sparse robotic sensor networks, all the
existing localization algorithms fail to work properly due to the lack
of distance or connectivity data to uniquely calculate the
geo-locations. In MA-MDS-MAP(P), we use one or
more mobile sensors to add extra distance constraints to a sparse
network, by moving the mobile sensors in the area of deployment and
recording distances to neighbors at these intermediate locations.
MA-MDS-MAP(P) can also be used for localizing
and tracking mobile objects in a robotic or body sensor network.
Experiments and evaluations of the proposed algorithm are provided.
- "A
Robust and Efficient Flooding-based Routing for Wireless Sensor
Networks", Ying Zhang and Markus Fromherz, accepted to Journal of Interconnection Networks,
2006
Abstract
Flooding protocols for wireless networks in general have been shown
to be very inefficient and therefore are mainly used in network
initialization or route discovery and maintenance. In this paper, we
propose a framework of constrained flooding protocols. The framework
incorporates a reinforcement learning kernel, a differential delay
mechanism, and a constrained and probabilistic retransmission policy.
This type of protocol takes the advantages of robustness from flooding,
but maintains energy efficiency by constraining retransmissions. Without
the use of any control packets, such a protocol adapts to the specific
routing requirements of the task and the dynamic changes of the network.
We analyze this framework in simulation using some real-world
applications in sensor networks.
- "Balancing
Push and Pull for Efficient Information Discovery in Large-Scale Sensor
Networks", Xin Liu, Qingfeng Huang, Ying Zhang, accepted to IEEE
Transactions on Mobile Computing, 2006
Abstract
In this paper we investigate efficient strategies for supporting
on-demand information dissemination and gathering in large-scale
wireless sensor networks. In particular, we propose a
``comb-needle" discovery support model resembling an ancient
method: use a comb to help find a needle in sands or a haystack. The
model combines push and pull for information dissemination and
gathering. The push component features data duplication in a linear
neighborhood of each node. The pull component features a dynamic
formation of an on-demand routing structure resembling a comb. The
comb-needle model enables us
to investigate the cost of a spectrum of push and pull combinations for
supporting query and discovery in large scale sensor networks. Our
result shows that the optimal routing structure depends on the
frequency of query occurrence and the spatial-temporal frequency of
related events in the network. The benefit of balancing push and pull
for information discovery is demonstrated.
- "A
Learning-based Adaptive Routing Tree for Wireless Sensor Networks",
Ying Zhang and Qingfeng Huang, Journal of Communications, Academy
Publisher, 2006
Abstract
One of the most common communication patterns in sensor networks is
routing data to a base station, while the base station can be either
static or mobile. Even in static cases, a static spanning tree may not
survive for a long time due to failures of sensor nodes. In this paper, we
present an adaptive spanning tree routing mechanism, using real-time
reinforcement learning strategies. We demonstrate via simulation that
without additional control packets for tree maintenance, adaptive
spanning trees can maintain the ``best" connectivity to the base
station, in spite of node failures or mobility of the base station. And
by using a general constraint-based routing specification, one can apply
the same strategy to achieve load balancing and to control network
congestion effectively in real time.
- "Robust
Distributed Node Localization with Error Management", Juan Liu,
Ying Zhang, Feng Zhao, MobiHoc
2006
Abstract
Location knowledge of nodes in a network is essential for many tasks
such as routing, cooperative sensing, or service delivery in ad hoc,
mobile, or sensor networks. This paper introduces a novel iterative
method ILS for node localization starting with a relatively small number
of anchor nodes in a large network. At each iteration,
nodes are localized using a least-squares based algorithm. The
computation is lightweight, fast, and any-time. To prevent error from
propagating and accumulating during the iteration, the error control
mechanism of the algorithm uses an error registry to select nodes that
participate in the localization, based on their relative contribution to
the localization accuracy. Simulation results have shown that the active
selection strategy significantly mitigates the effect of error
propagation. The algorithm has been tested on a network of Berkeley
Mica2 motes with ultrasound TOA ranging devices. We have compared the
algorithm with more global methods such as MDS-MAP and SDP-based
algorithm both in simulation and on real hardware. The iterative
localization achieves comparable location accuracy in both cases,
compared to the more global methods, and has the advantage of being
fully decentralized.
- "Distributed
Minimal Time Convergecast Scheduling in Wireless Sensor
Networks", Shashidhar Gandham, Ying Zhang, Qingfeng
Huang, ICDCS 2006
Abstract
We consider applications of sensor networks wherein data packets
generated by every node have to reach the base station. This results in a many-to-one communication paradigm
referred to as convergecast. We are interested
in determining a TDMA schedule that minimizes the total time
required to complete the convergecast. We
consider a simple version of the problem wherein every node generates
exactly one packet. We propose a distributed convergecast
scheduling algorithm that requires at most $3N$ timeslots, where $N$
represents the number of nodes in the network. Through extensive
simulations, we demonstrate that actual number of timeslots needed is
around 1.5N. In addition to time efficiency, we prove that our convergecast scheduling algorithm requires the nodes
to buffer no more than two packets at any instance. We propose a sleep
schedule that conserves more than 50% of the energy. We present
simulation results for a real application scenario to show that our convergecast scheduling algorithm performs
significantly better than existing convergecast
algorithms.
- "High-Level
Sensor Network Simulations for Routing Performance Evaluations", Ying
Zhang, Gyula Simon, Gyorgy Balogh, INSS06, 2006
Abstract
For wireless sensor networks a wide variety of ad-hoc routing algorithms
are available in the literature. Typically, each algorithm comes with
its own platform and application scenario, which makes it hard to
compare different routing algorithms. In this paper we introduce a high
level simulation environment, which provides a fast and easy way for
routing performance evaluations. Prowler, a probabilistic network
simulator is developed with various radio models and a CSMA MAC layer. Rmase, an application built on the top of Prowler,
provides a layered routing architecture with routing scenario
specifications and performance metrics for algorithm evaluations. Both
Prowler and Rmase are easily extensible with
new models, metrics and components. A routing algorithm repository has
been developed with a set of commonly used routing components and
algorithms from various research groups. A real-world routing scenario
is used as an example to demonstrate the use of this high level
simulation environment for routing performance evaluations.
- "Sequential
Localization Algorithm for Active Sensor Network Deployment",
Ying Zhang, Qingfeng Huang and Juan Liu, PCAC06, 2006
Abstract
There has been a lot of work on localization for sensor networks. Most
localization schemes assume an already deployed network. Very little
research has been done for active sensor deployment with mobile robots.
In this paper, we present a distributed sequential localization process
which is tightly integrated with robotic sensor deployment. Being
location-aware, sensors can be placed in advantageous locations to avoid
big localization errors. In turn, the accurate localization result helps
further sensor deployment. We compare our distributed sequential
localization scheme with five existing localization algorithms, both
through simulations and through repeated runs on a mote testbed. Results show that the distributed
sequential localization algorithm produces comparable results to the
state-of-the-art centralized localization algorithms. Experiments also
show that pre-post processing plays important roles at getting good
localization results for all localization algorithms.
- "Constrained
Flooding: A Robust and Efficient Routing Framework for Wireless Sensor
Networks", Ying Zhang and Markus Fromherz, AINA06, 2006
Abstract
Flooding protocols for wireless networks in general have been shown to
be very inefficient and therefore are mainly used in network
initialization or route discovery and maintenance. In this paper, we
propose a framework of constrained flooding protocols. The framework
incorporates a reinforcement learning kernel, a differential delay
mechanism, and a constrained and probabilistic retransmission policy.
This type of protocol takes the advantages of robustness from flooding,
but maintains energy efficiency by constraining retransmissions. Without
the use of any control packets, such a protocol adapts to the specific
routing requirements of the task and the dynamic changes of the network.
We analyze this framework in simulation using a real-world application
in sensor networks.
- "Adaptive
Tree: A Learning-based Meta-Routing Strategy for Sensor Networks",
Ying Zhang and Qingfeng Huang, CCNC06, 2006
Abstract
One of the most common communication patterns in sensor networks is
routing data to a base station, while the base station can be either
static or mobile. Even in static cases, a static spanning tree may not
survive for a long time due to failures of sensor nodes. In this paper,
we present an adaptive spanning tree routing mechanism, using real-time
reinforcement learning strategies. We demonstrate via simulation that
without additional control packets for tree maintenance, adaptive
spanning trees can maintain the ``best" connectivity to the base
station, in spite of node failures or mobility of the base station.
- "Coordinated
Convergecast in Wireless Sensor Networks",
Ying Zhang and Qingfeng Huang, MilCom05,
2005
Abstract
Convergecast is a common communication pattern
across many sensor network applications featuring data-flows from many
different source nodes to a single sink node during a very short time
window. Convergecast in wireless ad hoc
network requires proper coordination among the nodes to avoid high
packet collision rates near the sink node. A coordinated convergecast framework for achieving high convergecast reliability has been developed. In this
paper, we extend this framework and study the effectiveness of packet
aggregation and duplication within this framework. We analyze the
performance of the coordination strategies via simulation and show the
tradeoffs among reliability, latency, and throughput. We also compare a
set of coordinated convergecast strategies
with the existing routing strategy designed and implemented for a
real-world application.
- "Minimum
Power Configuration in Wireless Sensor Networks", Guoliang Xing; Chenyang
Lu, Ying Zhang; Qingfeng Huang, Robert Pless, MobiHoc05, 2005
Abstract
This paper proposes the minimum power configuration (MPC) approach to
energy conservation in wireless sensor networks. In sharp contrast to
earlier research that treats topology control, power-aware routing, and
sleep management in isolation, MPC integrates them as a joint
optimization problem in which the power configuration of a network
consists of a set of active nodes and the transmission powers of the
nodes. We show through analysis that the minimum power configuration of
a network is inherently dependent on the data rates of sources. We
propose several approximation algorithms with provable performance
bounds compared to the optimal solution, and a practical Minimum Power
Configuration Protocol (MPCP) that can dynamically (re)configure a
network to minimize the energy consumption based on current data rates.
Simulations based on realistic radio models of the Mica2 motes show that
MPCP can conserve significantly more energy than existing minimum power
routing and topology control protocols.
- "Information-Directed
Routing in Sensor Networks Using Real-Time Reinforcement Learning",
Ying Zhang, Juan Liu, Feng Zhao, Combinatorial
Optimization in Communication Networks, Springer, 2006
Abstract
In this chapter, we apply real-time reinforcement learning to
Information Directed Routing (IDR) in sensor networks, where learning is
used to locate the target or the destination. Combining with information
utilities, this method effectively generates paths which co-optimize for
both communication metrics (e.g., small number of hops) and information
metrics (e.g., tracking errors), even in the existence of network holes
and unpredictable moving targets. Simulation results show that such a
strategy is effective for both common query routing scenarios: routing a
user query from an arbitrary node to the vicinity of signal sources and
back, or to a pre-specified destination, maximizing information
accumulated along the path.
- "STAM:
A System of Tracking and Mapping in Real Environments", Ying
Zhang, Mark Yim, Lee Ackerson, David Duff, and Craig Eldershaw, IEEE Wireless Communications Magazine,
2004
Abstract
We have implemented a system of tracking mobile robots and mapping an
unstructured environment, using up to twenty-five wireless sensor nodes
in an indoor setting. These sensor nodes form an ad hoc network of
beacons, self-localize with respect to three anchor nodes, and then
track the locations of mobile robots in the field. The system described
here was motivated by search and rescue applications and has been
demonstrated in real physical environments.
- "Radial
Coordination for Convergecast in Wireless Sensor Networks", Qingfeng
Huang and Ying Zhang, IEEE EmNeTS-I,
2004
Abstract
Convergecast is frequently used for supporting
various tasks in sensor network applications. In this paper, we
investigate the problem of packet loss in the convergecast
process in wireless sensor networks due to congestion and collisions
near the sink, and propose a simple yet powerful coordinated convergecast protocol for achieving high convergecast reliability. We study the performance
of the new protocol via simulation and show the tradeoffs among
reliability, latency, throughput and energy
consumption. To compare this protocol with other existing convergecast protocols, a real application scenario
is used. Simulation shows that this protocol can achieve dramatic
improvement in reliability comparing to existing convergecast
protocols.
- "Combs,
Needles, Haystacks: Balancing Push and Pull for Efficient Information
Discovery in Large-Scale Sensor Networks", Xin Liu, Qingfeng
Huang, and Ying Zhang, SenSys04, 2004
Abstract
In this paper we investigate efficient strategies for supporting
on-demand information dissemination and gathering in large-scale
wireless sensor networks. In particular, we propose a
"comb-needle" discovery support model resembling an ancient
method: use a comb to help find a needle in sands or a haystack. The
model combines push and pull for information dissemination gathering.
The push component features data duplication in a linear neighborhood of
each node. The pull component features a dynamic formation of an
on-demand routing structure resembling a comb. The comb-needle model
enables us to investigate the cost of a spectrum of push and pull
combinations for supporting discovery and query in large scale sensor
networks. Our result shows that the optimal routing structure depends on
the frequency of query occurrence and the spatial-temporal frequency of
related events in the network. The benefit of balancing push and pull
for discovery in large scale geometric networks is demonstrated.
- "Smart
Routing with Learning-based QoS-aware Routing Strategies",
Ying Zhang, Markus P.J. Fromherz, and Lukas D.
Kuhn, WQoSR04, Oct. 2004
Abstract
Conventional Quality of Service (QoS) routing
cannot be applied easily to wireless ad-hoc sensor networks due to the
unreliable and dynamic nature of such networks. For these networks, we
have proposed a framework of Message-initiated Constraint-Based Routing
(MCBR), which consists of a QoS specification
and a set of QoS-aware meta-strategies. In
contrast to most existing ad-hoc routing with no QoS
support, MCBR is able to take QoS
specifications into account. In this paper, we focus on learning-based
meta-strategies. In contrast to most existing QoS
routing approaches, learning-based meta-strategies do not create and
maintain explicit routes; instead, packets discover and improve the
routes during the search for the destination.
- " Improvements on Ant Routing for Sensor Networks",
Ying Zhang and Lukas D. Kuhn and Markus P.J. Fromherz,
Ant04, in LNCS 3172, Sep. 2004.
Abstract
Ad-hoc wireless sensor networks have been an active research topic for
the last several years. Sensor networks are distinguished from
traditional networks by characteristics such as deeply embedded routers,
highly dynamic networks, resource-constrained nodes, and unreliable and
asymmetric links. Ant routing has shown good performance for
communication networks; in this paper, we show why the existing ant
routing algorithms do not work well for sensor networks. Three new
ant-routing algorithms are proposed and performance evaluations for
these algorithms on a real application are conducted on a routing
simulator for sensor networks.
- "Search-based
Adaptive Routing Strategies for Sensor Networks", Ying Zhang
and Markus P.J. Fromherz, AAAI04 workshop on Sensor Networks,
July 2004
Abstract
Real-time or agent-centered search has been an active research area in
AI for the past decade. These techniques have been applied to many
applications including planning in robotic systems and routing in
communication networks. Sensor networks are distinguished from
traditional networks by characteristics such as deeply embedded routers,
highly dynamic networks, resource-constrained nodes, and unreliable and
asymmetric links. In this paper, we explore the space of search-based
techniques for sensor networks, including piggybacked heuristics,
heuristic estimation, promiscuous learning, indirect confirmation, and
forward propagation. Performance evaluations for these techniques on
real application scenarios are conducted on a routing simulator for
sensor networks.
- "Localization
from Connectivity in Sensor Networks", Yi Shang, Wheeler Ruml, Ying Zhang, and Markus P.J. Fromherz, IEEE Transactions on Parallel and
Distributed Systems, Nov. 2004, Vol. 15, No. 11
Abstract
We propose an approach that uses connectivity information---who is
within communications range of whom---to derive the locations of nodes
in a network. The approach can take advantage of additional information,
such as estimated distances between neighbors or known positions for
certain anchor nodes, if it is available. It is based on
multidimensional scaling (MDS), an efficient data analysis technique
that takes $O(n^3)$ time for a network of $n$
nodes. Unlike previous approaches, MDS takes full advantage of
connectivity or distance information between nodes that have yet to be
localized. Two methods are presented: a simple method that builds a
global map using MDS and a more complicated one that builds small local
maps and then patches them together to form a global map. Furthermore,
least-squares optimization can be incorporated into the methods to
further improve the solutions at the expense of additional computation.
Through simulation studies on uniform as well as irregular networks, we
show that the methods achieve more accurate solutions than previous
methods, especially when there are few anchor nodes. They can even yield
good relative maps when no anchor nodes are available.
- "Message-initiated
Constraint-based Routing for Wireless Ad-hoc Sensor Networks",
Ying Zhang and Markus P.J. Fromherz, CCNC04, 2004
Abstract
Most existing routing mechanisms today differ in routing objectives and
routing strategies, however all the existing routing protocols have in
common that the routing objective and destination specification are
fixed, and that the routing objective is incorporated only implicitly.
In this paper, we propose a general message specification mechanism to
explicitly encode the routing destinations, constraints and objectives
in messages, so that general-purpose instead of objective or destination
specific routing strategies can be applied. Using general-purpose
routing strategies while specifying quality-of-service (QoS) properties at the application layer explicitly
in messages, QoS-aware strategies for
individual messages are obtained. We also propose two frameworks of
general-purpose routing strategies for this type of message
specification.
- "Localization
from Mere Connectivity", Yi Shang, Wheeler Ruml, Ying Zhang, and Markus P.J. Fromherz, MobiHoc03, 2003
Abstract
It is often useful to know the geographic positions of nodes in a
communications network, but adding GPS receivers or other sophisticated
sensors to every node can be expensive. We present an algorithm that
uses connectivity information - who is within
communications range of whom - to derive the locations of the nodes in
the network. The method can take advantage of additional information,
such as estimated distances between neighbors or known positions for
certain anchor nodes, if it is available. The algorithm is based on
multidimensional scaling, a data analysis technique that takes O(n3) time for a network of n
nodes. Through simulation studies, we demonstrate that the algorithm is
more robust to measurement error than previous proposals, especially
when nodes are positioned relatively uniformly throughout the plane.
Furthermore, it can achieve comparable results using many fewer anchor
nodes than previous methods, and even yields relative coordinates when
no anchor nodes are available.
- "Limbless
Conforming Gaits with Modular Robots", Mark Yim, Craig Eldershaw
, Ying Zhang and David Duff, Experimental Robotics IX: The 9th
International Symposium on Experimental Robotics, Springer Tracts in
Advanced Robotics, 2006
Abstract
This paper presents experimentation using the PolyBot
modular robot of two limbless gaits which conform to environment. A
conforming loop gait is low profile and traverses over a variety of
obstacles where the ratio of the height of the obstacle to robot is up
to 1.3. A concertina snake gait is capable of negotiating narrow
passages (for example a width of double the width of the robot itself),
including those with bends as sharp as 110°. It is well suited to
locomotion in unstructured tunnels. One little appreciated point that is
emphasized in this paper is that the difficulty of an environment is
always relative to size of the robot itself.
- "PolyBot and PolyKinetic
System: A Modular Robotic Platform for Education", Alex Golovinsky, Mark Yim, Ying
Zhang, Craig Eldershaw, Dave Duff, IEEE
ICRA04
Abstract
Modular robotics has been an active area of research for the last
decade. In this paper, we argue that it also provides an excellent
platform for education. PolyBot is a type of
modular reconfigurable robot developed at PARC. The PolyKinetic
System provides a robotic scripting language and programming environment
for controlling this type of robot. Based on experience with mentoring
high school students, and running a tutorial for robotic researchers at
IROS'03, we show that, PolyBot and the PolyKinetic System is effective for educational
activities at multiple levels. These include playing, exploring,
building, programming, competing, and most of all, learning while having
fun.
- "An
XML-based Scripting Language for Chain-type Modular Robotic
Systems", Ying Zhang, Alex Golovinsky, Mark Yim, Craig Eldershaw, 8th Conference on Intelligent
Autonomous Systems, 2004
Abstract
A number of modular robotic systems have been developed over the last
decade. Such systems promise increased flexibility and robustness and
lower cost over conventional robots; however programming systems with
many degrees of freedom is still more an art than engineering. The complexity of programming limits the usage of
such systems and the sharing of knowledge within the modular robotics
community. We have previously published work on using ``Phase
Automata" as a programming model for chain-type modular robotic
systems. In this paper, we present an XML-based scripting language for
describing phase automata and complex behavior compositions.
- "Scalable
and reconfigurable configurations and locomotion gaits for chain-type
modular reconfigurable robots", Y. Zhang, M. Yim, C. Eldershaw, D.
Duff and K. Roufas, IEEE Symposium on
computational intelligence in robotics and automation (CIRA), Japan,
2003
Abstract
Modular reconfigurable robots have shown the promises of great
versatility and robustness; however, they also impose design challenges
on mechanical, electronic and software scalability. In this paper, we
present a class of configura- tions that are scalable mechanically and
electronically. Moreover, there exists a predefined reconfiguration
sequences between any of the three types of configuration, namely,
snakes, centipedes, and multi-loops. Locomotion gaits for the three
types of configurations are defined and created using Phase Automata, a
generalization of gait tables. The system has been tested both in
simulation of 100+ modules and in hardware of 50+ modules.
- "Phase
Automata: a programming model of locomotion gaits for scalable chain-type
modular robots", .
Zhang, M. Yim, C. Eldershaw,
D. Duff and K. Roufas, IEEE/RSJ conference
on intelligent robots and systems (IROS), Los Vegas, 2003
Abstract
Modular reconfigurable robots have shown the promises of great
versatility and robustness; however programming locomotion gaits for
hundreds of modules remains a challenge. In this paper we present a
formal model for programming locomotion gaits in chain-type modular
robots: Phase Automata. A phase automaton is an event-driven
input/output state automaton with an initial phase delay. The phase
delay is normally a real value between 0 and 1. Phase automata are
capable of being embedded and distributed across modules. They have been
implemented on both PCs and embedded micro-processors. Locomotion gaits
programmed using phase automata have been tested both in simulation with
100+ modules and in hardware with 50+ modules.
- "Connecting
and disconnecting for chain self-reconfiguration with PolyBot", M. Yim,
Y. Zhang, K. Roufas, D. Duff and C. Eldershaw, IEEE/ASME Transactions on mechatronics, special issue on Information
Technology in Mechatronics, 2003
Abstract
Chain modular robots form systems with many degrees of freedom which are
capable of being reconfigured to form arbitrary chain-based topologies.
This reconfiguration requires the detaching of modules from one point in
the system and re-attaching at another. The internal errors in the
system (especially with large numbers of modules) are such that accurate
movement of chain ends, required for the attaching of modules, can be
extremely difficult. A three phase docking process is described that
utilizes both open- and closed-loop techniques. This process has been
shown to work with an early version. Issues raised during this testing
have been addressed in a later version. Discussion of these issues,
their solutions and preliminary results of the testing the latest
version are given.
- "Modular
Reconfigurable Robots in Space Applications", M. Yim, K. Roufas, D.
Duff, Y. Zhang, C. Eldershaw and S. Homans, Autonomous Robot Journal, special
issue for Robots in Space, Springer Verlag,
2003
Abstract
Robots used for tasks in space have strict requirements. Modular
reconfigurable robots have a variety of attributes that are well suited
to for these conditions, including: the ability to serve as many
different tools at once (saving weight), packing into compressed forms
(saving space) and having high levels of redundancy (increasing
robustness). In addition, self-reconfigurable systems can self-repair
and adapt to changing or unanticipated conditions. This paper will
introduce such a self-reconfigurable modular robot: PolyBot.
PolyBot has significant potential in the space
manipulation and surface mobility class of applications for space.
- "A
General Constraint-Based Control Framework with Examples in Modular
Self-Reconfigurable Robots", Y. Zhang, M. Fromherz, L. Crawford, Y. Shang, IEEE/RSJ
Intl. Conf. on Intelligent Robots and Systems, Lausanne,
Switzerland, Oct. 2002
Abstract
In this paper, we advocate a general constraint-based control framework
that is highly promising for building control systems with complex
dynamic structures, such as modular self-reconfigurable robots. In this
framework, a controller consists of constraint solving components
distributed in a network of embedded processors. Constraint solvers are
goal oriented deliberative agents that can be used as control regulators
or as information retrievers. The framework is built on the
Attribute/Service Model (ASM), a middleware for coordinating actuators,
sensors and tasks in distributed real-time embedded systems. The
communications and coordination among the services are realized via
shared attributes. Examples of controlling a modular self-reconfigurable
robot are illustrated in the paper.
- "Sensor
Computation in Modular Self-Reconfigurable Robots", Y. Zhang,
K. Roufas, C. Eldershaw,
M. Yim, D. Duff, Experimental Robotics VIII,
Advanced Robotics Series, Ed. Springer, 2003
Abstract
Sensors play important roles in automatic systems; smart systems have to
be equipped with smart sensors. PolyBot, a
modular self-reconfigurable robot developed at the Palo Alto Research
Center, is
designed with a rich set of sensors in each of its 5cm-cubed modules.
These include infrared (IR), accelerometers, potentiometers, force, and
touch sensors. These sensors are used: to determine the current state of
the system and its environment; to obtain the six degree-of-freedom
offset between two docking plates for automatic reconfiguration; to
select the right gait for locomotion; and to trigger different behavior
modes in response to different terrain conditions. Sensor computations
are computational methods that, given raw sensor data, extract or deduce
the state information about the system. In general, there are two types
of sensor computation, forward computation and inverse computation.
Analogous to forward and inverse kinematics, forward sensor computation
obtains state information directly from sensor data; inverse sensor
computation obtains state information by solving a constraint or
optimization problem using either closed-form or numerical methods. This
paper focuses on two interesting sensor computations in PolyBot: IR 6 DOF ranging and accelerometer 2 DOF
orientation.
- "A
Platform for Studying Locomotion Systems: Modular Reconfigurable
Robots", Ying Zhang, Craig Eldershaw, Mark Yim, Kimon Roufas, Dave Duff, NIST
workshop on Performance Metrics for Intelligent systems, August 2002
Abstract
There are many fundamentally different mechanical motions that a system
can use to achieve locomotion. Two standard examples are the wheels on a
car or the legs of an artificial ant, but many others exist as well. As
with all systems, there is an obvious desire to quantify how
"well" each locomotion method performs. Unfortunately, as with
many metrics, this is far from being a well-defined problem. Apart from
the usual difficulty of deciding exactly what is the most important
measure (peak speed, efficiency, etc), there is the question of
divorcing the underlying locomotive concept from the particular
implementation (just like a universal machine such as Turing Machine
divorces hardware implementations from algorithms)
This paper proposes a particular platform which the authors believe can
be used as part of a standard system for evaluating many different means
of locomotion. Since one of the fundamentally different aspects of each
of these locomotive methods is the underlying mechanism, then any
standard platform must be capable of changing its shape and fashion of moving
so as to be able to faithfully perform the locomotion to be tested. The PolyBot system, developed at PARC, is capable of
just this.
- "Massively
Distributed Control Nets for Modular Self-Reconfigurable Robots",
Y. Zhang, M. Yim, K. Roufas, C. Eldershaw, AAAI 2002 Spring Symposium on
Intelligent Distributed and Embedded Systems
Abstract
Massively Distributed Control Nets (MDCN) is a CAN based high-level
protocol that has the following features: (1) Three types of
communication: individual, group and broadcast, with eight priority
levels. (2) Addressing of up to 254 nodes and groups in standard CAN
format, and up to 100,000’s in extended CAN format. (3) I/O
(node-to-node) and port (point/process-to-point/process) communications,
where I/O is mostly reserved for system processes with high priorities
and short message sizes, and port is for user applications, with lower
priorities and possibly large message sizes. Compared to the existing
widely used high-level CAN protocols, MDCN can address more communication
nodes, has simpler APIs, is easier and more efficient to implement. Also
the protocol is transparent to either a single CAN bus or a networked
CAN buses. MDCN is currently implemented in C for MPC555 TouCAN controller on the Real-Time Operating Systems
vxWorks, and in Java on host PC. The API is
designed and implemented for multi-threaded environments. MDCN is a
general protocol that not only can be applied to modular robots, but
also can be applied to any industry control or automation using CAN bus
network with hundreds of communication nodes.
- "Attribute/Service
Model: Design Patterns for Efficient Coordination of Distributed
Sensors, Actuators and Tasks in Embedded Systems", Y. Zhang, M.
Yim, K. Roufas, C.
Eldershaw, D. Duff, Workshop on Embedded
System Codesigns 2002
Abstract
This paper proposes the Attribute/Service Model (ASM) and associated
design patterns as a general and simple framework for applications that
require programming with multiple tasks on multiple processors. This
model enables the programming of complex tasks with multiple sensors and
actuators on highly distributed yet tightly coupled systems by: making
transparent the location of where services run, simplifying the
synchronization of multiple processes concurrently changing the shared
data, protecting that shared data and using a simple unified protocol
for communication. Associated design patterns such as the event/trigger
mechanism for general event-driven control and phase automata for
modular robots’ gait control are developed on ASM. ASM is designed for
distributed coordination of sensors, actuators and tasks for modular
self-reconfigurable robots; however it can be used for any
multi-threaded distributed embedded control network. ASM has been
implemented both in C on top of VxWorks on the
MPC555 embedded microprocessors, and in Java on a host PC, using
Controller Area Network (CAN) as the communication medium. It could be
equally implemented on any real-time operating system using any
communication media.
- "Closed
Chain Motion with Large Mechanical Advantage", M. Yim, D. Duff, Y. Zhang, IEEE/RSJ Intl.
Conf. on Intelligent Robots and Systems, Hawaii, USA, Oct. 2001
Abstract
One of the constraints that severely limit the capability of highly
redundant manipulator arms is the actuator torque limits. This paper
presents a way to achieve large effective forces from weak actuators by
exploiting large mechanical advantage that results from systems near
singularities. While large mechanical advantages have been applied near
singularities in many instances, this method allows the application of
this large force over a large distance. It is applied specifically to
closed chain mechanisms and demonstrated on the PolyBot
modular self-reconfigurable robot.
- "Software
Architecture for Modular Self-Reconfiguable Robots", Y. Zhang, K. Roufas, M. Yim, IEEE/RSJ
Intl. Conf. on Intelligent Robots and Systems, Hawaii, USA, Oct.
2001
Abstract
Modular, self-reconfigurable robots show the promise of great
versatility, robustness and low cost. However, programming such robots
for specific tasks, with hundreds of modules and each of which with
multiple actuators and sensors, can be tedious and error-prone. The
extreme versatility of the modular systems requires a new paradigm in
programming. In this paper, we present new software architecture for
this type of robot, in particular PolyBot,
which has been developed through its third generation. The architecture,
based on the properties of the PolyBot
electro-mechanical design, features a multi-master/multi-slave structure
in a multi-threaded environment, with three layers of communication
protocols. The architecture is currently being implemented for Motorola
PowerPC using vxWorks.
- "Modular
Reconfigurable Robots in Space Applications", M. Yim, K. Roufas, D.
Duff, Y. Zhang, S. Homans, 10th Intl. Conf.
on Advanced Robotics Budapest, Hungry, Aug. 2001
Abstract
Robots used for tasks in space have strict requirements. Modular
reconfigurable robots have a variety of attributes that are advantageous
for these conditions including the ability to serve as many tools at
once saving weight, packing into compressed forms saving space and
having large redundancy to increase robustness. Self-reconfigurable
systems can also self-repair as well as automatically adapt to changing
conditions or ones that were not anticipated. PolyBot
may serve well in the space manipulation and surface mobility class of
space applications.
- "Six
Degree of Freedom Sensing for Docking Using IR RED Emitters and
Receivers", K. Roufas, Y.
Zhang, D. Duff, M. Yim, Experimental
Robotics VII, Lecture Notes in Control and Information Sciences 271,
Daniela Rus and Sanjiv
Singh Eds. Springer, 2001
Abstract
Six DOF offset sensing between two plates is important for automatic
docking mechanisms. This paper presents an easy and inexpensive
implementation of such a system using four commercial-off-the-shelf
(COTS) infrared (IR) light emitting diode (LED) emitters and two COTS IR
receivers on each of two docking plates. The angular intensity distribution
of an emitter and the sensitivity distribution of a receiver allow for
estimation of the angle and distance between them. Simple experiments
have been conducted indicating that such a setup is able to give
positional offset in any of 6 degrees of error (x, y, z, pitch, roll,
and yaw) within a range. A theoretical framework is also established
using least squares minimization. The theoretical framework is general
and applies to other configurations of emitter and receiver parts and
positioning.
- "Distributed
Control for 3D Metamorphosis", M. Yim, Y. Zhang, J. Lamping, E. Mao, Autonomous Robots 10, 2001
Abstract
In this paper, we define Proteo as a
class of three-dimensional (3D) metamorphic robotic system capable of
approximating arbitrary 3D shapes by utilizing repeated modules. Each Proteo module contains embedded sensors,
actuators and a controller, and each resides in a 3D grid space. A
module can move itself to one of its open neighbor sites under certain
motion constraints. Distributed control for the self-reconfiguration of
such robots is an interesting and challenging problem. We present a
class of distributed control algorithms for the reconfiguration of Proteo robots based on the “goal-ordering”
mechanism. Performance results are shown for experiments of these
algorithms in a simulation environment, and the properties of these
algorithms are analyzed.
Hybrid Systems
- "A
Formal Approach to Agent Design: An Overview of Constraint-Based
Agents", Alan K. Mackworth and Ying
Zhang, Constraint Journal, Vol. 8, issue 3, 2003
Abstract
Formal models for agent design are important for both practical
and theoretical reasons. The Constraint-Based Agent (CBA) design
approach includes two formal models: Constraint Nets and Timed $\forall$-automata. A constraint net models the agents and the environment symmetrically as, possibly
hybrid, dynamical systems; a timed $\forall$-automaton
specifies
the desired real-time dynamic behaviors of the situated agents. Given a
constraint-based specification of the desired behavior, a
constraint-based agent can be synthesized as a constraint solver. Using
formal modeling and specification, it is also possible to verify complex
agents as obeying real-time temporal constraint specifications. This
overview paper presents a summary of the development and application of
the CBA framework.
- "Formal
Specification of Performance Metrics for Intelligent Systems",
Ying Zhang and Alan K. Mackworth, NIST
Workshop on Performance Metrics for Intelligent Systems,
Gaithersburg, MD, August 2000
Abstract
There are now so many architectures for intelligent systems:
deliberative planning vs. reactive acting, behavioral subsuming vs.
hierarchical structuring, machine learning vs. logic reasoning, and
symbolic representation vs. procedural knowledge. The arguments from all
schools are all based on how natural systems (i.e., biologically
inspired, from basic forms of life to high level intelligence) work by
taking the parts that support their architectures. In this paper, we
take an engineering point of view, i.e., by using requirements
specification and system verification as the measurement tool. Since
most intelligent systems are real-time dynamic systems (all lives are),
requirements specification should be able to represent timed properties.
We have developed timed "-automata
that fit to this purpose. We will present this formal specification,
examples for specifying requirements and a general procedure for
verification.
- "Design
and Analysis of Hybrid Control Systems: An Elevator Case Study",
Ying Zhang and Alan K. Mackworth, Ray
Reiter's 60th Birthday Collection, Logical Foundations for Cognitive
Agents, Springer, 1999
Abstract
We propose a formal approach to the modeling and analysis of hybrid
control systems. The approach consists of the interleaved phases of
hybrid dynamic system modeling, requirements specification, hybrid
control design and overall behavior verification. We have developed
Constraint Nets as a semantic model for hybrid dynamic systems. Using
this model, continuous, discrete and event-driven components of a
dynamic system can be represented uniformly. We have developed timed forall-automata as a
requirements specification language for dynamic behaviors. Using
this language, many important properties of a dynamic system, such as
safety, stability, reachability and real-time
response can be formally stated. We have also proposed a verification
method for checking whether a constraint net model satisfies a timed forall-automaton specification. The method
uses the induction principle and generalizes both Liapunov
stability analysis for dynamic systems and monotonicity
of well-foundedness in discrete-event systems.
The power of these techniques is demonstrated with a simple elevator
system. An elevator system is a typical hybrid system with continuous
motion following Newtonian dynamics and discrete event control
responding to users' request. We model the complete elevator system
using Constraint Nets and verify the overall behavior of the system
against the requirements specification in timed forall-automata.
- "Constraint
Nets: A Semantic Model for Hybrid Dynamic Systems", Ying Zhang
and Alan K. Mackworth, Journal of Theoretical Computer Science,
Vol. 138, No. 1, 1995, p.211--239, Special Issue on Hybrid Systems.
Abstract
Hybrid dynamic systems are systems consisting of
a non-trivial mixture of discrete and continuous components, such as a
controller realized by a combination of digital and analog circuits, a robot
composed of a digital controller and a physical plant, or a robotic system
consisting of a computer-controlled robot coupled to a continuous
environment. Hybrid dynamic systems are more general than traditional
real-time systems. The former can be composed of continuous subsystems in
addition to discrete and event-controlled components.
In this paper, we develop a semantic model,
constraint nets (CN), for hybrid systems. CN captures the most general
structure of dynamic systems so that systems with discrete and continuous
time, discrete and continuous variables, and asynchronous as well as
synchronous event structures, can be modeled in a unitary framework. Using
aggregation operators, a system can be modeled hierarchically in CN;
therefore, the dynamics of the environment as well as the dynamics of the
plant and the dynamics of the controller can be modeled individually and then
integrated. Based on abstract algebra and topology, CN supports multiple
levels of abstraction, so that a system can be analyzed at different levels
of detail. CN also provides a rigorous formal programming semantics for the
design of hybrid real-time embedded systems.
- "Specification
and Verification of Hybrid Dynamic Systems with Timed Forall-automata", Ying Zhang and Alan K.
Mackworth, Verification and Control of
Hybrid Systems, LNCS 1066, 1995.
Abstract
The advent of computer-controlled embedded
systems coupled to physical environments requires the development of new
theories of dynamic system modeling, specification and verification. We
present Timed Forall-automata, a
generalization of Forall-automata, for the
specification and verification of dynamic systems that can be discrete,
continuous or hybrid. Timed Forall-automata
are finite state and serve as a formal requirements specification
language for dynamic systems so that (1) timed as well as temporal
properties can be specified or recognized, and (2) global properties of
either discrete or continuous behaviors can be characterized. In
addition, we propose a formal model-checking method for behavior
verification of dynamic systems. This method generalizes stability
analysis of dynamic systems and can be completely automated for
discrete-time finite-domain systems.
- "Synthesis
of Hybrid Constraint-Based Controllers", Ying Zhang and Alan K.
Mackworth, Hybrid Systems II, LNCS 999, 1995,
p. 552--567.
Abstract
A robot is an integrated system, with a
controller embedded in its plant. We take a robotic system to be the
coupling of a robot to its environment. Robotic systems are, in general,
hybrid dynamic systems, consisting of continuous, discrete and
event-driven components. We call the dynamic relationship of a robot and
its environment the behavior of the robotic system. The problem of
control synthesis is: given a requirements specification for the
behavior, and given dynamic models of the plant and the environment,
generate a controller so that the behavior of the robotic system
satisfies the specification. We have developed a formal language, Timed
Linear Temporal Logic (TLTL), for requirements specification. We have
also developed a semantic model, Constraint Nets, for modeling hybrid
dynamic systems. In this paper, we study the problem of control
synthesis using these representations. Control synthesis in general is
difficult. We first focus on a special class of requirements specification,
called constraint-based specification, in which constraints are
associated with properties such as safety, reachability
and persistence. Then we develop a systematic approach to synthesizing
controllers using constraint methods, in which controllers are embedded
constraint solvers that solve constraints in real-time. Finally, we
consider hierarchical control structures, in which the higher levels
embody digital/symbolic event-driven control derived from discrete
constraint methods and the lower levels incorporate analog control based
on continuous constraint methods. We illustrate these techniques using a
robot soccer player as a running example.
- "Constraint
Programming in Constraint Nets", Ying Zhang and Alan K. Mackworth, Principles and Practice of Constraint
Programming, MIT Press, 1995, p.49--68.
Abstract
We view constraints as relations and constraint
satisfaction as a dynamic process of approaching the solution set of the
constraints. We have developed a semantic model for dynamic systems,
called Constraint Nets, to provide a real-time programming semantics and
to model and analyze dynamic systems. In this paper, we explore the
relationship between constraint satisfaction and constraint nets by
showing how to implement various constraint methods on constraint nets.
In particular, we examine discrete and continuous methods for discrete
and continuous domain constraint satisfaction problems. Hard and soft
constraints within the framework of unconstrained and constrained
optimization are considered. Finally, we present an application of this
on-line constraint satisfaction framework to the design of robot control
systems.
- "Specification
and Verification of Constraint-Based Dynamic Systems", Ying Zhang and Alan K. Mackworth,
Principles and Practice of Constraint Programming, LNCS 874,
1994, p. 229--242.
Abstract
Constraint satisfaction can be seen as a dynamic process that approaches
the solution set of the given constraints asymptotically. Constraint
programming is seen as creating a dynamic system with the required
property. We have developed a semantic model for dynamic systems,
Constraint Nets, which serves as a useful abstract target machine for
constraint programming languages, providing both semantics and
pragmatics. Generalizing, here we view a constraint-based dynamic system
as a dynamic system which approaches the solution set of the given
constraints persistently. Most robotic systems are constraint-based
dynamic systems with tasks specified as constraints. In this paper, we
further explore the specification and verification of constraint-based
dynamic systems. We first develop generalized forall-automata
for the specification and verification of general (hybrid) dynamic
systems, then explicate the relationship between constraint-based
dynamic systems and their requirements specification.
- "Will
The Robot Do The Right Thing?", Ying Zhang and Alan K. Mackworth,
Canadian Artificial Intelligence, 1994, p.255--262.
Abstract
Robots are generally composed of multiple sensors, actuators and
electromechanical parts. The overall behavior of a robot is emergent
from coordination among its various parts and its interaction with its
environment. Designing a `correct' robot which does `the right thing' in
a given environment is an important and challenging problem. The
question posed in the title is decomposed into two questions. First,
what is the right thing? Second, how does one guarantee the robot will
do it? We answer these questions in this paper by establishing a formal
approach to the design and analysis of robotic systems and behaviors.
- "Parallel
and Distributed Finite Constraint Satisfaction: Complexity, Algorithms
and Experiments", Ying Zhang and Alan K. Mackworth, Parallel Processing for Artificial
Intelligence, Elsevier/North Holland, 1993.
Abstract
This paper explores the parallel complexity of
finite constraint satisfaction problems (FCSPs)
by developing three algorithms for deriving minimal constraint networks
in parallel. The first is a parallel algorithm for the EREW PRAM model,
the second is a distributed algorithm for fine-grain interconnected
networks, and the third is a distributed algorithm for coarse-grain
interconnected networks. Our major results are: given an FCSP
represented by an acyclic constraint network (or a join tree) of size n with
treewidth bounded by a constant, then (1) the
parallel algorithm takes O(log n) time using O(n) processors, (2) there
is an equivalent network, of size poly(n) with treewidth
also bounded by a constant, which can be solved by the fine-grain
distributed algorithm in O(log n) time using poly(n) processors and (3)
the distributed algorithm for coarse-grain interconnected networks has
linear speedup and linear scaleup. In
addition, we have simulated the fine-grain distributed algorithm based
on the logical time assumption, experimented with the coarse-grain
distributed algorithm on a network of transputers,
and evaluated the results against the theory.
|
