Arrow Research search

Author name cluster

Cheng Fang

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

29 papers
2 author rows

Possible papers

29

EAAI Journal 2026 Journal Article

Global relationship awareness 3-dimensional object detection using 4-dimensional radar

  • Pianzhang Duan
  • Li Wang
  • Cheng Fang
  • Ziying Song
  • Ming Gao
  • Mo Zhou
  • Ying Li
  • Yibo Zhang

4D (4-dimensional) radar sensing technology is essential for high-precision autonomous driving perception systems, as its superior detection capabilities at increased distances, compared to traditional LiDAR (Light Detection and Ranging). However, due to the sparsity of point clouds and the low resolution of millimeter-wave radar, voxel-based methods may fail to detect distant or closely adjacent objects, leading to inadequate detection accuracy. To mitigate the accuracy issues arising from the sparse nature of point clouds in such scenarios, we propose a novel object detection network: GRA-Net (Global Relation-Aware object detection Network). By leveraging a self-attention mechanism, GRA-Net effectively learns critical features from each radar pillar, enhancing the network’s capacity to capture relevant information about nearby objects. Furthermore, we introduce a global perception module that integrates key features within the pillars and global features, mitigating the impact of point cloud sparsity, particularly in distant regions. We conducted a series of experiments to evaluate the performance of GRA-Net. On the Astyx HiRes 2019 dataset, our method achieved 33. 63 mAP (mean Average Precision) and 43. 93 mAP at the moderate level; On the View-of-Delft dataset, our method achieved 47. 74 mAP in the entire annotated area and 69. 25 mAP in the driving corridor area.

ICRA Conference 2025 Conference Paper

A Full-Optical Pretouch Dual-Modal and Dual-Mechanism (PDM 2 ) Sensor for Robotic Grasping

  • Cheng Fang
  • Zhiyu Yan
  • Fengzhi Guo
  • Shuangliang Li
  • Dezhen Song
  • Jun Zou

We report a new full-optical pretouch dual-modal and dual-mechanism (PDM2) sensor based on an air-coupled fiber-tip surface micromachined optical ultrasound transducer (SMOUT). Compared to ring-shaped piezoelectric acoustic receivers in previous PDM 2 sensors, the acoustic signal received by the new fiber-tip SMOUT is readout optically, which is naturally resistant to surrounding electromagnetic interference (EMI) and makes the complex grounding and shielding unnecessary. In addition, the new fiber-tip SMOUT receiver has a much smaller size, which makes it possible to further miniaturize the sensor package into a more compact structure. For verification, a prototype of the full-optical PDM 2 sensor has been designed, fabricated, and characterized. The experimental results show that even with the much smaller acoustic receiver, the new sensor can still achieve ranging and material/structure sensing performances comparable with the previous ones. Therefore, the new full optical PDM 2 sensor design is promising in providing a practical and miniaturized solution for ranging and material/structure sensing to assist robotic grasping of unknown objects.

IROS Conference 2025 Conference Paper

Diff-MSM: Differentiable MusculoSkeletal Model for Simultaneous Identification of Human Muscle and Bone Parameters

  • Yingfan Zhou
  • Philip Sanderink
  • Sigurd Jager Lemming
  • Cheng Fang

High-fidelity personalized human musculoskeletal models are crucial for simulating realistic behavior of physically coupled human-robot interactive systems and verifying their safety-critical applications in simulations before actual deployment, such as human-robot co-transportation and rehabilitation through robotic exoskeletons. Identifying subject-specific Hill-type muscle model parameters and bone dynamic parameters is essential for a personalized musculoskeletal model, but very challenging due to the difficulty of measuring the internal bio-mechanical variables in vivo directly, especially the joint torques. In this paper, we propose using Differentiable MusculoSkeletal Model (Diff-MSM) to simultaneously identify its muscle and bone parameters with an end-to-end automatic differentiation technique differentiating from the measurable muscle activation, through the joint torque, to the resulting observable motion without the need to measure the internal joint torques. Through extensive comparative simulations, the results manifested that our proposed method significantly outperformed the state-of-the-art baseline methods, especially in terms of accurate estimation of the muscle parameters (i. e. , initial guess sampled from a normal distribution with the mean being the ground truth and the standard deviation being 10% of the ground truth could end up with an average of the percentage errors of the estimated values as low as 0. 05%). In addition to human musculoskeletal modeling and simulation, the new parameter identification technique with the Diff-MSM has great potential to enable new applications in muscle health monitoring, rehabilitation, and sports science.

ICRA Conference 2025 Conference Paper

Heterogeneous Sensor Fusion and Active Perception for Transparent Object Reconstruction with a PDM 2 Sensor and a Camera

  • Fengzhi Guo
  • Shuangyu Xie
  • Di Wang 0020
  • Cheng Fang
  • Jun Zou
  • Dezhen Song

