Xiaoming Zheng

AAAI Conference 2014 Conference Paper

Trust Prediction with Propagation and Similarity Regularization

• Xiaoming Zheng
• Yan Wang
• Mehmet Orgun
• Youliang Zhong
• Guanfeng Liu

Online social networks have been used for a variety of rich activities in recent years, such as investigating potential employees and seeking recommendations of high quality services and service providers. In such activities, trust is one of the most critical factors for the decisionmaking of users. In the literature, the state-of-the-art trust prediction approaches focus on either dispositional trust tendency and propagated trust of the pair-wise trust relationships along a path or the similarity of trust rating values. However, there are other influential factors that should be taken into account, such as the similarity of the trust rating distributions. In addition, tendency, propagated trust and similarity are of different types, as either personal properties or interpersonal properties. But the difference has been neglected in existing models. Therefore, in trust prediction, it is necessary to take all the above factors into consideration in modeling, and process them separately and differently. In this paper we propose a new trust prediction model based on trust decomposition and matrix factorization, considering all the above influential factors and differentiating both personal and interpersonal properties. In this model, we first decompose trust into trust tendency and tendency-reduced trust. Then, based on tendencyreduced trust ratings, matrix factorization with a regularization term is leveraged to predict the tendencyreduced values of missing trust ratings, incorporating both propagated trust and the similarity of users’ rating habits. In the end, the missing trust ratings are composed with predicted tendency-reduced values and trust tendency values. Experiments conducted on a realworld dataset illustrate significant improvement delivered by our approach in trust prediction accuracy over the state-of-the-art approaches.

IJCAI Conference 2011 Conference Paper

Generalized Reaction Functions for Solving Complex-Task Allocation Problems

• Xiaoming Zheng
• Sven Koenig

We study distributed task-allocation problems wherecooperative agents need to perform some tasks simultaneously. Examples are multi-agent routing problems where several agents need to visit some targets simultaneously, for example, to move obstacles out of the way cooperatively. In this paper, we first generalize the concept of reaction functions proposed in the literature to characterize the agent costs of performing multiple complex tasks. Second, we show how agents can construct and approximate reaction functions in a distributed way. Third, we show how reaction functions can be used by an auction-like algorithm to allocate tasks to agents. Finally, we show empirically that the team costs of our algorithms are substantially smaller than those of an existing state-of-the-art allocation algorithm for complex tasks.

AAAI Conference 2010 Conference Paper

Market-Based Algorithms for Allocating Complex Tasks

• Xiaoming Zheng
• Sven Koenig

AAAI Conference 2010 Conference Paper

Model AI Assignments

• Todd Neller
• John DeNero
• Dan Klein
• Sven Koenig
• William Yeoh
• Xiaoming Zheng
• Kenny Daniel
• Alex Nash

AAAI Conference 2010 Conference Paper

Sequential Incremental-Value Auctions

• Xiaoming Zheng
• Sven Koenig

We study the distributed allocation of tasks to cooperating robots in real time, where each task has to be assigned to exactly one robot so that the sum of the latencies of all tasks is as small as possible. We propose a new auction-like algorithm, called Sequential Incremental-Value (SIV) auction, which assigns tasks to robots in multiple rounds. The idea behind SIV auctions is to assign as many tasks per round to robots as possible as long as their individual costs for performing these tasks are at most a given bound, which increases exponentially from round to round. Our theoretical results show that the team costs of SIV auctions are at most a constant factor larger than minimal.

IJCAI Conference 2009 Conference Paper

• Xiaoming Zheng
• Sven Koenig

In this paper, we study distributed algorithms for cooperative agents that allow them to exchange their assigned tasks in order to reduce their team cost. We define a new type of contract, called K-swaps, that describes multiple task exchanges among multiple agents at a time, which generalizes the concept of single task exchanges. We design a distributed algorithm that constructs all possible K-swaps that reduce the team cost of a given task allocation and show that each agent typically only needs to communicate a small part of its local computation results to the other agents. We then demonstrate empirically that K-swaps can reduce the team costs of several existing task-allocation algorithms significantly even if K is small.

IROS Conference 2009 Conference Paper

Negotiation with reaction functions for solving complex task allocation problems

• Xiaoming Zheng
• Sven Koenig

We study task-allocation problems where cooperative robots need to perform tasks simultaneously. We develop a distributed negotiation procedure that allows robots to find all task exchanges that reduce the team cost of a given task allocation, without robots having to know how other robots compute their robot costs. Finally, we demonstrate empirically that our negotiation procedure can substantially reduce the team costs of task allocations resulting from existing task-allocation procedures, including sequential single-item auctions.

AAMAS Conference 2008 Conference Paper

Reaction Functions for Task Allocation to Cooperative Agents

• Xiaoming Zheng
• Sven Koenig

In this paper, we present ARF, our initial effort at solving taskallocation problems where cooperative agents need to perform tasks simultaneously. An example is multi-agent routing problems where several agents need to visit targets simultaneously, for example, to move obstacles out of the way cooperatively. First, we propose reaction functions as a novel way of characterizing the costs of agents in a distributed way. Second, we show how to approximate reaction functions so that their computation and communication times are polynomial. Third, we show how reaction functions can be used by a central planner to allocate tasks to agents. Finally, we show experimentally that the resulting task allocations are better than those of other greedy methods that do not use reaction functions.

