Abstract: A multi-agent-based grid service discovery framework was put forward, in which agents were distinguished into three categories:service-agent, request-agent and service-discovery-agent. A service description language based on fuzzy Petri nets (FPN-SDL) was proposed as a specification to publish or request for a service, it used possibility transition to represent a service or request, input places and output places to denote conditions before and after performing the service respectively, and possibility and necessity to quantify the confidence levels that the service could satisfy a request. At last this paper presented a semantic-based service matchmaking that can find an appropriate service for a request and support partial matching, and illuminated these through an example of the vehicle maintenance service system.