Transparent household objects present a challenge for domestic service robots, since neither regular cameras nor RGB-D cameras can provide accurate points for shape reconstruction. The new type of pretouch dual-modality distance and material sensor (PDM 2 ) can provide reliable and accurate depth readings, but it is a point sensor and scanning the object exclusively with the sensor is too inefficient. Hence, we present a sensor fusion approach by combining a regular camera with the PDM 2 sensor. The approach is based on a data fusion algorithm for shape reconstruction and an active perception algorithm for scan planning for the PDM 2 sensor. The data fusion algorithm is a distributed Gaussian process (GP)-based shape reconstruction method that allows for incremental local update to reduce computational time. The active perception algorithm is an optimization-based approach by increasing the information gain (IG) and prioritizing the boundary points under a preset travel distance constraint. We have implemented and tested the algorithms with six different transparent household items. The results show satisfactory shape reconstruction results in all test cases with an average increase in intersection over union (IoU) from 0. 73 to 0. 96.

ICRA Conference 2025 Conference Paper

Stiffness Regulation Co-Pilot in Bilateral Teleimpedance Control: A Preliminary User Study

  • Pedro Gomez Hernandez
  • Jonas Mariager Jakobsen
  • Claudio Pacchierotti
  • Francesco Chinello
  • Cheng Fang

Variable stiffness of a remote robot is crucial for a teleoperation system to deal with challenging tasks. External stiffness command interfaces have emerged as a promising solution to regulating the remote robot stiffness because of the benefits of their accuracy, ergonomics, and avoidance of the “coupling effect” that usually exists in muscle activity-based stiffness interfaces. However, the use of an external stiffness command interface requires good coordination between two limbs of an operator, which take care of the teleoperation task and the stiffness regulation task, respectively, at the same time, which is demanding for novice operators in dynamic situations necessitating agile and timely stiffness adjustments. In this paper, a new concept of Stiffness Regulation Co-pilot was proposed to facilitate the use of these interfaces. A co-pilot is a virtual agent that consists of a Stiffness Regulation Policy, which infers a reasonable stiffness regulation action from the task performance, and a feedback modality, which conveys the suggested stiffness regulation action to the operator. A preliminary user study was conducted to evaluate the efficacy of the co-pilot and the effect of different modalities of the co-pilot. The results showed that the cutaneous feedback or combined with another modality can potentially improve the task performance of the system and reduce the cognitive load of the operator compared to a teleoperation system without using the co-pilot.

NeurIPS Conference 2024 Conference Paper

HAWK: Learning to Understand Open-World Video Anomalies

  • Jiaqi Tang
  • Hao Lu
  • Ruizheng Wu
  • Xiaogang Xu
  • Ke Ma
  • Cheng Fang
  • Bin Guo
  • Jiangbo Lu

Video Anomaly Detection (VAD) systems can autonomously monitor and identify disturbances, reducing the need for manual labor and associated costs. However, current VAD systems are often limited by their superficial semantic understanding of scenes and minimal user interaction. Additionally, the prevalent data scarcity in existing datasets restricts their applicability in open-world scenarios. In this paper, we introduce HAWK, a novel framework that leverages interactive large Visual Language Models (VLM) to interpret video anomalies precisely. Recognizing the difference in motion information between abnormal and normal videos, HAWK explicitly integrates motion modality to enhance anomaly identification. To reinforce motion attention, we construct an auxiliary consistency loss within the motion and video space, guiding the video branch to focus on the motion modality. Moreover, to improve the interpretation of motion-to-language, we establish a clear supervisory relationship between motion and its linguistic representation. Furthermore, we have annotated over 8, 000 anomaly videos with language descriptions, enabling effective training across diverse open-world scenarios, and also created 8, 000 question-answering pairs for users' open-world questions. The final results demonstrate that HAWK achieves SOTA performance, surpassing existing baselines in both video description generation and question-answering. Our codes/dataset/demo will be released at https: //github. com/jqtangust/hawk.

AIJ Journal 2023 Journal Article

A conflict-directed approach to chance-constrained mixed logical linear programming

  • Cheng Fang
  • Brian C. Williams