IJCAI Conference 2007 Conference Paper

• Sven Koenig
• Craig Tovey
• Xiaoming Zheng
• Ilgaz Sungur

We study auction-like algorithms for the distributed allocation of tasks to cooperating agents. To reduce the team cost of sequential single-item auction algorithms, we generalize them to assign more than one additional task during each round, which increases their similarity to combinatorial auction algorithms. We show that, for a given number of additional tasks to be assigned during each round, every agent needs to submit only a constant number of bids per round and the runtime of winner determination is linear in the number of agents. The communication and winner determination costs do not depend on the number of tasks and thus scale to a large number of tasks for small bundle sizes. We then demonstrate empirically that the team cost of sequential bundle-bid single-sale (= single-item) auction algorithms can be substantially smaller than that without bundles for multi-agent routing problems with capacity constraints.

YNIMG Journal 2007 Journal Article

Predictive oncology: A review of multidisciplinary, multiscale in silico modeling linking phenotype, morphology and growth

• Sandeep Sanga
• Hermann B. Frieboes
• Xiaoming Zheng
• Robert Gatenby
• Elaine L. Bearer
• Vittorio Cristini

Empirical evidence and theoretical studies suggest that the phenotype, i. e. , cellular- and molecular-scale dynamics, including proliferation rate and adhesiveness due to microenvironmental factors and gene expression that govern tumor growth and invasiveness, also determine gross tumor-scale morphology. It has been difficult to quantify the relative effect of these links on disease progression and prognosis using conventional clinical and experimental methods and observables. As a result, successful individualized treatment of highly malignant and invasive cancers, such as glioblastoma, via surgical resection and chemotherapy cannot be offered and outcomes are generally poor. What is needed is a deterministic, quantifiable method to enable understanding of the connections between phenotype and tumor morphology. Here, we critically assess advantages and disadvantages of recent computational modeling efforts (e. g. , continuum, discrete, and cellular automata models) that have pursued this understanding. Based on this assessment, we review a multiscale, i. e. , from the molecular to the gross tumor scale, mathematical and computational “first-principle” approach based on mass conservation and other physical laws, such as employed in reaction-diffusion systems. Model variables describe known characteristics of tumor behavior, and parameters and functional relationships across scales are informed from in vitro, in vivo and ex vivo biology. We review the feasibility of this methodology that, once coupled to tumor imaging and tumor biopsy or cell culture data, should enable prediction of tumor growth and therapy outcome through quantification of the relation between the underlying dynamics and morphological characteristics. In particular, morphologic stability analysis of this mathematical model reveals that tumor cell patterning at the tumor–host interface is regulated by cell proliferation, adhesion and other phenotypic characteristics: histopathology information of tumor boundary can be inputted to the mathematical model and used as a phenotype-diagnostic tool to predict collective and individual tumor cell invasion of surrounding tissue. This approach further provides a means to deterministically test effects of novel and hypothetical therapy strategies on tumor behavior.

IROS Conference 2007 Conference Paper

Robot coverage of terrain with non-uniform traversability

• Xiaoming Zheng
• Sven Koenig

In this paper, we study how multiple robots can cover known terrain quickly. We extend Multi-Robot Forest Coverage, a state-of-the-art multi-robot coverage algorithm, from terrain with uniform traversability to terrain with nonuniform traversability, which is nontrivial. We prove that its cover times are at most about sixteen times larger than minimal and demonstrate experimentally that they are significantly smaller than those of an alternative multi-robot coverage algorithm.

IROS Conference 2006 Conference Paper

Improving Sequential Single-Item Auctions

• Xiaoming Zheng
• Sven Koenig
• Craig A. Tovey

We study how to improve sequential single-item auctions that assign targets to robots for exploration tasks such as environmental clean-up, space-exploration, and search and rescue missions. We exploit the insight that the resulting travel distances are small if the bidding and winner-determination rules are designed to result in hillclimbing, namely to assign an additional target to a robot in each round of the sequential single-item auction so that the team cost increases the least. We study the impact of increasing the lookahead of hillclimbing and using roll-outs to improve the evaluation of partial target assignments. We describe the bidding and winner-determination rules of the resulting sequential single-item auctions and evaluate them experimentally, with surprising results: larger lookaheads do not improve sequential single-item auctions reliably while only a small number of roll-outs in early rounds already improve them substantially

IROS Conference 2005 Conference Paper

Multi-robot forest coverage

• Xiaoming Zheng
• Sonal Jain
• Sven Koenig
• David Kempe 0001

One of the main applications of mobile robots is terrain coverage: visiting each location in known terrain. Terrain coverage is crucial for lawn mowing, cleaning, harvesting, search-and-rescue, intrusion detection and mine clearing. Naturally, coverage can be sped up with multiple robots. In this paper, we describe multi-robot forest coverage, a new multi-robot coverage algorithm based on an algorithm by Even et al. (2004) for finding a tree cover with trees of balanced weights. The cover time of multi-robot forest coverage is at most eight times larger than optimal, and our experiments show it to perform significantly better than existing multi-robot coverage algorithms.