Author name cluster

Fuhan Yan

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.

7 papers

2 author rows

EAAI Journal 2024 Journal Article

Multi-robot task allocation for optional tasks with hidden workload: Using a model-based hyper-heuristic strategy

Fuhan Yan
Kai Di
Bin Ge
Luoliang Liu
Zeren Wang
Wenjian Fan
Didi Hu

Multi-robot task allocation (MRTA) is a classical problem in multi-robot systems. This paper analyzes the situations where the objective of the robots is to minimize the time cost of completing a certain proportion of tasks instead of completing all tasks, i. e. , the tasks are optional. Besides, in this problem, the true workload of each task is initially hidden and can only be known after the preliminary workload is completed. As the tasks are optional, selecting a suitable combination of the tasks is quite important. The main challenge in this problem is that the robots cannot exactly select the tasks that are easy to complete because the true workload is hidden. In previous similar problems (i. e. , MRTA with incomplete information), reallocation-based method is a general method. However, in this problem, if the robots exactly reallocate the tasks after collecting enough information, the sunk costs (i. e. , the tasks that have been partially performed but are not selected in reallocation) limit the decrease of the time cost. Thus, we design a new hyper-heuristic strategy. In detail, a simple heuristic method that lets the robots appropriately give up some allocated tasks is combined with reallocation to design the low-level heuristic (LLH). The high-level strategy (HLS) seeks the optimal setting of LLH based on a meta-heuristic algorithm 1 1 We respectively test particle swarm optimization (PSO) and simulated annealing (SA). . The strategies are tested based on various random instances, and the hyper-heuristic strategy can outperform the benchmark strategies in most instances. In some instances, the maximum improvement of results led by the hyper-heuristic is more than 9%.

Details DOI

TIST Journal 2022 Journal Article

A Foraging Strategy with Risk Response for Individual Robots in Adversarial Environments

Kai Di
Yifeng Zhou
Fuhan Yan
Jiuchuan Jiang
Shaofu Yang
Yichuan Jiang

As an essential problem in robotics, foraging means that robots collect objects from a given environment and return them to a specified location. On many occasions, robots are required to perform foraging tasks in adversarial environments, such as battlefield rescue, where potential adversaries may damage robots with a certain probability. The longer an individual robot moves through adversarial environments, the higher the probability of being damaged by adversaries. The robot system can gain utility only when the robot brings carried objects back to a predetermined home station. Such a risk of being damaged makes returning home at different locations potentially relevant to the expected utility produced by the robot. Thus, the individual robot faces a dilemma when it responds to the potential risks in adversarial environments: whether to return the carried resources home or continue foraging tasks. In this article, two fundamental environment settings are discussed, homogeneous cases and heterogeneous cases. The former is analyzed as having both the optimal substructure property and the non-aftereffect property. Then, we present a dynamic programming (DP) algorithm that can find an optimal solution with polynomial time complexity. For the latter, it is proven that finding an optimal solution is \( \mathcal {NP} \) -hard. We then propose a heuristic algorithm: A division hierarchical path planning (DHPP) algorithm that is based on the idea of dividing the foraging routes generated initially into a certain number of subroutes to dilute risks. Finally, these algorithms are extensively evaluated in simulations, concluding that in adversarial environments, they can significantly improve the productivity of an individual robot before it is damaged.

Details DOI

IJCAI Conference 2022 Conference Paper

Multi-robot Task Allocation in the Environment with Functional Tasks

Fuhan Yan
Kai Di

Multi-robot task allocation (MRTA) problem has long been a key issue in multi-robot systems. Previous studies usually assumed that the robots must complete all tasks with minimum time cost. However, in many real situations, some tasks can be selectively performed by robots and will not limit the achievement of the goal. Instead, completing these tasks will cause some functional effects, such as decreasing the time cost of completing other tasks. This kind of task can be called “functional task”. This paper studies the multi-robot task allocation in the environment with functional tasks. In the problem, neither allocating all functional tasks nor allocating no functional task is always optimal. Previous algorithms usually allocate all tasks and cannot suitably select the functional tasks. Because of the interaction and sequential influence, the total effects of the functional tasks are too complex to exactly calculate. We fully analyze this problem and then design a heuristic algorithm. The heuristic algorithm scores the functional tasks referring to linear threshold model (used to analyze the sequential influence of a functional task). The simulated experiments demonstrate that the heuristic algorithm can outperform the benchmark algorithms.

PDF Details DOI

TAAS Journal 2021 Journal Article

Risk-aware Collection Strategies for Multirobot Foraging in Hazardous Environments