Resistance to the adoption of autonomous systems comes in part from the perceived unreliability of the systems. The concerns can be addressed by deploying decision making algorithms that defines what it means to fail, and look for plans with the highest reward while limiting the probability of failure. This chance-constrained approach thus explicitly imposes a set of constraints that must be satisfied for success, and provides upper-bounds on the probability of violating such constraints. A chance-constrained mixed logical-linear program (CC-MLLP) is a natural formulation, allowing for the specification of linear and logical constraints, with probabilistic continuous variables. The formalism can be used to describe problems ranging from autonomous underwater vehicle path planning, to network routing under uncertainty. While naive encodings of CC-MLLPs can be solved with generalised solvers, the solution time may be unreasonable. In this work, we study architectures to speed up solutions by partitioning CC-MLLPs into the discrete and continuous portions. In order to provide faster solutions, we investigate methods for speeding up the solutions to the continuous chance-constrained linear programs. Further, by exploiting the new solution methods, we develop techniques for guiding the discrete decision making portion of the problem. The resulting algorithm achieves 10 times speed up over prior approaches on autonomous path planning benchmarks.

IROS Conference 2023 Conference Paper

A Pretouch Perception Algorithm for Object Material and Structure Mapping to Assist Grasp and Manipulation Using a DMDSM Sensor

  • Fengzhi Guo
  • Shuangyu Xie
  • Di Wang 0020
  • Cheng Fang
  • Jun Zou
  • Dezhen Song

We report a new material and structure mapping (MSM) algorithm to assist robotic grasping and manipulation. Building on our new sensor development, the algorithm has four main components: 1) detection of time-of-flight (ToF) durations for the dual modalities of optoacoustic (OA) and pulse-echo ultrasound (US), 2) contour reconstruction by fusing OA and US signals, 3) local noise filtering by checking local consistency of material and structure label (MSL), and 4) medium boundary searching that identifies class boundaries through two-staged clustering and boundary establishment using support vector machine (SVM) hyperplanes. We have implemented our algorithm and tested it with multiple common household items. The experimental results have successfully validated our algorithm design which shows that the average error of contour reconstruction is 0. 05 mm and the true positive rate of MSL is over 98%.

ICRA Conference 2023 Conference Paper

The Third Generation (G3) Dual-Modal and Dual Sensing Mechanisms (DMDSM) Pretouch Sensor for Robotic Grasping

  • Cheng Fang
  • Shuangliang Li
  • Di Wang 0020
  • Fengzhi Guo
  • Dezhen Song
  • Jun Zou

Fingertip-mounted pretouch sensors are very useful for robotic grasping. In this paper, we report a new (G3) dual-modal and dual sensing mechanisms (DMDSM) pretouch sensor for near-distance ranging and material sensing, which is based on pulse-echo ultrasound (US) and optoacoustics (OA). Different from previously reported versions, the G3 sensor utilizes a self-focused US/OA transceiver, thereby eliminating the need of a bulky parabolic reflective mirror for focusing the ultrasound and laser beams. The self-focused laser and ultrasound beams can be easily steered by a (flat) scanning mirror which expands from single-point ranging and detection to areal mapping or imaging. To verify the new design, a prototype G3 DMDSM sensor with a scanning mirror is fabricated. The US and OA ranging performances are tested in experiments. Together with the scanning mirror, thin wire targets made of same or different materials at different positions are scanned and imaged. The ranging and imaging results show that the G3 DMDSM sensor can provide new and better pretouch mapping and imaging capabilities for robotic grasping than its predecessors.

JAIR Journal 2022 Journal Article

Chance-constrained Static Schedules for Temporally Probabilistic Plans

  • Cheng Fang
  • Andrew J. Wang
  • Brian C. Williams

Time management under uncertainty is essential to large scale projects. From space exploration to industrial production, there is a need to schedule and perform activities. given complex specifications on timing. In order to generate schedules that are robust to uncertainty in the duration of activities, prior work has focused on a problem framing that uses an interval-bounded uncertainty representation. However, such approaches are unable to take advantage of known probability distributions over duration. In this paper we concentrate on a probabilistic formulation of temporal problems with uncertain duration, called the probabilistic simple temporal problem. As distributions often have an unbounded range of outcomes, we consider chance-constrained solutions, with guarantees on the probability of meeting temporal constraints. By considering distributions over uncertain duration, we are able to use risk as a resource, reason over the relative likelihood of outcomes, and derive higher utility solutions. We first demonstrate our approach by encoding the problem as a convex program. We then develop a more efficient hybrid algorithm whose parent solver generates risk allocations and whose child solver generates schedules for a particular risk allocation. The child is made efficient by leveraging existing interval-bounded scheduling algorithms, while the parent is made efficient by extracting conflicts over risk allocations. We perform numerical experiments to show the advantages of reasoning over probabilistic uncertainty, by comparing the utility of schedules generated with risk allocation against those generated from reasoning over bounded uncertainty. We also empirically show that solution time is greatly reduced by incorporating conflict-directed risk allocation.

ICRA Conference 2022 Conference Paper

