Automated Planning Ghallab, Malik; Nau, Dana; Traverso, Paolo
2004, 2004-05-21
eBook, Book
Automated planning technology now plays a significant role in a variety of demanding applications, ranging from controlling space vehicles and robots to playing the game of bridge. These real-world ...applications create new opportunities for synergy between theory and practice: observing what works well in practice leads to better theories of planning, and better theories lead to better performance of practical applications. Automated Planning mirrors this dialogue by offering a comprehensive, up-to-date resource on both the theory and practice of automated planning. The book goes well beyond classical planning, to include temporal planning, resource scheduling, planning under uncertainty, and modern techniques for plan generation, such as task decomposition, propositional satisfiability, constraint satisfaction, and model checking. The authors combine over 30 years experience in planning research and development to offer an invaluable text to researchers, professionals, and graduate students. *Comprehensively explains paradigms for automated planning. *Provides a thorough understanding of theory and planning practice, and how they relate to each other. *Presents case studies of applications in space, robotics, CAD/CAM, process control, emergency operations, and games.
*Provides a thorough understanding of AI planning theory and practice, and how they relate to each other. *Covers all the contemporary topics of planning, as well as important practical applications of planning, such as model checking and game playing. *Presents case studies and applications in planning engineering, space, robotics, CAD/CAM, process control, emergency operations, and games.*Provides lecture notes, examples of programming assignments, pointers to downloadable planning systems and related information online.
•We study cultural differences in strength of social norms for cooperation and coordination.•We study the effect of societal threats on the evolved strength of such social norms in evolutionary ...models.•We find higher threat leads to stronger norms and more punishment of deviance.•Our results illuminate the evolutionary basis for cultural variation in norm strength.
The strengths of social norms vary considerably across cultures, yet little research has shown whether such differences have an evolutionary basis. Integrating research in cross-cultural psychology with evolutionary game theory, we show that groups that face a high degree of threat develop stronger norms for organizing social interaction, with a higher degree of norm–adherence and higher punishment for deviant behavior. Conversely, groups that have little threat can afford to have weaker norms with less punishment for deviance. Our results apply to two kinds of norms: norms of cooperation, in which individuals must choose whether to cooperate (thereby benefitting everyone) or enrich themselves at the expense of others; and norms of coordination, in which there are several equally good ways for individuals to coordinate their actions, but individuals need to agree on which way to coordinate. This is the first work to show that different degrees of norm strength are evolutionarily adaptive to societal threat. Evolutionary game theoretic models of cultural adaptation may prove fruitful for exploring the causes of many other cultural differences that may be adaptive to particular ecological and historical contexts.
Explaining the evolution of gossip Pan, Xinyue; Hsiao, Vincent; Nau, Dana S ...
Proceedings of the National Academy of Sciences - PNAS,
02/2024, Letnik:
121, Številka:
9
Journal Article
Recenzirano
Odprti dostop
Gossip, the exchange of personal information about absent third parties, is ubiquitous in human societies. However, the evolution of gossip remains a puzzle. The current article proposes an ...evolutionary cycle of gossip and uses an agent-based evolutionary game-theoretic model to assess it. We argue that the evolution of gossip is the joint consequence of its reputation dissemination and selfishness deterrence functions. Specifically, the dissemination of information about individuals' reputations leads more individuals to condition their behavior on others' reputations. This induces individuals to behave more cooperatively toward gossipers in order to improve their reputations. As a result, gossiping has an evolutionary advantage that leads to its proliferation. The evolution of gossip further facilitates these two functions of gossip and sustains the evolutionary cycle.
The COVID-19 pandemic is a global health crisis, yet certain countries have had far more success in limiting COVID-19 cases and deaths. We suggest that collective threats require a tremendous amount ...of coordination, and that strict adherence to social norms is a key mechanism that enables groups to do so. Here we examine how the strength of social norms—or cultural tightness–looseness—was associated with countries' success in limiting cases and deaths by October, 2020. We expected that tight cultures, which have strict norms and punishments for deviance, would have fewer cases and deaths per million as compared with loose cultures, which have weaker norms and are more permissive.
We estimated the relationship between cultural tightness–looseness and COVID-19 case and mortality rates as of Oct 16, 2020, using ordinary least squares regression. We fit a series of stepwise models to capture whether cultural tightness–looseness explained variation in case and death rates controlling for under-reporting, demographics, geopolitical factors, other cultural dimensions, and climate.
The results indicated that, compared with nations with high levels of cultural tightness, nations with high levels of cultural looseness are estimated to have had 4·99 times the number of cases (7132 per million vs 1428 per million, respectively) and 8·71 times the number of deaths (183 per million vs 21 per million, respectively), taking into account a number of controls. A formal evolutionary game theoretic model suggested that tight groups cooperate much faster under threat and have higher survival rates than loose groups. The results suggest that tightening social norms might confer an evolutionary advantage in times of collective threat.
Nations that are tight and abide by strict norms have had more success than those that are looser as of the October, 2020. New interventions are needed to help countries tighten social norms as they continue to battle COVID-19 and other collective threats.
Office of Naval Research, US Navy.
As punishment can be essential to cooperation and norm maintenance but costly to the punisher, many evolutionary game-theoretic studies have explored how direct punishment can evolve in populations. ...Compared to direct punishment, in which an agent acts to punish another for an interaction in which both parties were involved, the evolution of third-party punishment (3PP) is even more puzzling, because the punishing agent itself was not involved in the original interaction. Despite significant empirical studies of 3PP, little is known about the conditions under which it can evolve. We find that punishment reputation is not, by itself, sufficient for the evolution of 3PP. Drawing on research streams in sociology and psychology, we implement a structured population model and show that high strength-of-ties and low mobility are critical for the evolution of responsible 3PP. Only in such settings of high social-structural constraint are punishers able to induce self-interested agents toward cooperation, making responsible 3PP ultimately beneficial to individuals as well as the collective. Our results illuminate the conditions under which 3PP is evolutionarily adaptive in populations. Responsible 3PP can evolve and induce cooperation in cases where other mechanisms alone fail to do so.
Adversarial search, or game‐tree search, is a technique for analyzing an adversarial game to determine what moves a player should make in order to win a game. Until recently, lookahead pathology (in ...which deeper game‐tree search results in worse play) has been thought to be quite rare. We provide an analysis that shows that every game should have some sections that are locally pathological, assuming that both players can potentially win the game.
We also modify the minimax algorithm to recognize local pathologies in arbitrary games and cut off search accordingly (shallower search is more effective than deeper search when local pathologies occur). We show experimentally that our modified search procedure avoids local pathologies and consequently provides improved performance, in terms of decision accuracy, when compared with the minimax algorithm. In addition, we provide an experimental evaluation on the African game of Kalah, which shows the improved performances of our suggested error‐minimizing minimax algorithm when there is a large degree of pathology.
In this paper, we present a contract-based, decentralized planning approach for a team of autonomous unmanned surface vehicles (USV) to patrol and guard an asset in an environment with hostile boats ...and civilian traffic. The USVs in the team have to cooperatively deal with the uncertainty about which boats pose an actual threat and distribute themselves around the asset to optimize their guarding opportunities. The developed planner incorporates a contract-based algorithm for allocating tasks to the USVs through forward simulating the mission and assigning estimated utilities to candidate task allocation plans. The task allocation process uses a form of marginal cost-based contracting that allows decentralized, cooperative task negotiation among neighboring agents. The task allocation plans are realized through a corresponding set of low-level behaviors. In this paper, we demonstrate the planner using two mission scenarios. However, the planner is general enough to be used for a variety of scenarios with mission-specific tasks and behaviors. We provide detailed analysis of simulation results and discuss the impact of communication interruptions, unreliable sensor data, and simulation inaccuracies on the performance of the planner.