Kai Di
Yifeng Zhou
Jiuchuan Jiang
Fuhan Yan
Shaofu Yang
Yichuan Jiang

Existing studies on the multirobot foraging problem often assume safe settings, in which nothing in an environment hinders the robots’ tasks. In many real-world applications, robots have to collect objects from hazardous environments like earthquake rescue, where possible risks exist, with possibilities of destroying robots. At this stage, there are no targeted algorithms for foraging robots in hazardous environments, which can lead to damage to the robot itself and reduce the final foraging efficiency. A motivating example is a rescue scenario, in which the lack of a suitable solution results in many victims not being rescued after all available robots have been destroyed. Foraging robots face a dilemma after some robots have been destroyed: whether to take over tasks of the destroyed robots or continue executing their remaining foraging tasks. The challenges that arise when attempting such a balance are twofold: (1) the loss of robots adds new constraints to traditional problems, complicating the structure of the solution space, and (2) the task allocation strategy in a multirobot team affects the final expected utility, thereby increasing the dimension of the solution space. In this study, we address these challenges in two fundamental environmental settings: homogeneous and heterogeneous cases. For the former case, a decomposition and grafting mechanism is adopted to split this problem into two weakly coupled problems: the foraging task execution problem and the foraging task allocation problem. We propose an exact foraging task allocation algorithm, and graft it to another exact foraging task execution algorithm to find an optimal solution within the polynomial time. For the latter case, it is proven \( \mathcal {NP} \) -hard to find an optimal solution in polynomial time. The decomposition and grafting mechanism is also adopted here, and our proposed greedy risk-aware foraging algorithm is grafted to our proposed hierarchical agglomerative clustering algorithm to find high-utility solutions with low computational overhead. Finally, these algorithms are extensively evaluated through simulations, demonstrating that compared with various benchmarks, they can significantly increase the utility of objects returned by robots before all the robots have been stopped.

Details DOI

AAMAS Conference 2017 Conference Paper

Pursuing a Faster Evader Based on an Agent Team with Unstable Speeds

Fuhan Yan
Yichuan Jiang

Previous studies of multiagent pursuit-evasion problem usually assume that the pursuers can move at stable speeds. However, in many real cases, the pursuers’ speeds may be unstable. In this paper, we study multiagent pursuit-evasion problem based on pursuers with unstable speeds in a continuous open world. We present a feasible pursuing strategy, and the experimental results show that our strategy can generally lead to higher capture success ratios than previous strategies in the situations where the pursuers’ speeds are unstable.

PDF

JAAMAS Journal 2015 Journal Article

Cross-layers cascade in multiplex networks

Zhaofeng Li
Fuhan Yan
Yichuan Jiang

Abstract The study of information cascade in multiplex networks, where agents are connected by using multiple linking types, has received increasing attention. Compared with the cascade in simplex networks, a noticeable characteristic of the cascade in multiplex networks is that information may be spread between multiple layers. In this study, we focus on the cross-layers cascade, which helps clarify two opposing opinions about the information cascade in multiplex networks: multiplexity can speed up or slow down information cascade. The linear threshold model is generalized into multiplex networks as conjoint agents become active, if the influences of active neighbors in any layer reach a predefined threshold. The preconditions and reasons for the slow-down and speed-up phenomena are discussed using four representative case studies and theoretical analyses. Next, analytical results are validated by using extensive simulations in which the multiplex networks are generated by random, small-world and scale-free network models. It is found that the slow-down phenomenon emerges due to the obstruction of cross-layers cascade which connects the distributed shortest path in multiple layers and the inhibitory effect of negative influence. Conversely, extra short paths or rapid spreading in one additional layer can facilitate the cascade process in existing networks, respectively. Extensive simulations also show that multiplex networks consisting of different network models are more competent for the cascade process compared with multiplex networks generated by a single network model. In conclusion, the concept of cross-layers cascade may elucidate the additional study of information spreading in multiplex networks.

Details DOI

ECAI Conference 2014 Conference Paper

Noised Diffusion Dynamics with Individual Biased Opinion

Fuhan Yan
Zhaofeng Li 0001
Yichuan Jiang

In online social network, the personal information dissemination behavior is reported to be affected by the clash of social individuals' biased opinions. In this paper, we present a model to discuss the influence of individual biased opinion on diffusion dynamics. Based on multi-agent simulations, we obtain some conclusions which are helpful for recommender systems and in controlling diffusion. In addition, our study offers potential avenues for the study of diffusion dynamics with personal biases.

Details