The Second Generation (G2) Fingertip Sensor for Near-Distance Ranging and Material Sensing in Robotic Grasping

  • Cheng Fang
  • Di Wang 0020
  • Dezhen Song
  • Jun Zou

To continuously improve robotic grasping, we are interested in developing a contactless fingertip-mounted sensor for near-distance ranging and material sensing. Previously, we demonstrated a dual-modal and dual sensing mechanisms (DMDSM) pretouch sensor prototype based on pulse-echo ultrasound and optoacoustics. However, the complex system, the bulky and expensive pulser-receiver, and the omni-directionally sensitive microphone block the sensor from practical applications in real robotic fingers. To address these issues, we report the second generation (G2) DMDSM sensor without the pulser-receiver and microphone, which is made possible by redesigning the ultrasound transmitter and receiver to gain much wider acoustic bandwidth. To verify our design, a prototype of the G2 DMDSM sensor has been fabricated and tested. The testing results show that the G2 DMDSM sensor can achieve better ranging and similar material/structure sensing performance, but with much-simplified configuration and operation. The primary results indicate that the G2 DMDSM sensor could provide a promising solution for fingertip pretouch sensing in robotic grasping.

ICRA Conference 2021 Conference Paper

Fingertip Pulse-Echo Ultrasound and Optoacoustic Dual-Modal and Dual Sensing Mechanisms Near-Distance Sensor for Ranging and Material Sensing in Robotic Grasping

  • Cheng Fang
  • Di Wang 0020
  • Dezhen Song
  • Jun Zou

To improve robotic grasping, we are interested in developing a new non-contact fingertip-mounted sensor for near-distance ranging and material sensing. Here we report new progress in combining direct pulse-echo ultrasound and optoacoustic effects in sensor design to deal with optically and/or acoustically challenging targets (OACTs). Our dual-modal and dual sensing mechanisms (DMDSM) sensor design is enabled by a novel wideband ultrasound transmitter embedded inside a piezoelectric (lead zirconate titanate - PZT) ring transducer. The new DMDSM sensor is capable of differentiating a variety of OACTs. To verify our design, both distance ranging tests and material sensing tests have been conducted. The ranging tests show the sensor can perform both optoacoustic ranging (for light-absorbing materials) and pulse-echo ultrasound ranging (for reflective or transparent materials). For material sensing, the dual-modal spectra from OACTs are collected to compare the new sensor with previous designs. The overall 100% accuracy from the confusion matrices indicates the initial success of our sensor design in differentiating conventional targets as well as the OACTs with the new DMDSM sensor.

SoCS Conference 2021 Conference Paper

Generalized Conflict-Directed Search for Optimal Ordering Problems

  • Jingkai Chen
  • Yuening Zhang
  • Cheng Fang
  • Brian Williams 0001

Solving planning and scheduling problems for multiple tasks with highly coupled state and temporal constraints is notoriously challenging. An appealing approach to effectively decouple the problem is to judiciously order the events such that decisions can be made over sequences of tasks. As many problems encountered in practice are over-constrained, we must instead find relaxed solutions in which certain requirements are dropped. This motivates a formulation of optimality with respect to the costs of relaxing constraints and the problem of finding an optimal ordering under which this relaxing cost is minimum. In this paper, we present Generalized Conflict-directed Ordering (GCDO), a branch-and-bound ordering method that generates an optimal total order of events by leveraging the generalized conflicts of both inconsistency and suboptimality from sub-solvers for cost estimation and solution space pruning. Due to its ability to reason over generalized conflicts, GCDO is much more efficient in finding high-quality total orders than the previous conflict-directed approach CDITO. We demonstrate this by benchmarking on temporal network configuration problems, which involves managing networks over time and makes necessary tradeoffs between network flows against CDITO and Mixed Integer-Linear Programing (MILP). Our algorithm is able to solve two orders of magnitude more benchmark problems to optimality and twice the problems compared to CDITO and MILP within a runtime limit, respectively.

IROS Conference 2020 Conference Paper

Fingertip Non-Contact Optoacoustic Sensor for Near-Distance Ranging and Thickness Differentiation for Robotic Grasping *

  • Cheng Fang
  • Di Wang 0020
  • Dezhen Song
  • Jun Zou

We report the feasibility study of a new optoacoustic sensor for both near-distance ranging and material thickness classification for robotic grasping. It is based on the optoacoustic effect where focused laser pulses are used to generate wideband ultrasound signals in the target. With a much smaller optical focal spot, the optoacoustic sensor achieves a lateral resolution of 93 μm, which is six times higher than ultrasound pulse-echo ranging under the same condition. A new multi-mode wideband PZT (lead zirconate titanate) transducer is built to properly receive the wideband optoacoustic signal. The ability to receive both low- and high-frequency components of the optoacoustic signal enhances the material sensing capability, which makes it promising to determine not only material type but also the sub-surface structures. For demonstration, optoacoustic spectra are collected from hard and soft materials with different thickness. A Bag-of-SFA-Symbols (BOSS) classifier is designed to perform primary material and then thickness classification based on the optoacoustic spectra. The accuracy of material / thickness classification reaches ≥ 99% and ≥ 94%, respectively, which shows the feasibility of differentiating solid materials with different thickness by the optoacoustic sensor.

