tailieunhanh - Piecemeal Learning of an Unknown Environment

Shrimp exploitation by tropical trawl fisheries generates significant amounts of non-shrimp by-catch. In some countries, by-catch has become an important source of income and contributes to food supply. In others, by-catch of fish, particularly small-sized, is discarded at sea. The capture of juveniles of valuable food fish constitutes a threat to the sustainable production of fish from an area. Extensive removal of non-target fish is also a threat to the biodiversity in a fishing area. If the introduction of fishing technologies and practices that reduce the capture of juveniles is successful in a few selected countries in various. | Small Journal Name 1-29 Kluwer Academic Publishers Boston. Manufactured in The Netherlands. Piecemeal Learning of an Unknown Environment MARGRIT BETKE MARGRIT@ RONALD L. RIVEST RIVEST@ MONA SINGH MONA@ Laboratory for Computer Science Massachusetts Institute of Technology 545 Technology Square Cambridge MA 02139 Editor Sally Goldman Abstract. We introduce a new learning problem learning a graph by piecemeal search in which the learner must return every so often to its starting point for refueling say . We present two linear-time piecemeal-search algorithms for learning city-block graphs grid graphs with rectangular obstacles. Keywords map learning graph algorithms robot navigation 1. Introduction We address the situation where a learner to perform a task better must learn a complete map of its environment. For example the learner might be a security guard robot a taxi driver or a trail guide. Exploration of unknown environments has been addressed by many previous authors such as Papadimitriou and Yanakakis 10 Blum Raghavan and Schieber 4 Rivest and Schapire 12 Deng and Papadimitriou 7 Betke 3 Deng Kameda and Papadimitriou 6 Rao Kareti Shi and Iyengar 11 and Bar-Eli Berman Fiat and Yan 2 . This paper considers a new constraint for some reason learning must be done piecemeal - that is a little at a time. For example a rookie taxi driver might learn a city bit by bit while returning to base between trips. A planetary exploration robot might need to return to base camp periodically to refuel to return collected samples to avoid nightfall or to perform some other task. A tourist can explore a new section of Rome each day before returning to her hotel. The piecemeal constraint means that each of the learner s exploration phases must be of limited duration. We assume that each exploration phase starts and ends at a fixed start position s. This special location might be the airport for a taxi driver a refueling station a