ICAPS Conference 2019 Conference Paper

Efficiently Exploring Ordering Problems through Conflict-Directed Search

  • Jingkai Chen
  • Cheng Fang
  • David Wang
  • Andrew J. Wang
  • Brian Williams 0001

In planning and scheduling, solving problems with both state and temporal constraints is hard since these constraints may be highly coupled. Judicious orderings of events enable solvers to efficiently make decisions over sequences of actions to satisfy complex hybrid specifications. The ordering problem is thus fundamental to planning. Promising recent works have explored the ordering problem as search, incorporating a special tree structure for efficiency. However, such approaches only reason over partial order specifications. Having observed that an ordering is inconsistent with respect to underlying constraints, prior works do not exploit the tree structure to efficiently generate orderings that resolve the inconsistency. In this paper, we present Conflict-directed Incremental Total Ordering (CDITO), a conflict-directed search method to incrementally and systematically generate event total orders given ordering relations and conflicts returned by sub-solvers. Due to its ability to reason over conflicts, CDITO is much more efficient than Incremental Total Ordering. We demonstrate this by benchmarking on temporal network configuration problems that involve routing network flows and allocating bandwidth resources over time.

ICRA Conference 2019 Conference Paper

Exploitation of Environment Support Contacts for Manipulation Effort Reduction of a Robot Arm

  • Cheng Fang
  • Navvab Kashiri
  • Giuseppe Francesco Rigano
  • Arash Ajoudani
  • Nikos G. Tsagarakis

Humans commonly exploit interaction with the environment constraints to assist the execution of the loco-manipulation tasks they perform. One particular example is the exploration of contacts during manipulation to relax the loading of those arm joints that are not directly involved in the generation of the manipulation motions and forces, e. g. establishing a contact with the elbow joint to reduce the effort of the upper arm while executing wrist level manipulation. In this paper, we shall explore the possibility of actively (a) utilizing the environment for a non-end-effector support contact towards reducing the joints efforts during manipulation tasks. This is achieved by our proposed control scheme with a three-level hierarchical compliance controller. The highest priority task is assigned to an impedance control that regulates the interaction at the contact control point on the arm in the normal direction of the support plane prior to contact, and is switched to an optimal contact force control for minimizing the joint effort after the contact is built. The second priority task is an impedance control at the same point in the tangential directions of the plane to stabilize the contact. In the end, an impedance behavior at the end-effector is designed to deal with the interaction forces required by the manipulation tasks. The efficacy of the proposed control scheme was corroborated by simulations and experiments, where significant joint effort reduction was observed.

ICRA Conference 2019 Conference Paper

Toward Fingertip Non-Contact Material Recognition and Near-Distance Ranging for Robotic Grasping

  • Cheng Fang
  • Di Wang 0020
  • Dezhen Song
  • Jun Zou

We report the feasibility study of a new acoustic and optical bi-modal distance & material sensor for robotic grasping. The new sensor is designed to be mounted on the robot fingertip to provide last-moment perception before contact happens. It is based on both pulse-echo ultrasound and optoacoustic effects enabled by single-element air-coupled transducers. In contrast to conventional contact-based and recent pre-touch approaches, this new method overcomes their disadvantages and provides robotic fingers with the capability to detect the distance and material type of the target at a near distance before contact occurs, which is crucial for robust and nimble grasping. The proposed sensor has been tested with different materials, shapes, and porous properties. The experimental results show that this sensor design is functional and practical.

IROS Conference 2018 Conference Paper

Online Human Muscle Force Estimation for Fatigue Management in Human-Robot Co-Manipulation

  • Luka Peternel
  • Cheng Fang
  • Nikos G. Tsagarakis
  • Arash Ajoudani

In this paper, we propose a novel method for selective management of muscle fatigue in human-robot co-manipulation. The proposed framework enables the detection of excessive fatigue levels of an individual muscle group while executing a certain task, and provides anticipatory robotic responses to distribute the effort among less-fatigued muscles of human arm. Our approach uses a machine learning technique to enable online predictions of muscle forces in different arm configurations and endpoint interaction forces. The estimated muscle forces are then used for the model-based estimation of muscle fatigue levels. Through optimisation, the fatigue management system can alter the task execution in a way that specific fatigued muscles are offloaded, while at the same time enables the production of task force using muscles with lower levels of fatigue. The main advantage of the proposed method is that it can operate online, and that all the measurements are performed by the robot sensory system, which can significantly increase the applicability in real-world scenarios. To validate the proposed method, we performed proof-of-concept experiments where the task of the human operator was to use a tool to polish an object that was manipulated by the robot.

IROS Conference 2017 Conference Paper

A torque-controlled humanoid robot riding on a two-wheeled mobile platform

  • Songyan Xin
  • Yangwei You
  • Chengxu Zhou
  • Cheng Fang
  • Nikos G. Tsagarakis

This paper is motivated by the questions: What would happen if a humanoid robot is put on a Segway? Is it possible for the humanoid robot to use this transportation device that is specifically designed for human? Simulation involving a two-wheeled mobile platform (TWMP) and our humanoid robot COMAN (COmpliant HuMANoid Platform) shows that it is indeed feasible without any hardware modification. Regarding the implementation, the full dynamics of the humanoid robot is considered and quadratic optimization is employed to generate whole-body joint torques to realise two types of tasks according to the interaction type between the TWMP and the humanoid robot. The TWMP is considered as unknown disturbance and the humanoid robot has to keep balancing on it in the first type of task. On the contrary, the active movement of the humanoid robot is utilised as an interface to intuitively drive the TWMP in the second type of task. For both tasks, tracking the position of center of mass (CoM) and regulating the angular momentum around it are considered as primary objectives, stabilizing the posture of certain part of its body is optional. In addition, both tasks are repeated on uneven terrain to demonstrate the robustness of the control method.

IJCAI Conference 2017 Conference Paper

Efficient Algorithms And Representations For Chance-constrained Mixed Constraint Programming

  • Cheng Fang

Resistance to adoption of autonomous systems comes in part from the perceived unreliability of the systems. Concerns can be addressed by approaches that guarantee the probability of success. This is achieved in chance-constrained constraint programming (CC-CP) by imposing constraints required for success, and providing upper-bounds on the probability of violating constraints. This extended abstract reports on novel uncertainty representations to address problems prevalent in current methods.

JAIR Journal 2017 Journal Article

Resolving Over-Constrained Temporal Problems with Uncertainty through Conflict-Directed Relaxation

  • Peng Yu
  • Brian Williams
  • Cheng Fang
  • Jing Cui
  • Patrik Haslum

Over-subscription, that is, being assigned too many things to do, is commonly encountered in temporal scheduling problems. As human beings, we often want to do more than we can actually do, and underestimate how long it takes to perform each task. Decision makers can benefit from aids that identify when these failure situations are likely, the root causes of these failures, and resolutions to these failures. In this paper, we present a decision assistant that helps users resolve over-subscribed temporal problems. The system works like an experienced advisor that can quickly identify the cause of failure underlying temporal problems and compute resolutions. The core of the decision assistant is the Best-first Conflict-Directed Relaxation (BCDR) algorithm, which can detect conflicting sets of constraints within temporal problems, and computes continuous relaxations for them that weaken constraints to the minimum extent, instead of removing them completely. BCDR is an extension to the Conflict-Directed A* algorithm, first developed in the model-based reasoning community to compute most likely system diagnoses or reconfigurations. It generalizes the discrete conflicts and relaxations, to hybrid conflicts and relaxations, which denote minimal inconsistencies and minimal relaxations to both discrete and continuous relaxable constraints. In addition, BCDR is capable of handling temporal uncertainty, expressed as either set-bounded or probabilistic durations, and can compute preferred trade-offs between the risk of violating a schedule requirement, versus the loss of utility by weakening those requirements. BCDR has been applied to several decision support applications in different domains, including deep-sea exploration, urban travel planning and transit system management. It has demonstrated its effectiveness in helping users resolve over-subscribed scheduling problems and evaluate the robustness of existing solutions. In our benchmark experiments, BCDR has also demonstrated its efficiency on solving large-scale scheduling problems in the aforementioned domains. Thanks to its conflict-driven approach for computing relaxations, BCDR achieves one to two orders of magnitude improvements on runtime performance when compared to state-of-the-art numerical solvers.

ICAPS Conference 2016 Conference Paper

PARIS: A Polynomial-Time, Risk-Sensitive Scheduling Algorithm for Probabilistic Simple Temporal Networks with Uncertainty

  • Pedro Henrique de Rodrigues Quemel e Assis Santana
  • Tiago Vaquero
  • Cláudio Toledo 0001
  • Andrew J. Wang
  • Cheng Fang
  • Brian Williams 0001

Inspired by risk-sensitive, robust scheduling for planetary rovers under temporal uncertainty, this work introduces the Probabilistic Simple Temporal Network with Uncertainty (PSTNU), a temporal planning formalism that unifies the set-bounded and probabilistic temporal uncertainty models from the STNU and PSTN literature. By allowing any combination of these two types of uncertainty models, PSTNU's can more appropriately reflect the varying levels of knowledge that a mission operator might have regarding the stochastic duration models of different activities. We also introduce PARIS, a novel sound and provably polynomial-time algorithm for risk-sensitive strong scheduling of PSTNU's. Due to its fully linear problem encoding for typical temporal uncertainty models, PARIS is shown to outperform the current fastest algorithm for risk-sensitive strong PSTN scheduling by nearly four orders of magnitude in some instances of a popular probabilistic scheduling dataset, while results on a new PSTNU scheduling dataset indicate that PARIS is, indeed, amenable for deployment on resource-constrained hardware.

IROS Conference 2015 Conference Paper

A reduced-complexity description of arm endpoint stiffness with applications to teleimpedance control

  • Arash Ajoudani
  • Cheng Fang
  • Nikos G. Tsagarakis
  • Antonio Bicchi

Effective and stable execution of a remote manipulation task in an uncertain environment requires that the task force and position trajectories of the slave robot be appropriately commanded. To achieve this goal, in teleimpedance control, a reference command which consists of the stiffness and position profiles of the master is computed and realized by the compliant slave robot in real-time. This highlights the need for a suitable and computationally efficient tracking of the human limb stiffness profile in real-time. In this direction, based on the observations in human neuromotor control which give evidence on the predominant use of the arm configuration in directional adjustments of the endpoint stiffness profile, and the role of muscular co-activations which contribute to a coordinated regulation of the task stiffness in all directions, we propose a novel and computationally efficient model of the arm endpoint stiffness behaviour. Real-time tracking of the human arm kinematics is achieved using an arm triangle monitored by three markers placed at the shoulder, elbow and wrist level. In addition, a co-contraction index is defined using muscular activities of a dominant antagonistic muscle pair. Calibration and identification of the model parameters are carried out experimentally, using perturbation-based arm endpoint stiffness measurements in different arm configurations and co-contraction levels of the chosen muscles. Results of this study suggest that the proposed model enables the master to naturally execute a remote task by modulating the direction of the major axes of the endpoint stiffness and its volume using arm configuration and the co-activation of the involved muscles, respectively.

ICAPS Conference 2015 Conference Paper

Optimising Bounds in Simple Temporal Networks with Uncertainty under Dynamic Controllability Constraints

  • Jing Cui
  • Peng Yu
  • Cheng Fang
  • Patrik Haslum
  • Brian Williams 0001

Dynamically controllable simple temporal networks with uncertainty (STNU) are widely used to represent temporal plans or schedules with uncertainty and execution flexibility. While the problem of testing an STNU for dynamic controllability is well studied, many use cases — for example, problem relaxation or schedule robustness analysis — require optimising a function over STNU time bounds subject to the constraint that the network is dynamically controllable. We present a disjunctive linear constraint model of dynamic controllability, show how it can be used to formulate a range of applications, and compare a mixed-integer, a non-linear programming, and a conflict-directed search solver on the resulting optimisation problems. Our model also provides the first solution to the problem of optimisation over a probabilistic STN subject to dynamic controllability and chance constraints.

AAAI Conference 2015 Conference Paper

Resolving Over-Constrained Probabilistic Temporal Problems through Chance Constraint Relaxation

  • Peng Yu
  • Cheng Fang
  • Brian Williams

When scheduling tasks for field-deployable systems, our solutions must be robust to the uncertainty inherent in the real world. Although human intuition is trusted to balance reward and risk, humans perform poorly in risk assessment at the scale and complexity of real world problems. In this paper, we present a decision aid system that helps human operators diagnose the source of risk and manage uncertainty in temporal problems. The core of the system is a conflict-directed relaxation algorithm, called Conflict-Directed Chance-constraint Relaxation (CDCR), which specializes in resolving overconstrained temporal problems with probabilistic durations and a chance constraint bounding the risk of failure. Given a temporal problem with uncertain duration, CDCR proposes execution strategies that operate at acceptable risk levels and pinpoints the source of risk. If no such strategy can be found that meets the chance constraint, it can help humans to repair the overconstrained problem by trading off between desirability of solution and acceptable risk levels. The decision aid has been incorporated in a mission advisory system for assisting oceanographers to schedule activities in deepsea expeditions, and demonstrated its effectiveness in scenarios with realistic uncertainty.

AAAI Conference 2014 Conference Paper

Chance-Constrained Probabilistic Simple Temporal Problems

  • Cheng Fang
  • Peng Yu
  • Brian Williams

Scheduling under uncertainty is essential to many autonomous systems and logistics tasks. Probabilistic methods for solving temporal problems exist which quantify and attempt to minimize the probability of schedule failure. These methods are overly conservative, resulting in a loss in schedule utility. Chance constrained formalism address over-conservatism by imposing bounds on risk, while maximizing utility subject to these risk bounds. In this paper we present the probabilistic Simple Temporal Network (pSTN), a probabilistic formalism for representing temporal problems with bounded risk and a utility over event timing. We introduce a constrained optimisation algorithm for pSTNs that achieves compactness and efficiency through a problem encoding in terms of a parameterised STNU and its reformulation as a parameterised STN. We demonstrate through a car sharing application that our chance-constrained approach runs in the same time as the previous probabilistic approach, yields solutions with utility improvements of at least 5% over previous arts, while guaranteeing operation within the specified risk bound.

ICRA Conference 2014 Conference Paper

General probabilistic bounds for trajectories using only mean and variance

  • Cheng Fang
  • Brian Williams 0001

Two ideas have gained traction in research in the robotics planning community. Activity planning has become popular where a library of predefined manipulation of the vehicle state is accessible, and is commonly used for missions with complex goal specifications. Another focus has been chance-constrained programming as a method of providing robust motion planning, in which the probability of failure is bounded. A combination of the two would allow for robust satisfaction of complex directives. However, to perform chance-constrained activity planning, we must be able to provide probabilistic bounds on the trajectory of the vehicle. While this may be done through propagation of statistics, we would require information about the actuation noise for the vehicle dynamics. In addition to such parameters as mean and variance, we also need to know the appropriate function for the noise. In many cases, the exact distribution of the actuation noise may not be known, although researchers can easily approximate the first two moments through calibrations. In this work we look at statistics propagation when only the first two moments of the actuation uncertainty is known, assuming white noise. We show that for linear systems, propagation is exact. Further, by looking at the expected error squared as a stochastic process, we can show that it is a submartingale under certain assumptions, and thus derive error bounds for deviation from mean over the duration of the entire path. We empirically show that, for nonlinear dynamics, we may approximate the propagation with the unscented transform, and obtain the corresponding bounds.

ICAPS Conference 2014 Conference Paper

Resolving Uncontrollable Conditional Temporal Problems Using Continuous Relaxations

  • Peng Yu
  • Cheng Fang
  • Brian Williams 0001

Uncertainty is commonly encountered in temporal scheduling and planning problems, and can often lead to over-constrained situations. Previous relaxation algorithms for over-constrained temporal problems only work with requirement constraints, whose outcomes can be controlled by the agents. When applied to uncontrollable durations, these algorithms may only satisfy a subset of the random outcomes and hence their relaxations may fail during execution. In this paper, we present a new relaxation algorithm, Conflict-Directed Relaxation with Uncertainty (CDRU), which generates relaxations that restore the controllability of conditional temporal problems with uncontrollable durations. CDRU extends the Best-first Conflict-Directed Relaxation (BCDR) algorithm to uncontrollable temporal problems. It generalizes the conflict-learning process to extract conflicts from strong and dynamic controllability checking algorithms, and resolves the conflicts by both relaxing constraints and tightening uncontrollable durations. Empirical test results on a range of trip scheduling problems show that CDRU is efficient in resolving large scale uncontrollable problems: computing strongly controllable relaxations takes the same order of magnitude in time compared to consistent relaxations that do not account for uncontrollable durations. While computing dynamically controllable relaxations takes two orders of magnitude more time, it provides significant improvements in solution quality when compared to strongly controllable relaxations.

AAAI Conference 2012 Conference Paper

Symbolic Dynamic Programming for Continuous State and Action MDPs

  • Zahra Zamani
  • Scott Sanner
  • Cheng Fang

Many real-world decision-theoretic planning problems are naturally modeled using both continuous state and action (CSA) spaces, yet little work has provided exact solutions for the case of continuous actions. In this work, we propose a symbolic dynamic programming (SDP) solution to obtain the optimal closed-form value function and policy for CSA-MDPs with multivariate continuous state and actions, discrete noise, piecewise linear dynamics, and piecewise linear (or restricted piecewise quadratic) reward. Our key contribution over previous SDP work is to show how the continuous action maximization step in the dynamic programming backup can be evaluated optimally and symbolically — a task which amounts to symbolic constrained optimization subject to unknown state parameters; we further integrate this technique to work with an efficient and compact data structure for SDP — the extended algebraic decision diagram (XADD). We demonstrate empirical results on a didactic nonlinear planning example and two domains from operations research to show the first automated exact solution to these problems.

v2026.09.13